靜態完美雜湊

完美雜湊的定義

完美雜湊被定義為一種雜湊模型，其中任何一組 n 個元素都可以儲存在大小相同的雜湊表中，並且可以在恆定時間內執行查詢操作。它是由 Fredman、Komlos 和 Szemeredi (1984) 特別發明和討論的，因此被稱為“FKS 雜湊”。

靜態雜湊的定義

靜態雜湊定義了雜湊問題的另一種形式，它允許使用者對最終的字典集執行查詢操作（這意味著字典中的所有物件都是最終的，並且不會更改）。

應用

由於靜態雜湊需要資料庫、其物件和引用保持不變，因此其應用受到限制。包含很少更改的資訊的資料庫也符合條件，因為它只需要在極少數情況下對整個資料庫進行重新雜湊。這種雜湊方案的各種示例包括特定語言的單詞和定義集、組織人員的重要資料集等。

實現

在靜態情況下，我們提前提供了一個包含 p 個條目的集合，每個條目都與一個唯一的鍵相關聯。Fredman、Komlós 和 Szemerédi 選擇一個第一級雜湊表，大小為 s = 2(p-1) 個桶。為了構建，p 個條目由頂級雜湊函式分成 q 個桶，其中 q = 2(p-1)。然後，對於每個包含 r 個條目的桶，分配一個包含 r2 個槽的二級表，並且其雜湊函式是從一個通用雜湊函式集中隨機選擇的，以便使其無衝突並與雜湊表一起儲存。如果隨機選擇的雜湊函式建立了一個包含衝突的表，則會隨機選擇一個新的雜湊函式，直到可以保證無衝突的表。最後，使用無衝突的雜湊，將 r 個條目雜湊到二級表中。

Arnab Chakraborty

更新於: 2020年1月3日

2K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習