1. 什么是哈希算法？

hash算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨后的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數據的哈希值可以檢驗數據的完整性。一般用于快速查找和加密算法。散列就是把任意長度的輸入通過散列算法變換成固定長度的輸出，輸入稱為Key(鍵)，輸出為Hash值，即散列值hash(key)，散列算法即hash()函數（散列與哈希是對hash的不同翻譯）；實際上存儲這些散列值的是一個數組，稱為散列表，散列表用的是數組支持按照下標隨機訪問數據的特性，把數據值與數組下標按散列函數做的一一映射，從而實現O(1)的時間復雜度查詢；

10年積累的成都網站建設、成都網站設計經驗，可以快速應對客戶對網站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網絡服務。我雖然不認識你，你也不認識我。但先網站設計后付款的網站建設流程，更有長汀免費網站建設讓你可以放心的選擇與我們合作。

1.1 散列沖突

目前的哈希算法MD5、SHA、CRC等都無法做到一個不同的key對應的散列值都不一樣的散列函數，即無法避免出現不同的key映射到同一個值的情況，即出現了散列沖突，而且，因為數組的存儲空間有限，也會加大散列沖突的概率。如何解決散列沖突？我們常用的散列沖突解決方法有兩類：開放尋址法(open addressing) 和 鏈表法(chaining)。

1.1.1 開放尋址法

通過線性探測的方法找到散列表中空閑位置，寫入hash值：

如圖，834313在hash表中散列到303432的位置上，出現了沖突，則順序遍歷hash表直到找到空閑位置寫入834313；當散列表中空閑位置不多的時候，散列沖突的概率就會大大增加，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位，此時，我們用裝載因子來表示空閑位置的多少，計算公式是：散列表的裝載因子=填入表中的元素個數/散列表的長度。裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能就會下降。

當數據量比較小，裝載因子小的時候，適合采用開放尋址法，這也是java中的ThreadLocalMap使用開放尋址法解決散列沖突的原因。

1.1.2 鏈表法

鏈表法是一種更常用的散列沖突解決辦法，也更簡單。如圖：

在散列表中，每個桶/槽會對應一條鏈表，所有散列值相同的元素我們都放到相同槽位對應的鏈表中；當散列沖突比較多時，鏈表的長度也會變長，查詢hash值需要遍歷鏈表，這時查詢效率就會從O(1)退化成O(n)。

這種解決散列沖突的處理方法比較適合大對象、大數據量的散列表，而且，支持更多的優(yōu)化策略，比如使用紅黑樹代替鏈表；jdk1.8為了對HashMap做進一步優(yōu)化，引入了紅黑樹，當鏈表長度太長（默認超過8）時，鏈表就會轉換成紅黑樹，這時可以利用紅黑樹快速增刪查改的特點，提高HashMap的性能，當紅黑樹節(jié)點個數小于8個時，又將紅黑樹轉化成為鏈表，因為在數據量比較小的情況下，紅黑樹要維護平衡，比起鏈表，性能上的優(yōu)勢并不明顯。

2. 哈希算法的應用場景2.1 安全加密

最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm)和SHA(Secure Hash Algorithm 安全散列算法)，利用hash的特點計算出來的hash值很難反向推導原始數據，從而達到加密的目的。

以MD5為例子，哈希值是固定的128位二進制串，最多能表示 2^128 個數據，這個數據已經是天文數字了，散列沖突的概率要小于1/2^128，如果希望通過窮舉法來找到跟這個MD5相同的另一個數據，那耗費的時間也應該是天文數字了，所以在有限的時間內哈希算法還是很難被破解的，這也就達到了加密效果了。

2.2 數據校驗

利用Hash函數對數據敏感的特點，可以用來校驗網絡傳輸過程中的數據是否正確，防止被惡意串改。

2.3 散列函數

利用hash函數相對均勻分布的特點，取hash值作為數據存儲的位置值，讓數據均勻分布在容器里面。

2.4 負載均衡

通過hash算法，對客戶端id地址或者會話id進行計算hash值，將取得的哈希值與服務器列表的大小進行取模運算，最終得到的值就是應該被路由到的服務器編號。

2.5 數據分片

假如我們有1T的日志文件，里面記錄了用戶的搜索關鍵詞，我們想要快速統(tǒng)計出每個關鍵詞被搜索的次數，該怎么做呢？數據量比較大，很難放到一臺機的內存中，即使放到一臺機子上，處理時間也會很長，針對這個問題，我們可以先對數據進行分片，然后采用多臺機器處理的方法，來提高處理速度。

具體的思路是：為了提高處理速度，我們用n臺機器并行處理。從搜索記錄的日志文件中，依次獨處每個搜索關鍵詞，并通過哈希函數計算哈希值，然后再跟n取模，最終得到的值，就是應該被分配到的機器編號；這樣哈希值相同的搜索關鍵詞就被分配到了同一臺機器上，每個機器會分別計算關鍵詞出現的次數，最后合并起來就是最終的結果。實際上，這里的處理過程也是MapReduce的基本設計思想。

2.6 分布式存儲

對于海量的數據需要緩存的情況，一臺緩存機器肯定是不夠的，于是，我們就需要將數據分布在多臺機器上。 這時，我們可以借助前面的分片思想，即通過哈希算法對數據取哈希值，然后對機器個數取模，得到應該存儲的緩存機器編號。

但是，如果數據增多，原來的10臺機器已無法承受，需要擴容了，這時是如果所有數據都重新計算哈希值，然后重新搬移到正確的機器上，那就相當于所有的緩存數據一下子都失效了，會穿透緩存回源到數據庫，這樣就可能發(fā)生雪崩效應，壓垮數據庫。為了新增緩存機器不搬移所有的數據，一致性哈希算法就是比較好的選擇了，主要的思想是：假設我們有kge機器，數據的哈希值范圍是[0,Max]，我們將整個范圍劃分成m個小區(qū)間(m遠大于k)，每個機器負責m/k個小區(qū)間，當有新機器加入時，我們就將某幾個小區(qū)間的數據，從原來的機器中搬移到新的機器中，這樣，即不用全部重新哈希、搬移數據，也保持了各個機器上數據量的平衡。

文章名稱：哈希算法的應用場景有哪些-創(chuàng)新互聯
網站鏈接：http://chinadenli.net/article30/ecopo.html

成都網站建設公司_創(chuàng)新互聯，為您提供網站設計、標簽優(yōu)化、Google、企業(yè)建站、定制網站、網站營銷

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯