- 《資料結構與算法》專欄完整版在公衆号【書偉認視界】中檢視，轉載需聯系微信【econe0219】
散清單
散清單（Hash Table），也可直譯為哈希表。散清單是基于數組擴充得到的一種新的資料結構，是以有延續了數組最重要的一條性質：支援按下标随機通路，時間複雜度是O(1)。
通過散列函數把元素的鍵值映射為下标，然後将資料存儲在數組中對應下标的位置。我們熟悉的python的字典就是由散清單實作的。
散列函數：
直覺定義為hash(key)，key表示元素的鍵值，hash(key)指的就是經過散列函數得到的散列值。
用python的字典大概舉個例子：
定義一個變量 student = {‘name’: ‘張三’, ‘age’: 20}
hash(‘name’)得到散列值0，即第一個位置，對應元素是’張三’；hash(‘age’)得到散列值1，對應元素是20。
因為散清單中的元素不可重複，是以散列函數的設計需要有以下三個要求：
- 散列函數計算得到的散列值是一個非負整數（數組下标從0開始）；
- 如果key1≠key2，則hash(key1)≠hash(key2)；
- 如果key1=key2，則hash(key1)=hash(key2)；
散列沖突/碰撞：
指的是多個關鍵字映射到同一個數組下标位置（其實就是鴿巢原理）。解決散列沖突的辦法有開放尋址法和連結清單法。（參考連結）
1. 開放尋址法：如果出現了散列沖突，那就重新探測一個空閑位置，将其插入。
探測方法主要有三種：線性探測、二次探測、雙重探測
線性探測如下圖所示。散清單隻有兩個空位置，現有一進制素經過散列函數計算後，被散列的位置是下标6，而該位置以及有資料，于是就産生了散列沖突，于是開始往後依次周遊找到空位置，直到找到下标為2的位置，将被散列的元素插入其中。
線性探測在極端情況下可能需要探測整個散清單，最壞情況下的時間複雜度時O(n)，因為線性探測每次探測的步長是1，即下标序列依次是hash(key)+0，hash(key)+1，hash(key)+2……而二次探測的步長是原來的“二次方”，即下标序列是hash(key)+0，hash(key)+ 1 2 1^2 12，hash(key)+ 2 2 2^2 22……
雙重散列是指，使用多個散列函數hash1(key)、hash2(key)、hash3(key)…… 用第一個哈希函數計算得到的位置如果被占用，那麼再用第二個哈希函數計算散列位置，以此類推。
無論那種方法，隻要散清單中的空位置太少的話就容易構成散列沖突。為了保證散清單的操作效率，散清單中需要有一定比例的空閑位置。于是引入一個**加載因子（load factor）**來表示空位的多少。
加載因子 = 填入表中的元素個數 / 散清單的長度。 加載因子越大，說明空閑位置越少，沖突越多，散清單的性能越差。
2. 連結清單法
連結清單法相對更常用，也更簡單。如上圖所示，每個散清單中的每個槽位都有一條連結清單，所有散列值相同的元素都放在相同槽位對應的連結清單中。插入的時間複雜度是O(1)，查找删除的時間複雜度和連結清單的長度k成正比，即O(k)。
開放尋址法和連結清單法的對比
開放尋址的沖突代價更高，加載因子不能太大，适合小資料量的情況。連結清單法不受加載因子大小的影響，但如果小資料量的話，存儲連結清單指針消耗的記憶體代價更高，但是對于大資料量，指針消耗的記憶體可以忽略不計。而且連結清單還可以改造為其他的高效資料結構，如跳表、紅黑樹等，使用更加靈活，容易優化。
散清單的擴容
有不斷插入的資料，加載因子過大時，就需要對散清單進行動态擴容。每次擴容都申請原散清單大小的兩倍空間，新散清單的加載因子就變成原來的一半。擴容之後，需要對資料進行搬移操作，這時候還需要計算原散清單中的資料在新散清單中的對應位置。
資料量大時，“一次性”擴容耗時比較多。但是可以分批完成，擴容操作和插入操作交替完成。也就是說，加載因子超過一定的門檻值之後，先申請新空間，但不把資料一次性都搬移過去。當再有新資料插入時，将新資料直接插入到新散清單中，并在舊散清單中拿一個資料放到新散清單中。每次都交替插入和搬移操作，這樣均攤分析實作的插入操作就快很多，時間複雜度從O(n)變為O(1)。
《資料結構與算法》專欄完整版在公衆号【書偉認視界】中檢視，轉載需聯系微信【econe0219】
.