哈希表

哈希表（Hash table），是存儲鍵值（Key Value）對數據的一種數據結構。

例如，我們可以将人的名字作為鍵，性别作為值來存儲。通過把鍵映射到表中的一個位置來訪問數據，以提高查找速度。而這個映射關系就是哈希函數。

哈希函數

因為哈希表的數據映射關系以哈希函數為體現，為了避免小夥伴對哈希函數不夠了解，此處先介紹哈希函數。

哈希函數可以把給定的數據轉換成固定長度的無規律數值，可以把它想象成一台處理器，如下圖所示：

輸入的數據經過加工後，會輸出對應的“哈希值”。哈希值多用十六進制表示（十六進制數範圍是，數字0~9和字母a~f）。而計算機中則使用0和1表示的二進制來管理這些數據，實際上，哈希函數就是計算機内部進行的某種運算。

哈希函數的五個基本特征：

1. 不管輸入數據大或小，輸出的哈希值數據長度固定不變
2. 如果輸入的數據相同，那麼輸出的哈希值也必定相同
3. 輸入相似的數據并不會導緻輸出的哈希值也相似
4. 即使輸入的數據完全不同，輸出的哈希值也有可能相同，這種情況叫作“哈希沖突”
5. 哈希函數的輸入、輸出不可逆，即無法反向推算出原數據

哈希表結構

如果将鍵值對數據存儲在固定大小的數組中，那麼當需要查找某個數據時，我們隻能從頭開始遍曆，我相信你已經很熟悉了，這就是“線性查找”。數據量越多，線性查找耗費的時間就越長，從耗時來看，此處使用數組來存儲數據并不理想。

但使用哈希表就可以解決這個問題，首先，仍然使用具有5個存儲空間的數組來存儲數據。現在，嘗試将Sue的鍵值對數據存入數組，使用哈希函數（Hash）計算Sue的哈希值，得到的結果為83491，将哈希值對5取模（mod），求得餘數1。因此，我們将Sue數據存儲在數組1号空間中。

重複前面的操作，Tom鍵的哈希值為84274，mod 5後結果為4，将Tom數據存儲到4号空間中。

Bat鍵的哈希值為66549，mod 5後餘數為4，按照前述操作來看，我們應當将其存入4号空間中，但4号空間已經存儲了Tom的數據，這種存儲位置重複的情況叫作“沖突”。遇到此種情況，可使用鍊表結構在已有的數據後面繼續存儲數據，關于鍊表的内容可見“鍊表”篇。

繼續存儲Amy數據，Amy鍵的哈希值為65965，mod 5後的餘數為0，将其存儲在0号空間中。

Tan鍵的哈希值為83841，mod 5後的餘數為1。本應将其存儲在數組1号空間中，但1号空間已有Sue的數據，故而使用鍊表，在Sue後面繼續存儲Tan的數據。

Rob數據同上，其哈希值為82341，mod 5後的餘數為1，因“沖突”，使用鍊表結構，繼續存儲在Tan數據的後面。

像這樣存儲完數據，哈希表也就制作完成了。

查詢哈希表的數據也很簡單，先計算出目标數據鍵的哈希值，然後對其進行mod運算，得到餘數即是數組對應的空間索引。如果這個數據正好存儲在數組空間上，那當然是皆大歡喜，如果不在，就需要對單鍊表進行線性查找了。

說明

哈希表中，可以通過哈希函數（Hash）快速獲取數組中的目标數據。如果出現“沖突”，可以使用單鍊表在已有數據的後面插入新數據來解決沖突，這個方法被稱為“鍊地址法”。這樣不管數據量是多少，都可以靈活處理。

當然，除了鍊地址法以外還有其他解決沖突的方法，使用較為廣泛的是“開放地址法”。此方法是指沖突發生時，循環計算下一個後補地址，直到有滿足條件的為止。

數組空間越小，哈希表沖突的概率就越大，對單鍊表的線性查找頻率就越高。反過來，如果數組空間過大，又會出現很多閑置的存儲空間，因此，設定合适的數組空間非常重要！

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!