文章目錄
- 1.概念
- 2.實作
-
- 2.1 開放尋址法
- 2.2 連結清單法
1.概念
散清單用的是數組支援按照下标随機通路的特性，是以散清單其實就是數組的一種擴充，由數組演化而來
key
: key.
散列函數(hash函數)
：把key轉化為hash值的函數
散列值(hash值)
：數組的下标.
對hash函數的基本要求:
- 散列函數計算得到的散列值是一個非負數整數：對于數組的下标，從0開始
- 如果 key1 == key2 那麼 hash(key1) == hash(key2)
-
如果 key1 != key2 那麼 hash(key1) != hash(key2)
對于第三點，其實無法完全避免，滿足這一點的hash函數幾乎不存在。當 key1 != key2時， hash(key1) 有可能等于 hash(key2), 尤其當數組的空間有限，這中可能性就更大。這種情況較 hash沖突。
再好的hash函數也無法避免hash沖突的問題。解決hash沖突有兩個思路：
- 開放尋址法(Open addressing)
- 連結清單法(chaining)
2.實作
2.1 開放尋址法
核心思路：如果出現了散列沖突，就重新探測一個空閑的位置，将其插入。如何重新探尋新的位置？一個比較簡單的探測方法，
線性探測
：如果某個資料經過散列之後，存儲位置已經被占用了，就從目前位置開始，依次往後查找，直達找到空閑位置為止。
上圖中，橙色表示 已經有元素，黃色表示該位置空閑。hash之後，得到位置為7。此時7已經有元素，是以順序往下，8，9都有元素，從頭開始，0，1，直至找到x.
- 插入
按之前線性探方法直至找到空閑位置。時間複雜度為： 最好：下一個元素有空位 O(1) 最壞：上一個相鄰位置才有空位，需要周遊n-1次 -> O(n) 平均：(1+2+3+。。。+n-1)/(n-1) = n/2 -> O(n) - 删除
如果直接把找到的元素置空，則有問題，因為無法知道是否真正删除了元素。可以把這個元素标記為為"deleted"狀态。當周遊至這個元素時，如果key一樣，狀态已經标記為deleted，則說明已經删除。如果無找不到，則須一次周遊查找,然後删除 - 查詢
其他開放尋址方法：先通過hash查找，O(1). 如果找到hash(key)，比較key,如果key一隻，則結束。如果key不一緻，則通過線性查找，直至找到，平均為O(n)。如果該位置空閑，則說明不在數組中。- 二次探測
步長不為1，而是為原來2次方，即： hash(key) + 0, hash(key)+1, hash(key)+2, ... 變為 hash(key) + 2^0, hash(key)+2^1, hash(key)+2^2, ... - 雙重散列
不管采用哪種探測方法，當散列中空閑位置不多時，散列沖突的機率就會大大提高。為了盡可能保證散列清單的操作效率，一般情況下，我們會盡力可能保證散列中有一定比例的空閑槽位。我們用裝載因子(load factor) 來表示空位的多少使用一組hash函數，而非一個hash函數：{hash1, hash2, hash3, hash4, ...}, 當hash1(key)已經有值，則用hash2(key), 依次類推，直至找到空閑位置.
裝載因子越大，說明空閑位置越少，沖突越多，散清單的性能會下降。裝載因子 = 填入表中的元素個數 / 散清單的長度
- 二次探測
2.2 連結清單法
連結清單法是一種更加常用的散列沖突解決辦法，相對開放尋址法，它要簡單很多。如下圖。在散列中，每個”桶(bucket)“或則”槽(slot)“ 會對應一條連結清單，hash(key)相同的元素都會放入相同槽位對應的鍊條中：
時間複雜度：
對于插入和删除，
- 最好： 數組每個位置都直接插入，無需連結清單，為O(1)
- 最壞：每次hash(key)的值都一樣，此時，變成了一條連結清單，複雜度為O(n)
- 平均：均勻分布，假設有m個桶，則每條鍊的長度為 n/m, 所有複雜度為 O(k) = O(n/m)