一、什么是哈希值

哈希值是通過一個計(jì)算函數(shù)把難以比較的字符串或者其他類型的數(shù)據(jù)映射成一個整數(shù)，最常用的就是映射a～z的hash值，變成hash[(str(i)-‘a(chǎn)’]這個數(shù)是一個十進(jìn)制數(shù)，這個十進(jìn)制數(shù)把它映射到0-25，也就是數(shù)組下標(biāo)。

但通常來說是映射成1-26，因?yàn)榉奖阌?jì)算，這是最簡單的哈希值，然后這個哈希值映射成下標(biāo)，這在算法題里面經(jīng)常會出現(xiàn)，或者說可以將一個數(shù)據(jù)看成一個P進(jìn)制數(shù)，還是說上一個例子，如果是字符串對比的話，我們可以把這26個字母看成一個26進(jìn)制的數(shù)，一般的話任意子串的哈希我們一般使用前綴和的方式，這里暫時不展開了。那么這個數(shù)怎么映射呢？就是把字符串出現(xiàn)的字母都取一遍然后去當(dāng)成一個26進(jìn)制算，這樣得到的哈希值發(fā)生沖突的概率就比較低，因?yàn)檗D(zhuǎn)換為的數(shù)一定是一個少數(shù)值，比如要計(jì)算abc的值，那就是（123）26=1*26^2+2*26^1+3這個計(jì)算出來的數(shù)就是hash值。

現(xiàn)在下結(jié)論：hash值是通過一個f(hash)計(jì)算出一個整數(shù)，然后當(dāng)查找一個數(shù)據(jù)或者字符串的時候就將計(jì)算出來的整數(shù)進(jìn)行對比，只用看整數(shù)相不相等就可以，而不用去暴力O(n)(如果是要對比n個數(shù)那就是O(n^2)了，所以，hash值就是為查找算法，提供一個優(yōu)異的O(1)復(fù)雜度的解決方案（哈希的開銷主要是對函數(shù)進(jìn)行計(jì)算）另外hash值在加密問題里也很重要，通過一種不可知的hash算法將hash值計(jì)算出來然后校驗(yàn)也是一種應(yīng)用方式。

延伸閱讀：

二、Hash 算法碰撞

稍微想一下就可以發(fā)現(xiàn)，既然輸入數(shù)據(jù)長度不固定，而輸出的哈希值卻是固定長度的，這意味著哈希值是一個有限集合，而輸入數(shù)據(jù)則可以是無窮多個，那么建立一對一關(guān)系明顯是不現(xiàn)實(shí)的。所以“碰撞”是必然會發(fā)生的，所以一個成熟的哈希算法會有較好的抗沖突性，同時在實(shí)現(xiàn)哈希表的結(jié)構(gòu)時也要考慮到哈希沖突的問題。

比如“666”經(jīng)過 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”，相同 Hash 算法得到的值是一樣的。比如 WiFi 密碼如果是 8 位純數(shù)字的話，頂多就是 99999999 種可能性，破解這個密碼需要做的就是提前生成好 0 到 1 億數(shù)字的 Hash 值，然后做 1 億次布爾運(yùn)算（就是 Bool 值判斷，0 或者 1），而現(xiàn)在普通 I5 四核 CPU 每秒能到達(dá) 200 億次浮點(diǎn)數(shù)計(jì)算，做 1 億次布爾運(yùn)算也就是秒級別的時間就破解了。