桶保存鍵值,不提供保證
用雜湊表表示鍵值集合時,查詢不能把雜湊值相同的不同鍵值混為一談。分離鏈結使用函數 把每個鍵值映到 個桶之一,每個桶儲存該桶鍵值的串列。
定義 5.1.1
(分離鏈結表與負載因子)
以雜湊函數 和 個桶建立的分離鏈結表,儲存 個不同鍵值,使每個已存鍵值 恰好位於一個串列,即桶 的串列。其負載因子為 。
- 搜尋先算桶,再逐個比較該串列中的鍵值,直至找到相等者或到達末尾。
- 插入先檢查鍵值是否已存在,若不存在才加入該桶。
- 刪除從串列移除相等的鍵值。
因此即使發生碰撞,結構仍表示由不同鍵值組成的集合。
假設計算 、比較兩個鍵值及存取桶都需常數時間,每訪問一個鍵值算一次比較。鏈表刪除亦需保存前一節點的參照或等價連結。
一個具體表格
例題 5.1.2
(五個鍵值放入五個桶)
令 、,依次插入 ,並在桶尾加入。非空串列為
搜尋 訪問桶 ,做兩次鍵值比較;搜尋不存在的 訪問桶 ,也做兩次。刪除 後,桶 剩下 ,不影響找到 。鍵值碰撞不等於鍵值相等,所以搜尋必須實際比較。
常見錯誤
(把同一個桶當成相等的鍵值)
在上面的表中, 與 的雜湊值同為 。若搜尋在發現桶非空時就停止,便會回答 存在,但桶 的串列其實是 。雜湊值相同只說明應該到哪裏找;是否屬於集合,要靠把查詢鍵值與已存鍵值比較來決定,所以上面的搜尋要做兩次比較後才報告不存在。
反例模式
平均負載不是最壞情況界
負載因子 是每桶儲存鍵值數目的平均值,不是每個桶的上界。對相同的餘數雜湊,當 ,鍵值 全進入桶 :負載因子是 ,但該串列長度為 。對每個 ,使用模 餘數雜湊並插入 。負載保持為 ,但一條鏈有 個鍵值;查詢不存在的 需比較 次。確定性的雜湊及小平均負載本身不能建立常數最壞查詢界。
碰撞假設及其結果
定義 5.1.3
(具逐對碰撞界的函數族)
從鍵值映到 個桶的有限函數族 具有逐對碰撞界,若每對不同鍵值 都滿足
其中 從 均勻選取。
從這樣的函數族均勻選取 ,只選一次,並且在儲存任何鍵值之前完成。固定一組 個不同鍵值的集合 及查詢 ,並要求它們獨立於隨機選取 。
定理 5.1.4
(逐對碰撞界下的期望搜尋成本)
設 取自具逐對碰撞界的函數族,且 與 的固定不依賴 。則在儲存 的鏈結表中,鍵值比較次數的期望至多為
- 不成功搜尋():;
- 成功搜尋():。
在上述成本假設下,不成功搜尋的期望時間為 。
證明
(計算與查詢同桶的鍵值)
設 ,令 為被搜尋桶中屬於 的鍵值數目。由期望的線性性,
不成功搜尋恰好比較這 個鍵值,其餘工作(計算 、到達桶)為常數,因此期望時間為 。
對 ,被搜尋串列的長度為
同一假設用於其餘 個鍵值 ,令其期望長度至多為 。成功搜尋訪問的鍵值不多於整條串列,故無論串列次序如何,其期望比較次數至多為此值。
證明透視
線性性論證用了甚麼
論證只用到兩項:每個 的逐對界,以及期望的線性——它把 個這樣的界相加,不要求各事件之間有任何相依性條件。 與 獨立於 而固定,才能對每一對套用逐對界。成功搜尋多出的 就是查詢鍵值本身,它必定在自己的串列中。期望是對 的選擇而言,所以定理沒有說明某一個表的最長鏈;上面的反例表明,一個表可以有長度為 的鏈。
因此在此模型中,保持 有界可得期望常數查詢界。若看過雜湊函數後才自適應選擇集合或查詢,上面的固定輸入論證不會自動適用。擴容及重新雜湊有其自身成本,此處未分析。串列及桶陣列使用 空間。
例題 5.1.5
(小型函數族的精確期望鏈長)
取三個可能的鍵值 、兩個桶,並令 為從鍵值到兩個桶的全部 個函數。對兩個不同鍵值,恰好一半的函數使雜湊值相同,所以碰撞概率為 ,此族具有逐對碰撞界。儲存 ,搜尋 ,即 、、。
若 ,則 這四種選擇下,桶 中的已存鍵值數目依次為 。 的情形對稱。所以每一半中 取值 ,而
界在此取等號,而各個別表並不相同:有的有兩個鍵值的鏈,有的鏈是空的。
例題 5.1.6
(一個桶與空表)
若 ,每個函數都把全部鍵值送到桶 ,所以任何函數族的碰撞概率都是 ,逐對碰撞界顯然成立。含 個鍵值的表就是一條串列,不成功搜尋要做 次比較,而 :界 恰好取到,表只是一個鏈表。
空表 時每個串列都是空的。搜尋計算 ,到達空串列,不作任何鍵值比較,成本只是雜湊與到達桶的常數工作。這與 時的 吻合。
常見錯誤
(存好鍵值後才重新抽取雜湊函數)
期望界針對的是插入之前作出的一次隨機選擇 。若查詢到達時才抽取新函數 ,已存鍵值仍然放在舊函數 的串列中。以上面的表為例,存放在桶 的鍵值 ,可能被到桶 查找而報告不存在。只有把每個已存鍵值移到新函數給出的桶,更換函數才是合理的。
習題與解答
快速檢查
(桶追蹤。具體表格搜尋 時查哪個桶?若它不存在需多少次比較?)
解答 · 答案
由於 ,查桶 。它含 ,故比較一次。
快速檢查
(確定的碰撞。若不同鍵值滿足 ,表格能否丟棄其中之一?)
解答 · 答案
不能。兩者都留在串列中,並由相等比較區分。
快速檢查
(期望次數。在所述碰撞界下, 時不成功搜尋的期望比較次數有甚麼上界?)
解答 · 答案
對獨立於 的固定集合及不存在的固定查詢,至多 。
快速檢查
(假設。證明是否需要不同 的碰撞事件互相獨立?)
解答 · 答案
不需要;期望線性性及各自的概率上界已足夠。