算法入門之散清單簡介

什麼是散清單

散清單又被稱為哈希表，包含一個鍵key、一個值value它們之間的對應關系是一對一，散清單就提供了鍵key和值value的對應關系，基本結構如下。

鍵值不會重複是以通過鍵就可以找到與之對應的值，一般散清單查詢的時間複雜度為O(1)，那麼為什麼散清單會這麼快呢？

哈希函數

在分析原因之前我們需要知道散清單其存儲底層是數組，正是利用了數組下标擷取元素效率高的特點，但我們需要注意的是數組下标是整型，而散清單的鍵值可不一定是整型，為什麼散清單還能通過鍵高效擷取值呢？這就需要聊到哈希函數，所謂的哈希函數就是将散清單的鍵轉換為存儲數組的下标，再通過下标擷取散清單的值，擷取過程如下。

哈希函數如何實作

那麼哈希函數如何實作呢？每個語言會有自己的計算邏輯，這裡以JAVA為例。如果想要自己設計一個哈希函數第一步是需要取到每個鍵唯一且為整數的辨別，在JAVA中有這種功能的函數被稱為hashCode方法，是每個對象唯一的辨別，是以鍵對應的哈希函數就可以采用如下邏輯（JAVA中必然不可能如此簡單還會通過一系列的位運算提升效率，這裡隻是簡單讨論）。

// key.hashCode()調用鍵的hashCode方法得到唯一的int值
// arr.length表示散清單底層數組的長度
int index = key.hashCode()%arr.length;
           

哈希碰撞

無論多好的哈希函數都避免不了的一個問題就是，兩個不相同的哈希值可能計算出來的數組下标為同一個。

假設數組長度為6，需要放入兩個鍵key1和key2，key1的hashCode值為3，key2的hashCode值為9，那麼通過與數組長度模運算得到兩個數組下标都是3，如果按照數組的存儲方式，後面存儲的必然會把前面存儲的值覆寫，這種場景被稱為哈希碰撞。

為解決哈希碰撞提出了兩種方法，分别為連結清單法和開放尋址法。

開放尋址法

開放尋址法其原理就是，當存儲元素的鍵下标被占用時，自動查找下一個空擋位置存放值，如下

存在一個元素Entry2，計算其數組下标為2，也就是Entry3的位置，計算出來的數組下标被占用，那麼就往下查找下一個元素但是被Entry4占用，再去查找為空的位置，直到查找到數組下标為4的位置，插入元素儲存即可。

這種方法在JAVA中的經典應用就是ThreadLocal~

連結清單法

連結清單法就是将散清單由單純的數組存儲改為數組+連結清單組合的形式存儲，每個數組中的元素都可以了解為連結清單的頭節點，當需要存儲元素時，先判斷該下标元素是否為空如果為空之間作為頭節點插入，如果不為空則将該數組下标元素頭節點指向需要插入的元素。

JAVA中的HashMap就是采用的連結清單法來解決哈希沖突，當然連結清單法不是萬無一失，當連結清單過長那麼檢索的效率必然降低因為連結清單檢索需要周遊連結清單，時間複雜度為O(n)，是以HashMap中還會涉及到擴容，擴容後将所有的元素重新哈希，以此來達到縮短連結清單長度的目的。