本節解釋線性探測配合墓碑標記時的一般刪除與查找原理。請先自行嘗試練習,再閱讀下面的解釋與例子。
為何不能把刪除位置直接設為空
雜湊函數選出主位置,但碰撞時需要規則尋找另一位置。線性探測把有 個位置的表編號為 。
定義 5.2.1
(探測序列)
若鍵 的主位置是 ,其探測序列為
由 起計,第 次探測檢查位置 。
這序列恰好遍歷每個位置一次,即使 不是質數也一樣。因此即使沒有從未使用的位置,也必須在最多 次探測後停止。
定義 5.2.2
(位置的狀態)
每個位置恰有三種狀態之一:從未使用、帶鍵和值的存活記錄,或已刪除(墓碑)。
從未使用與已刪除均沒有存活記錄,但查找時意義不同。遇到匹配的存活鍵便找到;遇到墓碑則繼續;若表一直按以下規則維護,遇到從未使用的位置便可判定不存在。若之前仍未作出判斷,完成全部 次探測亦可判定不存在。
插入、刪除與重複鍵
定義 5.2.3
(帶墓碑的查找、插入與刪除)
每項操作都沿鍵 的探測序列進行,最多探測 次。
- 查找。 在首個存有 的存活位置停止,並傳回其值。在首個從未使用的位置,或完成 次探測後,以「不存在」停止。遇到墓碑和存有其他鍵的存活位置則繼續。
- 插入。 記住首個遇到的墓碑,但繼續探測。若鍵已存活,便在該位置更新其值。若遇到從未使用的位置, 必不存在:有已記下的墓碑便放在墓碑,否則放在該從未使用的位置。若 次探測都找不到 或從未使用的位置,有墓碑便放在已記下的墓碑;沒有墓碑則報告表已滿。
- 刪除。 先查找。找到鍵便把其位置標記為已刪除;若鍵不存在,表保持不變。
若不完成掃描便立即使用較早的墓碑,可能會為路徑更後處仍然存活的鍵產生重複項目。表滿時仍可更新已有鍵。墓碑保留了探測路徑經過該刪除位置的所有存活鍵的查找路徑。把所有存活記錄正確地重新插入新表,可以清除墓碑。
例子:繞回與更新
例題 5.2.4
(繞回、墓碑與更新)
取 ,這裏非負整數鍵使用 。在新表依次插入 、、,三者的主位置均為 ,分別放在 。刪除鍵 ,在 留下墓碑。
| 操作 | 依次檢查的位置 | 結果 |
|---|---|---|
| 查找 17 | 5, 0, 1 | 在 1 找到;0 的墓碑不會終止查找。 |
| 插入 17,值為 C | 5, 0, 1 | 更新位置 1;不要在 0 再插入一個 17。 |
| 插入 23,值為 d | 5, 0, 1, 2 | 位置 2 從未使用,故 23 不存在;重用首個墓碑 0。 |
操作後位置 分別存有鍵 ,位置 仍從未使用。最後一次插入探測超過最終放置位置,因為必須先排除表中已有 。
反例模式
以「從未使用」代替墓碑來刪除
假設上面的例子中,刪除 時在位置 寫入「從未使用」,而不是墓碑。此時表中存活記錄是位置 的鍵 和位置 的鍵 。查找 時先探測位置 (另一個鍵),再探測位置 ,它從未使用,於是以「不存在」停止。但 其實存活於位置 ,答案是錯的。同一張表也會令之後插入 時在位置 放入第二個副本。
失敗的原因正是下一節的不變量被破壞:位置 在 的探測路徑上、在其儲存位置之前,卻是從未使用。刪除必須寫入墓碑,讓查找可以越過,這樣已儲存鍵的路徑上才不會出現從未使用的位置。
例題 5.2.5
(沒有從未使用位置的表)
取 、。插入 :它們放在位置 ,表中全是存活位置。更新 的值需探測位置 ,即使表已滿也能成功。插入新鍵 則探測 ,找不到匹配、從未使用的位置或墓碑,便報告表已滿。
現在刪除 ,在位置 留下墓碑。再插入 :探測位置 (鍵 )、位置 (墓碑,記住)和位置 (鍵 )。完成全部 次探測,沒有遇到從未使用的位置或鍵 ,所以 不存在,放在已記下的墓碑,即位置 。其後查找不存在的鍵 (主位置 )會探測 ,結束它的是 次探測的上限。
例題 5.2.6
(墓碑令失敗查找變長)
取 、。把 插入位置 ,然後刪除 和 ,只有鍵 仍然存活。查找 ,其主位置為 :位置 是另一個鍵,位置 和 是墓碑,位置 從未使用。因此搜尋作了四次探測才報告不存在,雖然只有一個存活項目。反覆插入與刪除可以令大部分位置都是墓碑,那時失敗查找可接近 次探測。重建到新位置可令計數重置。
常見錯誤
(未完成掃描便在首個墓碑插入)
在第一個例子中,再次插入值為 的 ,但一見到首個墓碑(位置 )就放在那裏。位置 和 便都存有存活的 。刪除 時先找到位置 並把它變成墓碑;其後查找 會越過它,在位置 找到舊項目。已刪除的鍵帶著過時的值重新出現。掃描必須持續到找到該鍵或確定它不存在,這時才可使用墓碑。
常見錯誤
(探測沒有上限)
對第二個例子中已滿的表,若查找 時只在從未使用的位置停止,便永遠不會停止:沒有這樣的位置,探測索引會無限繞圈。「最多探測 次」是算法的一部分,不是優化。同一個上限也限制插入:沒有從未使用位置的表,插入也必須在 次探測後停止。
停止規則為何正確
假設表初始時全部從未使用,且所有更新均遵循上述規則。
命題 5.2.7
(帶墓碑的線性探測的不變量)
從全部從未使用的表開始,經過任意一連串查找、插入和刪除之後,下列兩項恆成立。
- 每個鍵至多出現在一個存活位置。
- 若鍵 存活於位置 ,則 的探測路徑上從主位置起、直到 之前(不含 )的位置,沒有從未使用的位置。
證明
(從未使用的位置只會減少)
初始時沒有存活位置,兩項顯然成立。下面證明每項操作都保持它們。
查找不改變任何東西。更新存活鍵的值不改變位置狀態。刪除把一個存活位置變成墓碑:該處的鍵不再存活,涉及它的條件隨之消失;其他存活鍵的位置與路徑不變,路徑上各位置的「從未使用」狀態也與之前相同。
考慮插入 。若 已存活,掃描到達它的位置並更新其值,其他沒有改變。否則,掃描在它涵蓋的路徑部分找不到 的存活副本;它在首個從未使用的位置停止,或在完整的 個位置循環後停止。由第二項,存活的 不可能位於首個從未使用的位置之後,也不可能在整個循環之外,所以 不存在,放入一個位置後至多有一個存活副本。所選位置是首個經過的墓碑,或掃描停止處的從未使用位置。在它之前路徑上的位置都已檢查過,並且都不是從未使用,否則掃描早已在該處停止。所以 滿足第二項。
最後,放入 是把墓碑或從未使用位置變成存活位置。從未使用位置的數目只會減少,也沒有墓碑或存活位置會再變回從未使用。原來路徑在儲存位置之前沒有從未使用位置的鍵 ,路徑上仍然沒有。因此兩項持續成立。
證明透視
為何墓碑不等於從未使用
令查找正確的不變量具有單調性:從未使用位置的集合只會縮小,因為插入填滿位置,刪除寫入的是墓碑而非從未使用。形如「我的位置之前沒有從未使用位置」的條件,因此只會受益於各項更改,不會被破壞。唯一性則倚賴另一項要素:插入在寫入之前要掃描到能證明該鍵不存在,所以首個墓碑只是候選位置。去掉第一項要素,刪除便可能抹去某個鍵的路徑,如反例所示;去掉第二項,更新便可能產生重複。重建到新位置同樣安全,因為它從沒有存活位置的表開始,並按同樣規則重新插入。
命題 5.2.8
(查找的正確性)
在上述不變量下,查找 至多檢查 個位置。若 存活於表中便傳回其值,否則報告不存在。
證明
(掃描不會越過存活的鍵)
規則規定最多探測 次。設 存活於位置 。由第二項,路徑上 之前沒有從未使用的位置,所以查找不會提早以「不存在」停止。它只會越過墓碑和存有其他鍵的位置;由唯一性,首個匹配的存活位置就是 ,所以它到達 並傳回該處的值。
設 不存活。沒有任何探測找到匹配的存活位置,所以查找只會以「不存在」結束,即在首個從未使用的位置,或完成 次探測之後。它沒有漏掉任何存活副本,因為根本沒有。
這些結論依賴維護不變量,任意損壞的表未必符合。
概念視角幾何
在圓周上閱讀不變量
把 個位置按編號次序放在一個圓周上。若有位置從未使用,這些位置便把圓周切成若干段弧。第二項不變量說的是:每個存活鍵 與其主位置 在同一段弧上,並且沿編號遞增方向看,位於 處或其後。因此從 出發的查找,在到達 之前不會碰到切口。若沒有從未使用的位置,這段弧就是整個圓周,而 次探測的上限便取代了切口的角色。
成本與練習
每次操作最多探測 個位置,故最壞探測成本為 ; 個位置使用 空間。即使存活記錄很少,大量墓碑仍可能令失敗查找很長。要主張一般的期望常數時間,必須另加雜湊與佔用情況的假設,不能只憑有雜湊函數便得出。
快速檢查
(取 、,插入 3、7、11 後刪除 7。查找 11 時依次檢查哪些位置?為何首個墓碑不能結束查找?)
解答 · 答案
鍵 放在位置 ;鍵 的主位置是 ,放在位置 ;鍵 的主位置是 ,發現位置 和 都已佔用,放在位置 。刪除 在位置 留下墓碑。查找 依次檢查位置 ,在位置 找到。位置 的墓碑只是記錄曾經有鍵在那裏,而 是在位置 被佔用時放到它後面的。若查找在墓碑處停止,便會錯誤地報告 不存在。
快速檢查
(若每個位置不是存活就是已刪除,且沒有存活鍵 ,分別說明有墓碑和沒有墓碑時如何插入 。為何必須限制掃描次數?)
解答 · 答案
有墓碑時,掃描全部 個位置而找不到 ,記住首個遇到的墓碑,並把 插入該處。沒有墓碑時,每個位置都存有其他鍵,表已滿,插入應報告失敗。必須在 次探測後停止,因為沒有從未使用的位置可以結束掃描;沒有上限,探測索引會無限繞圈。
快速檢查
(解釋為何立即在首個墓碑插入會破壞鍵的唯一性。構造一個更後位置有匹配存活鍵的簡短例子。)
解答 · 答案
墓碑並沒有說明該鍵在路徑更後處是否已經存活。取 、,插入 ,它們佔用位置 。刪除 ,在位置 留下墓碑。若再次插入 時立即放在首個墓碑,位置 就有第二個存活的 ,排在位置 的舊項目之前。這時兩個存活位置存有鍵 ,第一項不變量不成立。正確的插入會繼續到位置 ,發現 已存活,便更新它。