Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。
今天我們就一起來探索一下，哈希最底層的奧秘。
1. 哈希概念
構造一種儲存結構，通過某種函數(shù)，使得其元素的儲存位置與他的關鍵碼之間能夠建立一一映射關系，那么在查找時通過該函數(shù)很快找到相應元素。
簡言之，就是設定某一固定函數(shù)（hashFunc），通過此函數(shù)來使插入元素的值與元素位置相對應，往后我們需要查找此元素時就可以通過此函數(shù)（hashFunc）找到該值。
2. 哈希函數(shù)
散列函數(shù)（英語：Hash function）又稱散列算法、哈希函數(shù)，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。
該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。散列值通常用一個短的隨機字母和數(shù)字組成的字符串來代表。
哈希函數(shù)使得計算出來的地址均勻分布在整個空間。
3. 插入及搜索元素
根據(jù)待插入元素的關鍵碼，根據(jù)哈希函數(shù)計算出其存儲位置。
我們用除留余數(shù)法的哈希函數(shù)進行介紹：
例： 現(xiàn)有 1 ，3，4，5，6，9幾個數(shù)進行儲存，將n%10求模運算的結果作為哈希地址進行元素插入。
若想查找某一元素時，則只需要對查找元素進行哈希函數(shù)運算，得到其存放地址，就能找到該元素。
4. 哈希沖突
當出現(xiàn)插入一個元素，其根據(jù)哈希函數(shù)計算出的地址，已經(jīng)被其他元素占用的情況稱為哈希沖突。
如：
為了能更好的識別當前位置是否被占用，我們需要對每個位置進行標記
enum state{EMPTY，F(xiàn)ULL，DELETE};
注意：如果我們要刪除某一元素時，不能將其直接刪除，如果直接刪除，會對當前結構產(chǎn)生影響，導致其他元素的搜索出錯，所以當我們要刪除一個元素時，需要將其標記為刪除，而非空。
5. 開散列
開散列又稱鏈地址法，首先對關鍵碼集合用哈希函數(shù)計算哈希地址，當具有相同地址的關鍵碼時，將所有同一地址的元素，通過單鏈表的形式鏈接起來，而各鏈表的頭結點存儲在哈希表中。
下載文檔
