Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長(zhǎng)度的輸入（又叫做預(yù)映射pre-image）通過(guò)散列算法變換成固定長(zhǎng)度的輸出，該輸出就是散列值。

今天我們就一起來(lái)探索一下，哈希最底層的奧秘。

1. 哈希概念

構(gòu)造一種儲(chǔ)存結(jié)構(gòu)，通過(guò)某種函數(shù)，使得其元素的儲(chǔ)存位置與他的關(guān)鍵碼之間能夠建立一一映射關(guān)系，那么在查找時(shí)通過(guò)該函數(shù)很快找到相應(yīng)元素。

簡(jiǎn)言之，就是設(shè)定某一固定函數(shù)（hashFunc），通過(guò)此函數(shù)來(lái)使插入元素的值與元素位置相對(duì)應(yīng)，往后我們需要查找此元素時(shí)就可以通過(guò)此函數(shù)（hashFunc）找到該值。

2. 哈希函數(shù)

散列函數(shù)（英語(yǔ)：Hash function）又稱散列算法、哈希函數(shù)，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來(lái)。

該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。散列值通常用一個(gè)短的隨機(jī)字母和數(shù)字組成的字符串來(lái)代表。

哈希函數(shù)使得計(jì)算出來(lái)的地址均勻分布在整個(gè)空間。

3. 插入及搜索元素

根據(jù)待插入元素的關(guān)鍵碼，根據(jù)哈希函數(shù)計(jì)算出其存儲(chǔ)位置。

我們用除留余數(shù)法的哈希函數(shù)進(jìn)行介紹：

例： 現(xiàn)有 1 ，3，4，5，6，9幾個(gè)數(shù)進(jìn)行儲(chǔ)存，將n%10求模運(yùn)算的結(jié)果作為哈希地址進(jìn)行元素插入。

若想查找某一元素時(shí)，則只需要對(duì)查找元素進(jìn)行哈希函數(shù)運(yùn)算，得到其存放地址，就能找到該元素。

4. 哈希沖突

當(dāng)出現(xiàn)插入一個(gè)元素，其根據(jù)哈希函數(shù)計(jì)算出的地址，已經(jīng)被其他元素占用的情況稱為哈希沖突。

如：

為了能更好的識(shí)別當(dāng)前位置是否被占用，我們需要對(duì)每個(gè)位置進(jìn)行標(biāo)記

enum state{EMPTY，F(xiàn)ULL，DELETE};

注意：如果我們要?jiǎng)h除某一元素時(shí)，不能將其直接刪除，如果直接刪除，會(huì)對(duì)當(dāng)前結(jié)構(gòu)產(chǎn)生影響，導(dǎo)致其他元素的搜索出錯(cuò)，所以當(dāng)我們要?jiǎng)h除一個(gè)元素時(shí)，需要將其標(biāo)記為刪除，而非空。

5. 開(kāi)散列

開(kāi)散列又稱鏈地址法，首先對(duì)關(guān)鍵碼集合用哈希函數(shù)計(jì)算哈希地址，當(dāng)具有相同地址的關(guān)鍵碼時(shí)，將所有同一地址的元素，通過(guò)單鏈表的形式鏈接起來(lái)，而各鏈表的頭結(jié)點(diǎn)存儲(chǔ)在哈希表中。

責(zé)任編輯；zl