1. 什么是哈希算法？

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

10年積累的成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶(hù)對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶(hù)得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有長(zhǎng)汀免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

1.1 散列沖突

目前的哈希算法MD5、SHA、CRC等都無(wú)法做到一個(gè)不同的key對(duì)應(yīng)的散列值都不一樣的散列函數(shù)，即無(wú)法避免出現(xiàn)不同的key映射到同一個(gè)值的情況，即出現(xiàn)了散列沖突，而且，因?yàn)閿?shù)組的存儲(chǔ)空間有限，也會(huì)加大散列沖突的概率。如何解決散列沖突？我們常用的散列沖突解決方法有兩類(lèi)：開(kāi)放尋址法(open addressing) 和 鏈表法(chaining)。

1.1.1 開(kāi)放尋址法

通過(guò)線性探測(cè)的方法找到散列表中空閑位置，寫(xiě)入hash值：

如圖，834313在hash表中散列到303432的位置上，出現(xiàn)了沖突，則順序遍歷hash表直到找到空閑位置寫(xiě)入834313；當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突的概率就會(huì)大大增加，一般情況下，我們會(huì)盡可能保證散列表中有一定比例的空閑槽位，此時(shí)，我們用裝載因子來(lái)表示空閑位置的多少，計(jì)算公式是：散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度。裝載因子越大，說(shuō)明空閑位置越少，沖突越多，散列表的性能就會(huì)下降。

當(dāng)數(shù)據(jù)量比較小，裝載因子小的時(shí)候，適合采用開(kāi)放尋址法，這也是java中的ThreadLocalMap使用開(kāi)放尋址法解決散列沖突的原因。

1.1.2 鏈表法

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

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

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

2. 哈希算法的應(yīng)用場(chǎng)景2.1 安全加密

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

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

2.2 數(shù)據(jù)校驗(yàn)

利用Hash函數(shù)對(duì)數(shù)據(jù)敏感的特點(diǎn)，可以用來(lái)校驗(yàn)網(wǎng)絡(luò)傳輸過(guò)程中的數(shù)據(jù)是否正確，防止被惡意串改。

2.3 散列函數(shù)

利用hash函數(shù)相對(duì)均勻分布的特點(diǎn)，取hash值作為數(shù)據(jù)存儲(chǔ)的位置值，讓數(shù)據(jù)均勻分布在容器里面。

2.4 負(fù)載均衡

通過(guò)hash算法，對(duì)客戶(hù)端id地址或者會(huì)話id進(jìn)行計(jì)算hash值，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號(hào)。

2.5 數(shù)據(jù)分片

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

具體的思路是：為了提高處理速度，我們用n臺(tái)機(jī)器并行處理。從搜索記錄的日志文件中，依次獨(dú)處每個(gè)搜索關(guān)鍵詞，并通過(guò)哈希函數(shù)計(jì)算哈希值，然后再跟n取模，最終得到的值，就是應(yīng)該被分配到的機(jī)器編號(hào)；這樣哈希值相同的搜索關(guān)鍵詞就被分配到了同一臺(tái)機(jī)器上，每個(gè)機(jī)器會(huì)分別計(jì)算關(guān)鍵詞出現(xiàn)的次數(shù)，最后合并起來(lái)就是最終的結(jié)果。實(shí)際上，這里的處理過(guò)程也是MapReduce的基本設(shè)計(jì)思想。

2.6 分布式存儲(chǔ)

對(duì)于海量的數(shù)據(jù)需要緩存的情況，一臺(tái)緩存機(jī)器肯定是不夠的，于是，我們就需要將數(shù)據(jù)分布在多臺(tái)機(jī)器上。 這時(shí)，我們可以借助前面的分片思想，即通過(guò)哈希算法對(duì)數(shù)據(jù)取哈希值，然后對(duì)機(jī)器個(gè)數(shù)取模，得到應(yīng)該存儲(chǔ)的緩存機(jī)器編號(hào)。

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

網(wǎng)頁(yè)名稱(chēng)：哈希算法的應(yīng)用場(chǎng)景有哪些-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/ecopo.html