資料結構學習之：散清單

定義

散清單，也叫哈希表，是根據關鍵碼和值 (key和value) 直接進行通路的資料結構，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素。

特點

記錄的存儲位置=f(key)

這裡的對應關系 f 成為散列函數，又稱為哈希 (hash函數)，而散清單就是把Key通過一個固定的算法函數既所謂的哈希函數轉換成一個整型數字，然後就将該數字對數組長度進行取餘，取餘結果就當作數組的下标，将value存儲在以該數字為下标的數組空間裡，這種存儲空間可以充分利用數組的查找優勢來查找元素，是以查找的速度很快。

哈希表在應用中也是比較常見的，就如Java中有些集合類就是借鑒了哈希原理構造的，例如HashMap，HashTable等，利用hash表的優勢，對于集合的查找元素時非常友善的，然而，因為哈希表是基于數組衍生的資料結構，在添加删除元素方面是比較慢的，是以很多時候需要用到一種數組連結清單來做，也就是拉鍊法。拉鍊法是數組結合連結清單的一種結構，較早前的hashMap底層的存儲就是采用這種結構，直到jdk1.8之後才換成了數組加紅黑樹的結構，其示例圖如下：

從圖中可以看出，左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個連結清單的頭，當然這個連結清單可能為空，也可能元素很多。我們根據元素的一些特征把元素配置設定到不同的連結清單中去，也是根據這些特征，找到正确的連結清單，再從連結清單中找出這個元素。

哈希表的應用場景很多，當然也有很多問題要考慮，比如哈希沖突的問題，如果處理的不好會浪費大量的時間，導緻應用崩潰。