僅供個(gè)人記錄和復(fù)習(xí)

Hash函數(shù)：數(shù)字摘要

我關(guān)于Hash函數(shù)和Hash值的知識(shí)還是在Minecraft里學(xué)的。

數(shù)字摘要技術(shù)就是用Hash函數(shù)（散列函數(shù)，或者哈希函數(shù)，我習(xí)慣叫哈希）將任意長(zhǎng)度的數(shù)據(jù)變成固定長(zhǎng)度的數(shù)據(jù)的技術(shù)。關(guān)于哈希函數(shù)是怎么做到這一點(diǎn)的（也就是算法），我不會(huì)仔細(xì)記錄（不過(guò)是一些很簡(jiǎn)單的辦法，比如分成一些小段之后加起來(lái)，除一個(gè)數(shù)后取余數(shù)之類的）。注意，哈希函數(shù)與其說(shuō)是一個(gè)函數(shù)，不如說(shuō)是一種方法：它沒有特定的算法，只要能起到作用就可以了，最知名的算法如MD5和SHA-1。

容易看出，哈希函數(shù)一定是一種壓縮映射，輸入的空間遠(yuǎn)大于輸出的空間，值域比定義域小很多。哈希函數(shù)的性質(zhì)：

1.?不同的輸入值可能得到相同的輸出值（這并不是絕對(duì)的，例如線段上的點(diǎn)數(shù)量和直線上的點(diǎn)數(shù)量相等）；

2. 輸出值不同，輸入值一定不同，但輸入值不同，輸出值可能相同；

3.?哈希函數(shù)缺乏逆向規(guī)律，無(wú)法通過(guò)輸出倒推出輸入，對(duì)數(shù)據(jù)本身的保密性很好。

哈希函數(shù)到底有什么用？想象一堆數(shù)據(jù)被保存在我這里，我收到一些數(shù)據(jù)，希望找到這些數(shù)據(jù)是不是在我這里存過(guò)，如果存過(guò)的話存在哪里。唯一的辦法就是把這些收到的數(shù)據(jù)和我存著的數(shù)據(jù)一個(gè)個(gè)對(duì)比一下了，效率低得要命。

這就是最開始設(shè)計(jì)哈希函數(shù)的目的。存儲(chǔ)的記錄內(nèi)容和記錄的位置沒有關(guān)系，所以必須得挨個(gè)比對(duì)。假如記錄內(nèi)容和所在位置是有關(guān)的，只需要按照事先制作的表，就能不對(duì)比記錄的具體內(nèi)容而直接找到它們的存儲(chǔ)地址。

具體來(lái)說(shuō)，在一個(gè)表中存在一個(gè)函數(shù)，可以根據(jù)輸入的關(guān)鍵字得到包括該關(guān)鍵字的記錄在表中的地址，這個(gè)函數(shù)就是哈希函數(shù)（散列函數(shù)），這個(gè)表就是哈希表Hash Table，哈希函數(shù)得到的值（地址Address）就是哈希值（地址）。哈希函數(shù)在設(shè)計(jì)時(shí)是用來(lái)加快查找速度的，而當(dāng)在把不定長(zhǎng)度的數(shù)據(jù)變成一定長(zhǎng)度的“摘要Digest”時(shí)也可以用哈希函數(shù)，這個(gè)時(shí)候輸出的哈希值叫做數(shù)據(jù)摘要。

上文我們提到過(guò)，不同的輸入可以有相同的輸出，這叫做沖突Collision，這要通過(guò)開放尋址或者鏈?zhǔn)降刂贩▉?lái)解決，在此不詳細(xì)記錄。