資料結構中的溢位處理

當一個新對 (鍵，元素) 的主桶已滿時，就會發生溢位。

我們可以透過以下方式解決溢位問題：

以某種系統的方式搜尋雜湊表，找到一個未滿的桶。

• 線性探測（線性開放定址）。
• 二次探測。
• 隨機探測。

允許每個桶都維護一個列表，其中包含所有以它為主桶的對，從而消除溢位。

• 陣列線性列表。
• 鏈。

開放定址是為了確保所有元素都直接儲存在雜湊表中，因此它嘗試透過實施各種方法來解決衝突。

線性探測透過將資料放置在表中下一個空閒槽中來解決衝突。

線性探測的效能

• 最壞情況下的查詢/插入/刪除時間為 θ(m)，其中 m 表示表中對的數量。
• 當所有對都位於同一個簇中時，就會發生這種情況。

線性探測的問題

• 識別符號傾向於聚集在一起
• 相鄰的簇傾向於合併
• 增加或提高搜尋時間

二次探測

線性探測搜尋桶 (H(x)+i2)%b；H(x) 表示 x 的雜湊函式

二次探測使用 i 的二次函式作為增量

檢查桶 H(x)、(H(x)+i2)%b、(H(x)-i2)%b，其中 1<=i<=(b-1)/2

b 表示一個形如 4j+3 的素數，其中 j 是一個整數

隨機探測

隨機探測結合了隨機數。

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].

Arnab Chakraborty

更新於: 2020年1月8日

7K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始