一、什么是哈希值
哈希值是通過一個計算函數把難以比較的字符串或者其他類型的數據映射成一個整數,最常用的就是映射a~z的hash值,變成hash[(str(i)-‘a’]這個數是一個十進制數,這個十進制數把它映射到0-25,也就是數組下標。
但通常來說是映射成1-26,因為方便計算,這是最簡單的哈希值,然后這個哈希值映射成下標,這在算法題里面經常會出現,或者說可以將一個數據看成一個P進制數,還是說上一個例子,如果是字符串對比的話,我們可以把這26個字母看成一個26進制的數,一般的話任意子串的哈希我們一般使用前綴和的方式,這里暫時不展開了。那么這個數怎么映射呢?就是把字符串出現的字母都取一遍然后去當成一個26進制算,這樣得到的哈希值發生沖突的概率就比較低,因為轉換為的數一定是一個少數值,比如要計算abc的值,那就是(123)26=1*26^2+2*26^1+3這個計算出來的數就是hash值。
現在下結論:hash值是通過一個f(hash)計算出一個整數,然后當查找一個數據或者字符串的時候就將計算出來的整數進行對比,只用看整數相不相等就可以,而不用去暴力O(n)(如果是要對比n個數那就是O(n^2)了,所以,hash值就是為查找算法,提供一個優異的O(1)復雜度的解決方案(哈希的開銷主要是對函數進行計算)另外hash值在加密問題里也很重要,通過一種不可知的hash算法將hash值計算出來然后校驗也是一種應用方式。
延伸閱讀:
二、Hash 算法碰撞
稍微想一下就可以發現,既然輸入數據長度不固定,而輸出的哈希值卻是固定長度的,這意味著哈希值是一個有限集合,而輸入數據則可以是無窮多個,那么建立一對一關系明顯是不現實的。所以“碰撞”是必然會發生的,所以一個成熟的哈希算法會有較好的抗沖突性,同時在實現哈希表的結構時也要考慮到哈希沖突的問題。
比如“666”經過 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”,相同 Hash 算法得到的值是一樣的。比如 WiFi 密碼如果是 8 位純數字的話,頂多就是 99999999 種可能性,破解這個密碼需要做的就是提前生成好 0 到 1 億數字的 Hash 值,然后做 1 億次布爾運算(就是 Bool 值判斷,0 或者 1),而現在普通 I5 四核 CPU 每秒能到達 200 億次浮點數計算,做 1 億次布爾運算也就是秒級別的時間就破解了。