字典必須分清不同的鍵,即使它們關聯的值相同。雜湊表先把鍵轉成較小的桶索引,再在該桶內分辨實際的鍵。這項轉換之所以有用,正是因為桶的數目可以遠少於可能的鍵數。因此,一般而言碰撞無法避免;正確的設計必須處理碰撞,而不是假設它永不發生。
分離鏈結法的正確性容易看清:每個桶儲存一條項目的鏈表,查詢沿串列比較真正的鍵。效能則是另一個問題。我們先說明為何負載因子本身不能保證短鏈,再從適當的隨機雜湊族選擇函數,證明期望成本界。
桶是位置,不是鍵的身分
定義 16.1.1
(鏈結不變量與映射操作)
設固定雜湊函數為 ,共有 個桶。每個儲存項目是一個鍵值對。鏈結不變量要求:
- 每個已儲存鍵 恰好出現一次,而且位於桶 。
- 該項目儲存目前與 關聯的值。
- 每個桶都是有限、無環的鏈表。
get(x) 傳回與 關聯的值,或表示鍵不存在。put(x,v) 替換既有鍵的值;若 不存在,則新增項目。erase(x) 在鍵存在時移除它。不同鍵可以有相同的桶索引,而不違反不變量。
查詢先計算 ,只搜尋該條鏈。若找到相等的鍵,唯一性便確定了所需的值。若到達鏈尾,該鍵就是不存在:不變量禁止它出現在其他桶。若只比較桶索引,反而會丟掉分辨碰撞鍵所需的資訊。
插入先搜尋既有鍵。找到時只修改值,不新增項目,也不改變鍵數;否則把新項目接到所選鏈的開頭。刪除則改動桶首指標或前一項目的 next 指標,把匹配項目從鏈中移除。其他項目的鍵和桶位置都不變,因此這些局部修改保留不變量。
追蹤碰撞,不遺失任何鍵
例題 16.1.2
(三個不同鍵,共用一條鏈)
使用五個桶,對 0 至 16 的整數鍵定義
兩次取模是分開的步驟:
| 鍵 | 桶 | |
|---|---|---|
依次插入 (0, "A")、(5, "B")、(9, "C"),每次把新項目放到鏈首。桶 1 變成
head -> (9, "C") -> (5, "B") -> (0, "A") -> end
get(5) 比較 9,再比較 5,傳回 "B"。put(5, "B2") 只修改該項目的值,長度仍為三,不能另加第二個鍵為 5 的項目。
現在執行 erase(5),令 9 的項目直接指向 0 的項目。其餘兩鍵仍然可達。失敗查詢 get(13) 比較這兩項後才表示不存在,不能只因 13 亦在桶 1,便傳回其中某個值。
鏈長可以大於一,而每個項目仍然有效。刪除中間節點亦不會留下需要標記的空洞,因為鏈指標已繞過它。這些敘述適用於分離鏈結法;透過探測其他陣列位置處理碰撞的表,具有不同的搜尋不變量。
常見錯誤
(先搜尋,才放到鏈首)
若 put(5, "B2") 直接把新項目放到鏈首,桶 1 會變成 (5, "B2") -> (9, "C") -> (5, "B") -> (0, "A"):同一個鍵有兩個項目。之後 erase(5) 只會移除第一個,舊值 "B" 便會在 get(5) 中重現。鏈結不變量規定每個鍵至多出現一次,所以插入前必須先搜尋該鏈,然後才放到鏈首。
負載因子能說明甚麼?
儲存 個鍵時,定義負載因子為 。所有鏈長的總和是 ,所以對桶取平均的鏈長恰為 。但這個算術事實,沒有保證某次查詢選中的鏈很短。
反例模式
平均很小,查詢選中的鏈仍可能很長
考慮確定性規則 。鍵 全在桶 0,其餘四個桶為空。負載因子是 ,但失敗查詢 20 需要比較全部四項。繼續加入五的不同倍數,只會延長同一條鏈。
一般而言,若全部 個鍵都在被查詢的桶,查詢可需要 次比較;各桶平均仍是 。有用的期望時間結論因此必須交代隨機性的來源及碰撞保證,不能只從負載因子的定義推出。
精確說明隨機性保證甚麼
定義 16.1.3
(通用雜湊族)
從 到 個桶的有限雜湊族 稱為通用,若對每對固定且不同的鍵 ,均有
隨機的是所選函數。敘述中的鍵固定,而且不依賴這次選擇。通用雜湊族不要求每個被選中的函數都沒有碰撞。雜湊族按參數索引;不同參數可以剛好定義相同的桶函數。
選好函數後,只要項目仍留在原桶,就保持函數不變。以下期望是對初次選擇取平均,不是對鍵值或鏈內項目的隨機次序取平均。
常見錯誤
(每次操作都重新抽取雜湊函數)
下面的期望針對的是在儲存任何項目之前所作的一次隨機選擇。若每次查詢都重新抽取函數,不變量便會被破壞:鍵 0 存放在桶 ,而查詢搜尋桶 ,通常會找不到。只有在同時把所有已存項目重新雜湊之後,更換函數才是合理的。
定理 16.1.4
(通用族下的期望鏈長)
設 是映入 個桶的通用族,並設 從中均勻選取一次。設 為含 個儲存鍵的集合, 為一個鍵,兩者都固定而不依賴 。在鏈結表中,查詢 比較的鍵數:
- 若 ,期望至多為 ;
- 若 ,期望至多為 。
證明
(以指示變量計算碰撞的鍵)
先設 。對每個 ,設
被查詢鏈的項目數是 。利用期望的線性及通用性,
失敗查詢恰好比較這 個鍵。雜湊計算及取桶只需常數工作,所以若鍵的雜湊與比較均需常數時間,期望時間就是 。
現設 。對 中的 個鍵 作同樣論證,得到與 同桶的其他鍵,其期望數目至多為 。即使 的項目位於鏈尾,查詢也在該處停止,所以比較次數至多是一次加上每個其他同桶鍵各一次:
證明透視
指示變量論證用了甚麼
論證用到三項要素,各用一次。通用性把每一對 限制在 以內;期望的線性把這 個上界相加; 與 在 之前已經固定,通用性不等式才能適用於每一對。指示變量 不必互相獨立,因為線性並不要求獨立。若鍵是在觀察 之後才選的,例如 個鍵全落在同一桶,鏈長便是 ,界 就不成立,正如上面的反例。
put 和 erase 內的搜尋具有相應界,之後的指標或值更新只需常數時間。某個已選函數仍可能產生長鏈,所以最壞查詢時間仍是線性。若先觀察函數,再刻意選擇碰撞鍵,也不滿足證明所用的獨立選擇假設。
用質數模數建立通用族
設 為質數,,鍵限制為整數 。從 均勻選 ,從 均勻選 ,兩次選擇獨立。定義
第一步在域 中運算;第二步把 種輸出分到 個桶。要證明碰撞界,必須同時分析兩個不同鍵,而不只是說一個輸出分布得很散。
定理 16.1.5
(質數模數下的仿射族是通用族)
設 為質數,。從 均勻選 ,從 均勻選 ,兩次選擇獨立,並在鍵 上令 。則對所有不同的鍵 ,
證明
(先數不同的域輸出對,再數桶碰撞)
固定 中的 。對指定的不同輸出 ,方程
在 中有唯一解
因 是質數且 非零,逆元存在。此解滿足 。反過來,非零 不會把不同的 映成相同域輸出。
因此, 個等可能的參數對 ,恰好各自產生一次每個有序且不同的輸出對 。給定第一個輸出 ,第二個輸出在其餘 個餘數中均勻分布。兩輸出必定不同,所以並不獨立。
再對 取模後,每桶至多含 個域餘數。固定 後,其餘餘數中至多有 個與它同桶。因此
它不要求 可被 整除,也不要求最後各桶的概率完全相等。
證明透視
由參數到輸出的變量替換
關鍵一步,是不再把 當作隨機對象,而改為觀察輸出對 :映射 是由 個參數對到有序且不同的餘數對的雙射。質數性只用一次,就是求 的逆元。條件 恰好對應 ,所以 取遍全部餘數,而 不能。最後對 取模是界唯一可能放鬆的地方:它只數出至多 個與 同桶的餘數。若 與 在 中相等,則對 根本無解,見下面的反例。
例題 16.1.6
(精確碰撞概率不必等於上界)
取 、,固定鍵 0 和 1。參數 有 種選擇,對應全部有序且不同的域輸出對。
桶 0 含餘數 ,桶 1 含 。位於同桶的有序不同輸出對共有
精確碰撞概率為 ,不超過 。單一域輸出在五個餘數中均勻分布,但桶概率是 和 ,不是各一半。指示變量證明只需要通用性的碰撞不等式,不需要桶輸出完全均勻。
反例模式
鍵的定義域是定理的一部分
若程式把 0 與 17 視為不同鍵,卻使用 的族,那麼每組參數下, 與 對 17 取模後都相同。兩鍵的碰撞概率是一,不會因隨機選 而改善。
這沒有矛盾:兩者在 中是同一元素,違反不同域鍵的假設。實作必須把允許的鍵單射地表示為域元素,或使用另一項有理據的雜湊構造。同樣,證明靠質數保證逆元,不能隨意用合數取代 。
例題 16.1.7
(一個桶與空表)
取 。映入一個桶的函數都是常數函數,所以任何族都是通用的,因為 ,而碰撞概率至多為 1。每個鍵都在桶 0,所以儲存 個鍵時,失敗查詢要比較全部 個。此時 ,定理的期望界恰好取等號,表已退化為單一鏈表。
另一端是空表 。查詢計算 ,到達空鏈,不作任何鍵比較,成本就是雜湊與取桶的常數。這與 時的 吻合:界中的 不能省略。
直接實作映射不變量
以下實作接受 的整數鍵。建構時假設 prime 確實是質數;本例不處理質數測試。程式檢查參數範圍,但不會隨機選參數。傳入 (17, 5, 3, 1) 可重現前面的確定性例子。若要使用期望界,須按上述均勻分布選參數,且選擇不依賴輸入鍵。
class Entry:
def __init__(self, key, value, next_entry):
self.key = key
self.value = value
self.next = next_entry
class ChainedMap:
def __init__(self, prime, bucket_count, a, b):
if not (1 <= bucket_count <= prime and
1 <= a < prime and 0 <= b < prime):
raise ValueError("invalid hash parameter range")
self.prime = prime
self.a, self.b = a, b
self.buckets = [None] * bucket_count
self.size = 0
def _index(self, key):
if not isinstance(key, int) or not 0 <= key < self.prime:
raise ValueError("key outside the integer field domain")
return ((self.a * key + self.b) % self.prime) % len(self.buckets)
def get(self, key):
node = self.buckets[self._index(key)]
while node is not None:
if node.key == key:
return node.value
node = node.next
raise KeyError(key)
def put(self, key, value):
index = self._index(key)
node = self.buckets[index]
while node is not None:
if node.key == key:
node.value = value
return False
node = node.next
self.buckets[index] = Entry(key, value, self.buckets[index])
self.size += 1
return True
def erase(self, key):
index = self._index(key)
previous = None
node = self.buckets[index]
while node is not None:
if node.key == key:
if previous is None:
self.buckets[index] = node.next
else:
previous.next = node.next
self.size -= 1
return True
previous, node = node, node.next
return False
項目仍在表內時,保持 prime、a、b 及桶數不變。改函數或桶數時,必須按新索引重新分配每個項目,否則查詢不變量失效。項目佔 空間,桶首指標佔 ,初始化需 時間。
在負載因子有界、隨機選擇及機器字運算假設成立時,操作的期望成本為常數。表增長時若要保持有界負載,需要擴容及重新雜湊策略。重建整張表是額外操作,其序列成本須另外分析;本節的固定狀態期望界不會令重建變成常數時間。
練習與詳解
快速檢查
(更新碰撞鍵,不能新增重複項目)
沿用五個桶的例子,插入 (0, "A")、(5, "B")、(9, "C"),把 5 的值改為 "B2",再刪除 9。給出桶 1 的最終鏈、鍵數、get(5),以及失敗查詢 get(13) 的鍵比較次數。
解答 · 答案
最終鏈為 (5, "B2") -> (0, "A") -> end。更新 5 只改值,刪除鏈首 9 則改桶首指標。鍵數是二,get(5) 傳回 "B2";get(13) 比較剩下的兩鍵後,才表示不存在。
快速檢查
(套用期望比較次數界)
固定的一千個鍵以均勻選取的通用雜湊函數放入 250 個桶。固定的不存在查詢,其期望比較次數上界是多少?固定的存在查詢又是多少?是否每次實際執行都滿足這些界?
解答 · 答案
不存在查詢的界為 。存在查詢的界為 。雜湊計算另加常數工作。期望是對函數選擇而言,鍵與查詢均固定而不依賴該選擇。某個選擇仍可能產生長鏈,所以不是每次實際執行的界。
快速檢查
(找出指示變量證明真正需要的假設)
不同儲存鍵的碰撞指示變量必須互相獨立嗎?套用通用性不等式時,對查詢及儲存鍵用了甚麼假設?
解答 · 答案
毋須互相獨立,因為任意有限和都滿足期望線性。每對不同鍵各自需要滿足碰撞概率界。儲存集合及查詢固定,不依賴隨機雜湊選擇;若知道函數後才適應性地選鍵,便需要另一個論證。
快速檢查
(解釋每組參數都會出現的碰撞)
質數為 17 時,為何整數鍵 2 和 19 永遠有相同域輸出?若字典要分辨它們,套用通用族定理前必須改變哪項條件?
解答 · 答案
兩鍵之差為 17,所以對每個 ,。它們表示同一個域元素。定理要求允許的不同鍵具有不同域表示;例如對有限非負整數鍵域,選擇比所有鍵都大的質數。只改隨機種子,無法修復定義域違規。
快速檢查
(精確計算小型族的碰撞數)
對 及固定不同鍵,為何二十種參數中有八種碰撞?某一桶的概率為 ,是否違反通用性?
解答 · 答案
仿射參數把全部有序不同域輸出對各列一次。桶 0 的三個餘數貢獻 對;桶 1 的兩個餘數貢獻 對,合共八對。因此碰撞概率為 。通用性限制兩個不同鍵的碰撞概率,不要求各桶概率恰為 。
快速檢查
(修改參數會改變查詢位置)
用 儲存鍵 0。不移動項目,直接把參數改成 。鍵 0 實際在哪個桶?新查詢會搜尋哪個桶?缺少了甚麼操作?
解答 · 答案
項目仍實際位於舊索引的桶 1。新函數把 0 送到桶 0,查詢便會錯誤地表示不存在。改參數時,必須把每個已存項目重新雜湊到新桶。新函數在數學上有效,不代表舊表的表示不變量仍然成立。