資料結構/雜湊表
雜湊表或雜湊對映是一種資料結構，它將鍵與值關聯起來。它最有效地支援的主要操作是查詢：給定一個鍵（例如，一個人的姓名），找到相應的鍵值（例如，該人的電話號碼）。它的工作原理是使用雜湊函式將鍵轉換為雜湊值，雜湊值是一個數字，雜湊表使用它來定位所需的值。此雜湊值直接對映到鍵/值對陣列中的一個桶，因此得名雜湊對映。對映方法讓我們直接訪問任何鍵/值對的儲存位置。
雜湊表<元素> 操作
make-hash-table(整數 n): 雜湊表
- 建立一個具有 n 個桶的雜湊表。
get-value(雜湊表 h, 可比較的 key): 元素
- 返回給定 key 的元素的值。key 必須是某個可比較的型別。
set-value(雜湊表 h, 可比較的 key, 元素 new-value)
- 將給定 key 的陣列元素設定為等於 new-value。key 必須是某個可比較的型別。
remove(雜湊表 h, 可比較的 key)
- 從雜湊表中刪除給定 key 的元素。key 必須是某個可比較的型別。
雜湊表通常用於實現關聯陣列、集合和快取。與陣列類似，雜湊表在平均情況下提供恆定時間的O(1) 查詢，無論表中有多少項。在大多數雜湊表方案中，（希望很少見的）最壞情況查詢時間是 O(n)。[1] 與其他關聯陣列資料結構相比，當我們需要儲存大量資料記錄時，雜湊表最有用。
雜湊表可以用作記憶體中的資料結構。雜湊表也可以用於持久資料結構；資料庫索引通常使用基於雜湊表的磁碟資料結構。
雜湊表還用於在許多資料壓縮實現中加快字串搜尋。
一個好的雜湊函式對於雜湊表的良好效能至關重要。選擇一個糟糕的雜湊函式可能會導致聚類行為，在這種行為中，鍵對映到同一個雜湊桶（即衝突）的機率明顯高於隨機函式的預期。在任何雜湊實現中，衝突發生的非零機率是不可避免的，但解決衝突的操作次數通常與對映到同一個桶的鍵的數量成線性關係，因此過多的衝突會顯著降低效能。此外，一些雜湊函式在計算上很昂貴，因此計算雜湊值所花費的時間（以及在某些情況下記憶體）可能會很繁重。
選擇一個好的雜湊函式很棘手。文獻中充斥著糟糕的選擇，至少從現代標準來看是這樣的。例如，在《計算機程式設計藝術》中，Knuth 提倡的非常流行的乘法雜湊演算法具有特別糟糕的聚類行為（見下面的參考文獻）。然而，由於糟糕的雜湊演算法僅僅會降低特定輸入鍵分佈下雜湊表的效能，因此這種問題經常得不到檢測。
文獻中關於選擇雜湊函式的標準也很稀少。與大多數其他基本演算法和資料結構不同，對於什麼是“好的”雜湊函式，還沒有普遍共識。本節的其餘部分將按照三個標準進行組織：簡單性、速度和強度，並介紹已知根據這些標準表現良好的演算法。
簡單性和速度很容易客觀地測量（例如，透過程式碼行數和 CPU 基準測試），但強度是一個更難以捉摸的概念。顯然，加密雜湊函式（如 SHA-1）將滿足雜湊表所需的相對寬鬆的強度要求，但它們的緩慢和複雜性使其不具有吸引力。事實上，即使是加密雜湊也不能提供對想要透過選擇所有都雜湊到同一個桶的鍵來降低雜湊表效能的對手的保護。對於這些特殊情況，應該使用通用雜湊函式，而不是任何一個靜態雜湊函式，無論它多麼複雜。
由於沒有衡量雜湊函式強度的標準方法，目前的技術是採用一系列統計測試來衡量雜湊函式是否可以很容易地與隨機函式區分開。可以說，最重要的測試是確定雜湊函式是否顯示雪崩效應，它本質上是指輸入鍵的任何一位變化平均應該影響輸出中的二分之一的位。Bret Mulvey 提倡特別測試嚴格雪崩條件，它表明，對於任何一位變化，每個輸出位應該以二分之一的機率改變，獨立於鍵中的其他位。純粹的加法雜湊函式，例如CRC，慘敗地未能滿足這個更強的條件。
顯然，一個強大的雜湊函式應該具有均勻分佈的雜湊值。Bret Mulvey 建議使用基於2 的冪雜湊表大小的卡方檢驗，大小範圍從 21 到 216。與許多其他用於衡量雜湊函式的建議方法相比，此測試的敏感度要高得多，它在許多流行的雜湊函式中發現了問題。
幸運的是，有一些好的雜湊函式滿足所有這些標準。最簡單的類在內迴圈的每次迭代中都消耗輸入鍵的一個位元組。在這個類中，簡單性和速度密切相關，因為快速演算法根本沒有時間執行復雜的計算。在這些演算法中，一個表現特別好的演算法是 Jenkins One-at-a-time 雜湊演算法，它改編自Bob Jenkins（它的創造者）的文章。
uint32 joaat_hash(uchar *key, size_t len)
{
uint32 hash = 0;
size_t i;
for (i = 0; i < len; i++)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
右側顯示了此雜湊的雪崩行為。該影像是使用 Bret Mulvey 的 Hash.cs 工具集 中的 AvalancheTest 製作的。每行對應輸入中的一個位，每列對應輸出中的一個位。綠色方塊表示良好的混合行為，黃色方塊表示弱混合行為，紅色表示沒有混合。最後一個位元組中只有幾個位混合不好，這比許多廣泛使用的雜湊函式的效能要好得多。
許多常用的雜湊函式在進行這種嚴格的雪崩測試時表現不佳。例如，廣受好評的 FNV 雜湊在短鍵的情況下，顯示了許多位根本沒有混合。請參閱 Bret Mulvey 對 FNV 的評估，以獲取更全面的分析。
如果速度比簡單性更重要，那麼那些每次迭代消耗多個位元組塊的雜湊函式類可能值得關注。其中最複雜的是 Bob Jenkins 的“lookup3”，它以 12 位元組（96 位）塊消耗輸入。不過請注意，使用此雜湊帶來的任何速度改進，只有在大型鍵的情況下才可能有用，並且更高的複雜性也可能帶來速度方面的後果，例如阻止最佳化編譯器內聯雜湊函式。Bret Mulvey 分析了 早期版本 lookup2，發現它具有極佳的雪崩行為。
雜湊函式的一個理想特性是，可以簡單地透過掩碼來將雜湊值（通常為 32 位）轉換為特定大小雜湊表的桶索引，僅保留較低的 k 位以用於大小為 2k 的表（此操作等效於計算雜湊值 模 表的大小）。此特性允許使用增量加倍雜湊表大小的技術——舊錶中的每個桶在新的表中僅對映到兩個桶。由於 FNV 雜湊使用 XOR 摺疊，因此它不具有此特性。一些舊的雜湊函式更糟糕，要求表的大小是素數而不是 2 的冪，再次將桶索引計算為雜湊值模表的大小。通常，這種要求是函式本質上較弱的標誌；使用素數表大小是使用更強函式的糟糕替代品。
衝突解決
[edit | edit source]如果兩個鍵對映到同一個索引，則相應的記錄不能儲存在同一個位置。因此，如果該位置已被佔用，我們必須找到另一個位置來儲存新記錄，並且必須以一種可以在以後查詢時找到它的方式來執行此操作。
為了說明良好的衝突解決策略的重要性，請考慮以下結果，該結果使用 生日悖論 推匯出。即使我們假設我們的雜湊函式在陣列上輸出 均勻分佈 的隨機索引，即使對於具有 100 萬個條目的陣列，在它包含 2500 條記錄之前至少發生一次衝突的機率為 95%。
有很多衝突解決技術，但最受歡迎的是鏈式雜湊法和開放定址法。
鏈式雜湊法
[edit | edit source]
在最簡單的鏈式雜湊表技術中，陣列中的每個槽位都引用一個 連結串列，其中包含插入到相同槽位的記錄。插入需要找到正確的槽位，並在該槽位的列表的任一端追加；刪除需要搜尋列表並刪除。
鏈式雜湊表比開放定址雜湊表具有優勢，因為刪除操作很簡單，並且可以更長時間地推遲表的大小調整，因為即使每個槽位都被使用，效能的 下降也更加平緩。實際上，許多鏈式雜湊表可能根本不需要調整大小，因為隨著表填滿，效能下降是線性的。例如，一個包含其推薦容量兩倍資料的鏈式雜湊表，其平均速度大約僅為相同表在其推薦容量下的兩倍慢。
鏈式雜湊表繼承了連結串列的缺點。在儲存小記錄時，連結串列的開銷可能很大。另一個缺點是遍歷連結串列的 快取效能 很差。
可以使用其他資料結構來代替連結串列。例如，使用 自平衡樹，可以將雜湊表的理論最壞情況時間從 O(n) 降至 O(log n)。但是，由於每個列表都希望很短，因此這種方法通常效率低下，除非雜湊表設計為以滿負荷執行，或者發生異常高的衝突率，就像在旨在導致衝突的輸入中可能會發生的那樣。 動態陣列 也可以用來減少空間開銷，並在記錄較小時提高快取效能。
一些鏈式實現使用了一種最佳化，即每個鏈的第一個記錄儲存在表中。雖然這可以提高效能，但通常不推薦這樣做：具有合理負載因子的鏈式表包含大量的空槽位，而較大的槽位大小會導致它們浪費大量空間。
開放定址法
[edit | edit source]
開放定址雜湊表可以將記錄直接儲存在陣列中。透過探測來解決雜湊衝突，或者在陣列中搜索備用位置（探測序列），直到找到目標記錄，或者找到一個未使用的陣列槽位，這表明表中沒有這樣的鍵。眾所周知的探測序列包括
- 線性探測
- 其中探測之間的間隔是固定的——通常為 1，
- 二次探測
- 其中探測之間的間隔線性增加（因此，索引由二次函式描述），以及
- 雙重雜湊
- 其中探測之間的間隔對於每個記錄是固定的，但透過另一個雜湊函式計算得出。
這些方法之間主要權衡在於，線性探測具有最佳的快取效能，但對聚類最為敏感，而雙重雜湊的快取效能很差，但幾乎沒有聚類現象；二次探測在這兩個方面都處於中間位置。雙重雜湊可能比其他形式的探測需要更多的計算。一些開放定址方法，如 後進先出雜湊 和 布穀鳥雜湊 會在陣列中移動現有的鍵以騰出空間存放新鍵。這提供了比基於探測的方法更好的最大搜索時間。
對開放定址雜湊表效能的關鍵影響是負載因子；即陣列中使用的槽位的比例。隨著負載因子增加到 100%，找到或插入給定鍵可能需要的探測次數急劇增加。一旦表已滿，探測演算法甚至可能無法終止。即使使用良好的雜湊函式，負載因子通常也限制在 80%。不良的雜湊函式即使在非常低的負載因子下也會表現出較差的效能，因為它們會產生大量的聚類。導致雜湊函式聚類的因素尚不清楚，並且很容易無意中編寫會導致嚴重聚類的雜湊函式。
示例虛擬碼
[edit | edit source]以下 虛擬碼 是開放定址雜湊表的實現，它使用線性探測和單槽位步進，這是一種常見的方法，如果雜湊函式很好，它將非常有效。lookup、set 和 remove 函式中的每一個都使用一個共同的內部函式 findSlot 來定位陣列槽位，該槽位要麼包含給定鍵，要麼應該包含給定鍵。
record pair { key, value }
var pair array slot[0..numSlots-1]
function findSlot(key)
i := hash(key) modulus numSlots
loop
if slot[i] is not occupied or slot[i].key = key
return i
i := (i + 1) modulus numSlots
function lookup(key)
i := findSlot(key)
if slot[i] is occupied // key is in table
return slot[i].value
else // key is not in table
return not found
function set(key, value)
i := findSlot(key)
if slot[i].key = key
// (Key already in table. Update value.)
slot[i].value := value
else
// (Insert key and value in un-occupied slot.)
// (But first, make sure insert won't overload the table)
if the table is almost full
rebuild the table larger (note 1)
i := findSlot(key)
slot[i].key := key
slot[i].value := value
另一個展示開放定址技術的示例。所呈現的函式是轉換 Internet 協議地址的每個部分（4），其中 NOT 是按位 NOT，XOR 是按位 XOR，OR 是按位 OR，AND 是按位 AND，<< 和 >> 是左移和右移
// key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx
function ip(key parts)
j := 1
do
key := (key_2 << 2)
key := (key + (key_3 << 7))
key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j
key := key AND _prime_ // _prime_ is a prime number
j := (j+1)
while collision
return key
- 注意 1
- 重建表需要分配一個更大的陣列，並遞迴地使用 set 操作將舊陣列的所有元素插入到新的更大的陣列中。通常會 指數地 增加陣列大小，例如將舊陣列大小加倍。
function remove(key)
i := findSlot(key)
if slot[i] is unoccupied
return // key is not in the table
j := i
loop
j := (j+1) modulus numSlots
if slot[j] is unoccupied
exit loop
k := hash(slot[j].key) modulus numSlots
if (j > i and (k <= i or k > j)) or
(j < i and (k <= i and k > j)) (note 2)
slot[i] := slot[j]
i := j
mark slot[i] as unoccupied
- 注意 2
- 對於叢集中的所有記錄，它們的自然雜湊位置與其當前位置之間不能有空槽（否則查詢將在找到記錄之前終止）。在虛擬碼的這一步，i 是一個空槽，它可能會使叢集中後續記錄的此屬性無效。j 是這樣後續記錄。k 是原始雜湊，如果不存在衝突，則位於j 的記錄將在雜湊表中自然落地。此測試詢問位於j 的記錄是否相對於叢集的必需屬性（現在i 是空的）處於無效位置。
另一種刪除技術是簡單地將該槽標記為已刪除。但是，這最終需要重建表以簡單地刪除已刪除的記錄。上述方法提供 O(1) 更新和刪除現有記錄，如果表的最高水位標記增長，則偶爾會重建。
上述 O(1) 刪除方法僅在使用單槽步長的線性探測雜湊表中才有可能。在需要在一個操作中刪除許多記錄的情況下，標記要刪除的槽位並稍後重建可能更高效。
與開放定址相比，鏈式雜湊表具有以下優點
- 它們易於有效地實現，並且只需要基本的資料結構。
- 從編寫合適的雜湊函式的角度來看，鏈式雜湊表對叢集不敏感，只需要最小化衝突。開放定址依賴於更好的雜湊函式來避免叢集。如果新手程式設計師可以新增自己的雜湊函式，這一點尤其重要，但即使是經驗豐富的程式設計師也可能被意外的叢集效應所困擾。
- 它們的效能下降更加平緩。儘管隨著表的填充，鏈條越來越長，但鏈式雜湊表不會“填滿”，並且不會像開放定址的接近滿載表那樣出現查詢時間突然增加。（參見右側）
- 如果雜湊表儲存大型記錄，每條記錄大約 5 個或更多個字，則鏈式定址比開放定址使用更少的記憶體。
- 如果雜湊表是稀疏的（即，它有一個包含許多空陣列槽的大陣列），由於其外部儲存，即使對於每條記錄只有 2 到 4 個字的小記錄，鏈式定址也比開放定址使用更少的記憶體。
對於小型記錄大小（幾個字或更少），與鏈式定址相比，就地開放定址的優點是
- 它們比鏈式定址更節省空間，因為它們不需要儲存任何指標或在雜湊表之外分配任何額外的空間。簡單的連結串列每個元素需要一個字的開銷。
- 插入避免了記憶體分配的時間開銷，甚至可以在沒有記憶體分配器的情況下實現。
- 由於它使用內部儲存，開放定址避免了鏈式定址的外部儲存所需的額外間接定址。它還具有更好的 區域性性，特別是對於線性探測。對於小型記錄大小，這些因素可以產生比鏈式定址更好的效能，特別是對於查詢。
- 它們更容易 序列化，因為它們不使用指標。
另一方面，對於大型元素來說，普通的開放定址是一個糟糕的選擇，因為這些元素會填滿整個快取行（抵消了快取優勢），並且在大型空表槽位上浪費了大量空間。如果開放定址表只儲存對元素的引用（外部儲存），它即使對於大型記錄也使用與鏈式定址相當的空間，但會失去其速度優勢。
總的來說，開放定址更適合用於具有小型記錄的雜湊表，這些記錄可以儲存在表中（內部儲存）並適合快取行。它們特別適合於一個字或更少的元素。在預期表具有高負載因子、記錄很大或資料大小可變的情況下，鏈式雜湊表通常執行得一樣好或更好。
最終，明智地使用任何型別的雜湊表演算法通常都足夠快；並且在雜湊表程式碼中花費的計算百分比很低。記憶體使用量很少被認為是過度的。因此，在大多數情況下，這些演算法之間的差異是微不足道的，其他考慮因素通常會起作用。
合併雜湊是鏈式定址和開放定址的混合體，它在表本身內連結節點鏈。與開放定址一樣，它比鏈式定址實現了更高的空間利用率和（略微降低的）快取優勢。與鏈式定址一樣，它不會出現叢集效應；實際上，表可以高效地填充到很高的密度。與鏈式定址不同，它不能具有超過表槽的元素。
如果所有將要使用的鍵都事先已知，並且沒有更多適合雜湊表的鍵，則可以使用 完美雜湊 來建立完美雜湊表，其中不會發生衝突。如果使用 最小完美雜湊，雜湊表中的每個位置也可以使用。
完美雜湊提供了一個雜湊表，其中在最壞情況下進行查詢的時間是恆定的。這與鏈式定址和開放定址方法形成對比，在這些方法中，查詢時間平均較低，但可能任意大。存在用於在插入鍵時維護完美雜湊函式的方法，稱為 動態完美雜湊。另一種更簡單的替代方案，它也提供了最壞情況下的恆定查詢時間，是 布穀鳥雜湊。
對於衝突，最簡單的解決方案可能是用新值替換已經存在於槽中的值，或者不太常見的是，刪除要插入的記錄。在以後的搜尋中，這可能會導致搜尋無法找到已插入的記錄。此技術對於實現快取特別有用。
與之類似的更節省空間的解決方案是使用 位陣列（一個一位欄位陣列）作為我們的表。最初所有位都設定為零，當我們插入一個鍵時，我們將相應的位設定為一。不會出現假陰性，但可能會出現 假陽性，因為如果搜尋找到 1 位，它將聲稱該值已找到，即使它只是另一個碰巧雜湊到同一個陣列槽中的值。實際上，這樣的雜湊表只是一個特定的 布隆過濾器 型別。
使用良好的雜湊函式，雜湊表通常可以包含大約 70%–80% 的表槽數，並且仍然可以正常執行。根據衝突解決機制的不同，效能可能會隨著新增更多元素而逐漸或急劇下降。為了解決這個問題，當負載因子超過某個閾值時，我們會分配一個新的、更大的表，並將原始表中的所有內容新增到這個新表中。例如，在 Java 的 HashMap 類中，預設負載因子閾值為 0.75。
這可能是一個非常昂貴的操作，而且它的必要性是雜湊表的一個缺點。實際上，一些天真的執行此操作的方法，例如每次新增新元素時將表擴大一個，會大幅降低效能，從而使雜湊表變得無用。但是，如果我們將表擴大某個固定百分比，例如 10% 或 100%，則可以使用 攤銷分析 來證明這些調整大小非常不頻繁，以至於每次查詢的平均時間仍然是恆定時間。為了瞭解這是為什麼，假設一個使用鏈式定址的雜湊表從最小大小 1 開始，並且每次填滿超過 100% 時都加倍。如果最終它包含 n 個元素，那麼對所有調整大小執行的總新增操作為
- 1 + 2 + 4 + ... + n = 2n - 1。
因為調整大小的成本構成一個 幾何級數，總成本為 O(n)。但我們還執行 n 次操作來新增最初的 n 個元素，因此新增 n 個元素（包含調整大小）的總時間為 O(n)，即每個元素的攤銷時間為 O(1)。
另一方面，一些雜湊表實現，特別是在 即時系統 中，無法承受一次性擴大雜湊表的價格，因為它可能會中斷時間敏感的操作。一個簡單的辦法是最初為預期元素數量分配足夠的儲存空間，並禁止新增太多元素。另一種有用但更佔記憶體的技術是逐步執行調整大小
- 分配新的雜湊表，但保留舊的雜湊表，並在查詢時檢查這兩個表。
- 每次執行插入時，將該元素新增到新表中，並將 k 個元素從舊錶移動到新表中。
- 當從舊錶中刪除所有元素後，釋放它。
為了確保在新的表本身需要擴大之前完全複製舊的表，在調整大小期間將表的尺寸增加至少 (k + 1)/k 倍是必要的。
線性雜湊 是一種允許增量雜湊表擴充套件的雜湊表演算法。它使用單個雜湊表實現，但具有兩種可能的查詢函式。
降低表格調整大小成本的另一種方法是選擇一種雜湊函式，以便在調整表格大小時，大多數值的雜湊值不會改變。這種方法稱為一致性雜湊，在基於磁碟和分散式雜湊中很普遍，因為在這些情況下，調整大小的成本非常高。
雜湊表將資料儲存在偽隨機位置，因此以排序方式訪問資料是一個非常耗時的操作。其他資料結構，例如自平衡二叉搜尋樹，通常執行速度更慢（因為它們的查詢時間為 O(log n)），而且比雜湊表更復雜，但始終維護著排序的資料結構。參見雜湊表和自平衡二叉搜尋樹的比較。
雖然雜湊表查詢平均使用常數時間，但花費的時間可能很長。評估一個好的雜湊函式可能是一個緩慢的操作。特別是，如果可以使用簡單的陣列索引，這通常更快。
雜湊表通常表現出較差的區域性性，也就是說，要訪問的資料在記憶體中看似隨機分佈。由於雜湊表會導致訪問模式四處跳躍，這會導致微處理器快取未命中，從而導致長時間延遲。緊湊的資料結構（如陣列），使用線性搜尋進行搜尋，如果表相對較小，並且金鑰比較起來很便宜，例如使用簡單的整數金鑰，則可能更快。根據摩爾定律，快取大小呈指數級增長，因此被認為“小”的可能也在增加。最佳效能點因系統而異；例如，在Parrot上的一個試驗表明，它的雜湊表在除最瑣碎的情況（一到三個條目）之外的所有情況下都優於線性搜尋。
更重要的是，雜湊表更難編寫和使用，而且容易出錯。雜湊表要求為每種金鑰型別設計一個有效的雜湊函式，在許多情況下，這比為自平衡二叉搜尋樹所需的對照函式更難，也更耗時。在開放定址雜湊表中，建立糟糕的雜湊函式甚至更容易。
此外，在某些應用程式中，一個瞭解雜湊函式的駭客可能能夠向雜湊提供資訊，透過導致過度衝突來建立最壞情況的行為，從而導致非常糟糕的效能（即，拒絕服務攻擊）。在關鍵應用程式中，可以使用通用雜湊，或者可能更適合使用具有更好最壞情況保證的資料結構。有關詳細資訊，請參閱 Crosby 和 Wallach 的透過演算法複雜性攻擊實現拒絕服務。
可擴充套件雜湊和線性雜湊是雜湊演算法，它們用於資料庫演算法的上下文中，例如索引檔案結構，甚至資料庫的主要檔案組織。通常，為了使搜尋對大型資料庫可擴充套件，搜尋時間應與 log N 或接近常數成正比，其中 N 是要搜尋的記錄數。可以使用樹結構實現 log N 搜尋，因為扇出度和樹的短小與查詢記錄所需的步驟數相關，因此樹的高度是查詢記錄位置所需的磁碟訪問次數的最大值。但是，也使用雜湊表，因為磁碟訪問的成本可以用磁碟訪問單位來計算，並且該單位通常是一個數據塊。由於雜湊表在最佳情況下可以用一次或兩次訪問找到金鑰，因此雜湊表索引在檢索聯接操作期間的一組記錄時通常被認為更快，例如。
SELECT * from customer, orders where customer.cust_id = orders.cust_id and cust_id = X
例如，如果訂單對 cust_id 有一個雜湊索引，那麼找到包含與 cust_id = X 匹配的訂單記錄位置的塊需要常數時間。（雖然，如果訂單的值型別是訂單 ID 列表，那麼這樣更好，這樣雜湊金鑰對於每個訂單批次只有一個唯一的 cust_id，以避免不必要的衝突）。
可擴充套件雜湊和線性雜湊有一些相似之處：衝突被認為是不可避免的，並且是演算法的一部分，其中添加了衝突空間的塊或桶；需要傳統的良好雜湊函式範圍，但雜湊值透過動態地址函式轉換；在可擴充套件雜湊中，使用位掩碼遮蔽掉不需要的位，但該掩碼長度會週期性地增加一，使可用地址空間翻倍；同樣在可擴充套件雜湊中，有一個指向目錄地址空間的間接地址，目錄條目與另一個地址（指標）配對，該地址指向包含鍵值對的實際塊；目錄中的條目對應於位掩碼雜湊值（因此條目數等於最大位掩碼值 + 1，例如，一個 2 位位掩碼可以定址一個包含 00 01 10 11 的目錄，或者 3 + 1 = 4）。
在線性雜湊中，傳統的雜湊值也使用位掩碼進行掩碼，但如果生成的較小雜湊值低於“分割”變數，則原始雜湊值使用一個位長度更大的位掩碼進行掩碼，使生成的雜湊值定址最近新增的塊。分割變數在 0 和當前最大位掩碼值之間遞增，例如，一個 2 位的位掩碼，或者線上性雜湊的術語中，一個“級別”為 2，分割變數將在 0 到 3 之間。當分割變數達到 4 時，級別增加 1，因此在分割變數的下一輪中，它將在 0 到 7 之間，並在達到 8 時再次重置。
分割變數遞增地允許增加地址空間，因為添加了新塊；新增新塊的決定發生在插入鍵值時，並且鍵值溢位到鍵值雜湊到的特定塊。此溢位位置可能與分割變數指向的要分割的塊完全無關。然而，隨著時間的推移，預計在給定一個將條目均勻分佈在所有可定址塊中的良好隨機雜湊函式的情況下，實際需要分割的塊（因為它們已經溢位）會以迴圈方式輪流獲得它們的分割機會，因為分割值在 0-N 之間，其中 N 是 2 的 Level 次方的因子，Level 是每次分割變數達到 N 時增加的變數。
可擴充套件雜湊和線性雜湊都一次新增一個新塊。
在可擴充套件雜湊中，塊溢位（一個新的鍵值與 B 個其他鍵值衝突，其中 B 是塊的大小）透過檢查“本地”的位掩碼大小來處理，稱為“本地深度”，這是一個必須與塊一起儲存的屬性。目錄結構也具有一個深度，即“全域性深度”。如果本地深度小於全域性深度，則本地深度加 1，並將所有鍵值重新雜湊並透過現在更長一位的位掩碼進行傳遞，將它們放置在當前塊或另一個塊中。如果另一個塊恰好在目錄中查詢時是同一個塊，則新增一個新塊，並且指向另一個塊的目錄條目被設定為指向新塊。為什麼目錄中會有條目，其中兩個條目指向同一個塊？這是因為如果本地深度等於目錄的全域性深度，這意味著目錄的位掩碼沒有足夠的位來處理塊的位掩碼長度的增加，因此目錄必須增加其位掩碼長度，但這意味著目錄現在使可定址條目的數量翻倍。由於一半的可定址條目不存在，因此目錄只需將指標複製到新條目中，例如，如果目錄具有針對 00、01、10、11 的條目，或者一個 2 位掩碼，並且它變成一個 3 位掩碼，那麼 000 001 010 011 100 101 110 111 成為新的條目，00 的塊地址轉到 000 和 001；01 的指標轉到 010 和 011，10 轉到 100 和 101 等等。因此，這會產生兩種目錄條目指向同一個塊的情況。雖然將要溢位的塊現在可以透過將第二個指標重定向到一個新新增的塊來新增一個新塊，但其他原始塊將有兩個指向它們的指標。當輪到它們分割時，該演算法將檢查本地深度與全域性深度，這次發現本地深度更小，因此不需要目錄分割，只需新增一個新塊，並將第二個目錄指標從指向先前塊更改為指向新塊。
在線性雜湊中，新增一個具有相似雜湊值的塊不會在塊溢位時立即發生，因此會建立一個溢位塊並將其附加到溢位塊。但是，塊溢位表明需要更多空間，這可以透過分割由“split”變數指向的塊來實現，該變數最初為零，因此最初指向塊零。分割是透過獲取分割塊中所有的鍵值對以及它的溢位塊（如果有），並再次雜湊鍵，但使用長度為當前級別 + 1 的位掩碼來實現的。這將導致兩個塊地址，一些將是舊的塊編號，而另一些將是
a2 = old block number + ( N times 2 ^ (level) )
- 原理
令 m = N 乘以 2 的 level 次方；如果 h 是原始的雜湊值，並且舊的塊編號 = h 模 m，現在新的塊編號是 h 模 (m * 2)，因為 m * 2 = N 乘以 2 的 (level+1) 次方，那麼新的塊編號要麼是 h 模 m（如果 (h / m) 是偶數，所以將 h/m 除以 2 會留下零餘數，因此不會改變餘數），要麼是 (h 模 m) + m（因為 h / m 是奇數，將 h / m 除以 2 會留下 m 的餘數，加上原始餘數）。（相同的原理適用於可擴充套件雜湊深度遞增）。
如上所述，一個新的塊將使用編號 a2 建立，該編號通常會出現在之前的 a2 值 + 1 處。完成此操作後，split 變數會遞增，以便下一個 a2 值將再次是舊的 a2 + 1。這樣，每個塊最終都會被 split 變數覆蓋，所以每個塊都會被預先重新雜湊到額外的空間，而新的塊會增量新增。不再需要的溢位塊會被丟棄，如果需要，則用於後面的垃圾回收，或者透過連結放到可用的空閒塊列表中。
當 split 變數達到 (N 乘以 2 的 level 次方) 時，level 會遞增，而 split 變數會被重置為零。在下一輪中，split 變數現在將從零遍歷到 (N 乘以 2 的 (舊的 level + 1) 次方)，這正是上一輪開始時的塊數，但包含了上一輪建立的所有塊。
可以看出，可擴充套件雜湊需要空間來儲存一個目錄，該目錄的大小可以翻倍。
由於兩種演算法的空間都以每次一個塊的速度增加，如果塊具有已知的最大尺寸或固定尺寸，那麼將塊對映為按順序附加到檔案的塊是直截了當的。
在可擴充套件雜湊中，將目錄儲存為一個單獨的檔案是合乎邏輯的，因為可以透過將目錄檔案附加到末尾來適應翻倍。除了將塊附加到其末尾之外，單獨的塊檔案不需要更改。
線性雜湊的頭部資訊的大小不會增加：基本上只需要記錄 N、level 和 split 的值，因此可以將它們作為頭部合併到固定塊大小的線性雜湊儲存檔案中。
但是，線性雜湊需要空間來儲存溢位塊，這最好儲存在另一個檔案中，否則線上性雜湊檔案中定址塊不會像將塊編號乘以塊大小然後加上 N、level 和 split 的空間那樣直截了當。
在下一節中，將提供線性雜湊在 Java 中的完整示例，使用線性雜湊的記憶體中實現，以及將塊作為檔案管理到檔案目錄中的程式碼，整個檔案目錄的內容代表持久化的線性雜湊結構。
雖然許多程式語言已經提供了雜湊表的功能，[2]但仍有幾個值得一提的獨立實現。
- Google Sparse Hash Google SparseHash 專案包含幾個在 Google 使用的雜湊對映實現，具有不同的效能特徵，包括一個針對空間最佳化的實現和一個針對速度最佳化的實現。記憶體最佳化的實現非常節省記憶體，每個條目只有 2 位的開銷。
- MCT 提供與 Google 的
dense_hash_map相似的雜湊表，但對包含的值沒有限制；它還具有異常安全性並支援 C++0x 功能。 - 許多執行時語言和/或標準庫使用雜湊表來實現它們對關聯陣列的支援，因為雜湊表的效率很高。
檔案-塊管理例程不存在，因此可以新增這些例程來使其成為資料庫雜湊索引的真實實現。
一個完整的頁面根據 (區域性深度) 位進行分割，首先透過收集所有指向完整頁面的目錄索引，根據 d 位是 0 還是 1 更新指標（對應於第一個和第二個新頁面），然後在雜湊每個鍵並使用每個雜湊的 d 位來檢視要分配到哪個頁面之後，重新載入所有鍵值對。每個新頁面的區域性深度比舊頁面的區域性深度大 1，以便下次分割時可以使用下一個 d 位。
PAGE_SZ = 20
class Page:
def __init__(self):
self.m = {}
self.d = 0
def full(self):
return len(self.m) > PAGE_SZ
def put(self,k,v):
self.m[k] = v
def get(self,k):
return self.m.get(k)
class EH:
def __init__(self):
self.gd = 0
p = Page()
self.pp= [p]
def get_page(self,k):
h = hash(k)
p = self.pp[ h & (( 1 << self.gd) -1)]
return p
def put(self, k, v):
p = self.get_page(k)
if p.full() and p.d == self.gd:
self.pp = self.pp + self.pp
self.gd += 1
if p.full() and p.d < self.gd:
p.put(k,v);
p1 = Page()
p2 = Page()
for k2 in p.m.keys():
v2 = p.m[k2]
h = k2.__hash__()
h = h & ((1 << self.gd) -1)
if (h | (1 << p.d) == h):
p2.put(k2,v2)
else:
p1.put(k2,v2)
l = []
for i in xrange(0, len(self.pp)):
if self.pp[i] == p:
l.append(i)
for i in l:
if (i | ( 1 << p.d) == i):
self.pp[i] = p2
else:
self.pp[i] = p1
p1.d = p.d + 1
p2.d = p1.d
else:
p.put(k, v)
def get(self, k):
p = self.get_page(k)
return p.get(k)
if __name__ == "__main__":
eh = EH()
N = 10000
l = []
for i in range(0,N):
l.append(i)
import random
random.shuffle(l)
for i in l:
eh.put(i,i)
print l
for i in range(0, N):
print eh.get(i)
對上述 Python 程式碼的直接 Java 翻譯，經過測試可以工作。
package ext_hashing;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class EH2<K, V> {
static class Page<K, V> {
static int PAGE_SZ = 20;
private Map<K, V> m = new HashMap<K, V>();
int d = 0;
boolean full() {
return m.size() > PAGE_SZ;
}
void put(K k, V v) {
m.put(k, v);
}
V get(K k) {
return m.get(k);
}
}
int gd = 0;
List<Page<K, V>> pp = new ArrayList<Page<K, V>>();
public EH2() {
pp.add(new Page<K, V>());
}
Page<K, V> getPage(K k) {
int h = k.hashCode();
Page<K, V> p = pp.get(h & ((1 << gd) - 1));
return p;
}
void put(K k, V v) {
Page<K, V> p = getPage(k);
if (p.full() && p.d == gd) {
List<Page<K, V>> pp2 = new ArrayList<EH2.Page<K, V>>(pp);
pp.addAll(pp2);
++gd;
}
if (p.full() && p.d < gd) {
p.put(k, v);
Page<K, V> p1, p2;
p1 = new Page<K, V>();
p2 = new Page<K, V>();
for (K k2 : p.m.keySet()) {
V v2 = p.m.get(k2);
int h = k2.hashCode() & ((1 << gd) - 1);
if ((h | (1 << p.d)) == h)
p2.put(k2, v2);
else
p1.put(k2, v2);
}
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < pp.size(); ++i)
if (pp.get(i) == p)
l.add(i);
for (int i : l)
if ((i | (1 << p.d)) == i)
pp.set(i, p2);
else
pp.set(i, p1);
p1.d = p.d + 1;
p2.d = p1.d;
} else
p.put(k, v);
}
public V get(K k) {
return getPage(k).get(k);
}
public static void main(String[] args) {
int N = 500000;
Random r = new Random();
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < N; ++i) {
l.add(i);
}
for (int i = 0; i < N; ++i) {
int j = r.nextInt(N);
int t = l.get(j);
l.set(j, l.get(i));
l.set(i, t);
}
EH2<Integer, Integer> eh = new EH2<Integer, Integer>();
for (int i = 0; i < N; ++i) {
eh.put(l.get(i), l.get(i));
}
for (int i = 0; i < N; ++i) {
System.out.printf("%d:%d , ", i, eh.get(i));
if (i % 10 == 0)
System.out.println();
}
}
}
（可用於任意大小的簡單資料庫索引，（幾乎？））
這段程式碼源於對更大 Java HashMap 的需求。最初，一個 Java HashMap 標準物件用作 Map 來索引一個類似堆的資料庫檔案（DBF 格式）。但後來，遇到一個檔案，其中包含如此多的記錄，以至於丟擲了 OutOfMemoryError，因此線性雜湊似乎是一種作為基於磁碟的索引方案使用的簡單演算法。
最初，線性雜湊是在 Java Map 介面後面實現的，主要是 put(k,v) 和 get(k,v) 方法。使用了泛型，以免過於關注鍵和值的細節。
自定義轉儲到 System.err 用於驗證塊是否正在建立、填充，以及溢位塊的數量是否如預期（數量 = 1）。所有這些都是在純記憶體中實現的。
後來，引入了標準的 Java 解耦，其中原始的 LHMap2 類接受事件監聽器，例如當需要一個塊時。然後，監聽器被實現為一個塊檔案管理器，只要在塊列表上遇到空塊就將塊載入到記憶體 LHMap2 物件的塊列表中，並檢查虛擬機器執行時空閒記憶體是否不足，並透過將塊儲存到磁碟檔案並然後主動呼叫系統垃圾收集器來使用基本的先到先出（FIFO）快取刪除演算法（而不是最近最少使用（LRU），也不是最不常使用）來刪除塊。
由於存在一個應用程式用例，即外部索引一個大型 DBF 表，因此該用例被用作演算法實現的主要測試工具。
package linearhashmap;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
/**
*
* @param <K>
* key type , must implement equals() and hashCode()
* @param <V>
* value type
*
*
*/
public class LHMap2<K, V> implements Map<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 3095071852466632996L;
/**
*
*/
public static interface BlockListener<K, V> {
public void blockRequested(int block, LHMap2<K, V> map);
}
List<BlockListener<K, V>> listeners = new ArrayList<BlockListener<K, V>>();
// int savedBlocks;
int N;
int level = 0;
int split = 0;
int blockSize;
long totalWrites = 0;
List<Block<K, V>> blockList = new ArrayList<Block<K, V>>();
public void addBlockListener(BlockListener<K, V> listener) {
listeners.add(listener);
}
void notifyBlockRequested(int block) {
for (BlockListener<K, V> l : listeners) {
l.blockRequested(block, this);
}
}
public LHMap2(int blockSize, int nStartingBlocks) {
this.blockSize = blockSize;
this.N = nStartingBlocks;
for (int i = 0; i < nStartingBlocks; ++i) {
addBlock();
}
Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
@Override
public void run() {
showStructure();
}
}));
}
public static class Block<K, V> implements Externalizable {
/**
*
*/
int j = 0;
Block<K, V> overflow = null;
LinkedList<K> keyList = new LinkedList<K>();
LinkedList<V> valueList = new LinkedList<V>();
transient private LHMap2<K, V> owner;
transient private Map<K, V> shadow = new TreeMap<K, V>();
private boolean changed = false;
private int size = 0;
public LHMap2<K, V> getOwner() {
return owner;
}
public void setOwner(LHMap2<K, V> owner) {
this.owner = owner;
Block<K, V> ov = overflow;
while (ov != null) {
overflow.setOwner(owner);
ov = ov.overflow;
}
}
public Block() {
super();
}
public Block(LHMap2<K, V> map) {
setOwner(map);
}
public V put(K k, V v) {
setChanged(true);
V v2 = replace(k, v);
if (v2 == null) {
++size;
if (keyList.size() == getOwner().blockSize) {
if (overflow == null) {
getOwner().blockOverflowed(this, k, v);
} else {
overflow.put(k, v);
}
} else {
keyList.addFirst(k);
valueList.addFirst(v);
}
}
return v2;
}
void setChanged(boolean b) {
changed = b;
}
public Map<K, V> drainToMap(Map<K, V> map) {
while (!keyList.isEmpty()) {
K k = keyList.removeLast();
V v = valueList.removeLast();
map.put(k, v);
}
if (overflow != null)
map = overflow.drainToMap(map);
garbageCollectionOverflow();
return map;
}
public void updateMap(Map<K, V> map) {
Iterator<K> ik = keyList.descendingIterator();
Iterator<V> iv = valueList.descendingIterator();
while (ik.hasNext() && iv.hasNext()) {
map.put(ik.next(), iv.next());
}
if (overflow != null)
overflow.updateMap(map);
}
private void garbageCollectionOverflow() {
if (overflow != null) {
overflow.garbageCollectionOverflow();
overflow = null;
}
}
public void addOverflowBucket() {
// assert overflow is needed
if (keyList.size() < getOwner().blockSize)
return;
if (overflow == null) {
overflow = new Block<K, V>(getOwner());
} else {
overflow.addOverflowBucket();
}
}
public V replace(K key, V v2) {
if (overflow != null) {
V v = overflow.replace(key, v2);
if (v != null)
return v;
}
Iterator<K> i = keyList.listIterator();
int j = 0;
while (i.hasNext()) {
if (key.equals(i.next())) {
V v = valueList.get(j);
if (v2 != null) {
valueList.set(j, v2);
}
return v;
}
++j;
}
return null;
}
public boolean isChanged() {
return changed;
}
@Override
public void readExternal(ObjectInput arg0) throws IOException,
ClassNotFoundException {
int sz = arg0.readInt();
for (int i = 0; i < sz; ++i) {
K k = (K) arg0.readObject();
V v = (V) arg0.readObject();
shadow.put(k, v);
}
}
public void loadFromShadow(LHMap2<K, V> owner) {
setOwner(owner);
Block<K, V> b = this;
for (K k : shadow.keySet()) {
if (b.keyList.size() == owner.blockSize) {
Block<K, V> overflow = new Block<K, V>(owner);
b.overflow = overflow;
b = overflow;
}
b.keyList.add(k);
b.valueList.add(shadow.get(k));
}
shadow.clear();
}
@Override
public void writeExternal(ObjectOutput arg0) throws IOException {
if (!changed)
return;
Map<K, V> map = new TreeMap<K, V>();
updateMap(map);
int sz = map.size();
arg0.writeInt(sz);
for (K k : map.keySet()) {
arg0.writeObject(k);
arg0.writeObject(map.get(k));
}
setChanged(false);
}
}
void init() {
for (int i = 0; i < N; ++i) {
addBlock();
}
}
/**
* @param hashValue
* @return a bucket number.
*/
int getDynamicHash(int hashValue) {
long unsignedHash = ((long) hashValue << 32) >>> 32;
// ^^ this long cast needed
int h = (int) (unsignedHash % (N << level));
// System.err.println("h = " + h);
if (h < split) {
h = (int) (unsignedHash % (N << (level + 1)));
// System.err.println("h < split, new h = " + h);
}
return h;
}
@Override
public V put(K k, V v) {
++totalWrites;
int h = getDynamicHash(k.hashCode());
Block<K, V> b = getBlock(h);
b.put(k, v);
return v;
}
public long getTotalWrites() {
return totalWrites;
}
private Block<K, V> getBlock(int h) {
notifyBlockRequested(h);
return blockList.get(h);
}
void blockOverflowed(Block<K, V> b, K k, V v) {
splitNextBucket();
b.addOverflowBucket();
b.put(k, v);
}
private void splitNextBucket() {
Block<K, V> b = getBlock(split);
TreeMap<K, V> map = new TreeMap<K, V>();
b.drainToMap(map);
addBlock();
System.err.printf("split N LEVEL %d %d %d \n", split, N, level);
if (++split >= (N << level)) {
++level;
split = 0;
}
for (K k : map.keySet()) {
V v = map.get(k);
int h = getDynamicHash(k.hashCode());
System.err.println(h + " ");
Block<K, V> b2 = getBlock(h);
b2.put(k, v);
}
}
private Block<K, V> addBlock() {
Block<K, V> b = new Block<K, V>(this);
blockList.add(b);
return b;
}
@Override
public void clear() {
blockList = new ArrayList<Block<K, V>>();
split = 0;
level = 0;
totalWrites = 0;// savedBlocks = 0;
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
return values().contains(value);
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
TreeSet<Map.Entry<K, V>> set = new TreeSet<Map.Entry<K, V>>();
Set<K> kk = keySet();
for (K k : kk) {
final K k2 = k;
set.add(new Entry<K, V>() {
@Override
public K getKey() {
return k2;
}
@Override
public V getValue() {
return get(k2);
}
@Override
public V setValue(V value) {
return put(k2, value);
}
});
}
return set;
}
@Override
public V get(Object key) {
int h = getDynamicHash(key.hashCode());
Block<K, V> b = getBlock(h);
return b.replace((K) key, null);
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public Set<K> keySet() {
TreeSet<K> kk = new TreeSet<K>();
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
kk.addAll(b.keyList);
Block<K, V> ov = b.overflow;
while (ov != null) {
kk.addAll(ov.keyList);
ov = ov.overflow;
}
}
return kk;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (K k : m.keySet()) {
put(k, m.get(k));
}
}
@Override
public V remove(Object key) {
return null;
}
@Override
public int size() {
long sz = longSize();
return (int) (sz > Integer.MAX_VALUE ? Integer.MAX_VALUE
: sz);
}
public long longSize() {
long sz = 0;
for (Block<K, V> b : blockList) {
Block<K, V> b1 = b;
while (b1 != null) {
sz += b1.size;
b1 = b.overflow;
}
}
return sz;
}
@Override
public Collection<V> values() {
ArrayList<V> list = new ArrayList<V>();
Set<K> kk = keySet();
for (K k : kk) {
list.add(get(k));
}
return list;
}
private void showStructure() {
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
Block<K, V> ov = b.overflow;
int k = 0;
while (ov != null) {
ov = ov.overflow;
++k;
}
System.out.println("Block " + i + " size " + b.keyList.size()
+ " overflow blocks = " + k);
}
}
}
在此實現中，每個塊都是一個檔案，因為塊在這裡是可變大小的，以適應泛型和可變大小的鍵值對，而溢位塊是概念上的，而不是實際的，因為在磁碟儲存上，塊的內容及其溢位桶（如果有）的內容在此實現中被儲存為交替的鍵和值的列表。在 Block 資料類中實現 Externalizable 介面，使用標準的 Java 自定義物件持久化方法，使用儲存和載入到物件流的方法。
package linearhashmap;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Random;
/**
* This class manages the LHMap2 class block disk swapping, and saves and load an instance of the LHMap2 class.
* It has been used to externally index a legacy file based database of 100,000 record master table, and 1,000,000 record
* sized child tables, and accounts for heap space available in the java virtual machine, so that OutOfMemory errors
* are avoided when the heap space is low by putting blocks back on files, and garbage collecting them.
* The main performance bottleneck appeared when loading a million record table for an index , on initial creation
* of the index.
* @author doctor
*
* @param <K>
* @param <V>
*/
public class LHMap2BlockFileManager<K, V> implements
LHMap2.BlockListener<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 2615265603397988894L;
LHMap2BlockFileManagerData data = new LHMap2BlockFileManagerData(
new byte[10000], new Random(), 0, new ArrayList<Integer>(), 0);
public LHMap2BlockFileManager(File baseDir, String name, int maxBlocks,
double unloadRatio) {
data.home = new File(baseDir, name);
if (!data.home.exists())
data.home.mkdir();
this.data.maxBlocks = maxBlocks;
this.data.unloadRatio = unloadRatio;
}
@Override
public void blockRequested(int block, LHMap2<K, V> map) {
LHMap2.Block<K, V> b = map.blockList.get(block);
if (b == null) {
int tries = 3;
File f = new File(data.home, Integer.toString(block));
do {
if (f.exists())
break;
if (!f.exists()) {
if (--tries >= 0)
fatal(block);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
} while (true);
try {
ByteArrayInputStream bis = new ByteArrayInputStream(data.buf);
FileInputStream fis = new FileInputStream(f);
int sz = fis.read(data.buf);
fis.close();
addByteStats(sz);
ObjectInputStream ois = new ObjectInputStream(bis);
b = new LHMap2.Block<K, V>();
b.readExternal(ois);
ois.close();
b.loadFromShadow(map);
map.blockList.set(block, b);
--data.retired;
} catch (FileNotFoundException e) {
e.printStackTrace();
fatal(block);
} catch (IOException e) {
e.printStackTrace();
fatal(block);
} catch (ClassNotFoundException e) {
e.printStackTrace();
fatal(block);
}
}
int size = map.blockList.size();
try {
long freeMemory = Runtime.getRuntime().freeMemory();
long limitMemory = (long) (data.avgBlockSize * data.unloadRatio * size);
if (block % 30 == 0)
System.err.println("free memory =" + freeMemory + " limit "
+ limitMemory);
if (map.split % 20 == 19) {
// this is just to add statistics before really needing to retire
retireRandomBlock(map, block);
++data.retired;
} else if (freeMemory < limitMemory) {
for (int i = 0; i < size / 4; ++i) {
retireRandomBlock(map, block);
++data.retired;
}
System.runFinalization();
System.gc();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
private void addByteStats(int sz) {
++data.avgCount;
data.avgBlockSize = (int) ((data.avgBlockSize
* (data.avgCount - 1) + sz) / data.avgCount);
}
public void retireRandomBlock(LHMap2<K, V> map, int notThisOne)
throws FileNotFoundException, IOException {
int pick = 0;
int size = map.blockList.size();
LHMap2.Block<K, V> b = null;
for (pick = 0; pick < size
&& (pick == notThisOne || (b = map.blockList.get(pick)) == null); ++pick)
;
if (pick < size)
retireOneBlock(map, pick, b);
}
private void retireOneBlock(LHMap2<K, V> map, int pick, LHMap2.Block<K, V> b)
throws IOException, FileNotFoundException {
if (b == null)
return;
if (b.isChanged()) {
// System.err.println("Retiring " + pick);
File f = new File(data.home, Integer.toString(pick));
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(bos);
b.writeExternal(oos);
oos.flush();
oos.close();
FileOutputStream fos = new FileOutputStream(f);
byte[] bb = bos.toByteArray();
fos.write(bb);
fos.flush();
fos.close();
if (bb.length > data.buf.length) {
data.buf = bb;
}
}
map.blockList.set(pick, null);
b = null;
}
private void fatal(int block) {
Exception e = new Exception();
try {
throw e;
} catch (Exception e2) {
e2.printStackTrace();
}
System.err.println("block " + block
+ " requested and it is not in blocklist and not a file");
for (int i : data.retirees) {
System.err.print(i + " ");
}
System.err.println(" were retired");
System.exit(-2);
}
public static boolean metaExists(File indexDir, String name) {
File home = new File(indexDir, name);
return new File(home, "LinearMap2").exists();
}
public static <K, V> LHMap2<K, V> load(File baseDir, String name)
throws FileNotFoundException, IOException, ClassNotFoundException {
File home = new File(baseDir, name);
File f2 = new File(home, "LinearMap2");
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(f2));
LHMap2<K, V> map = (LHMap2<K, V>) ois.readObject();
ois.close();
loadBlocks(map);
return map;
}
private static <K, V> void loadBlocks(LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(map);
int size = map.blockList.size();
for (int i = 0; i < size; ++i) {
mgr.blockRequested(i, map);
}
}
public static <K, V> LHMap2BlockFileManager<K, V> getBlockManagerListener(
LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = (LHMap2BlockFileManager<K, V>) map.listeners
.get(0);
return mgr;
}
public static void save(File indexDir, String name,
LHMap2<?, ?> offsetMap) throws FileNotFoundException, IOException {
retireAllBlocks(offsetMap);
File home = new File(indexDir, name);
File f2 = new File(home, "LinearMap2");
ObjectOutputStream oos = new ObjectOutputStream(
new FileOutputStream(f2));
oos.writeObject(offsetMap);
oos.close();
}
private static <K, V> void retireAllBlocks(LHMap2<K, V> offsetMap)
throws FileNotFoundException, IOException {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(offsetMap);
int sz = offsetMap.blockList.size();
for (int i = 0; i < sz; ++i) {
LHMap2.Block<K, V> b = offsetMap.blockList.get(i);
// offsetMap.blockList.set(i, null); // mark for reloading as block
// destroyed after writing
if (b != null) {
mgr.retireOneBlock(offsetMap, i, b);
}
}
}
}
package linearhashmap;
import java.io.File;
import java.io.Serializable;
import java.util.List;
import java.util.Random;
public class LHMap2BlockFileManagerData implements Serializable{
/**
*
*/
private static final long serialVersionUID = 1L;
public byte[] buf;
public Random r;
public File baseDir;
public File home;
public int maxBlocks;
public int retired;
public double unloadRatio;
public List<Integer> retirees;
public int avgBlockSize;
public long avgCount;
public LHMap2BlockFileManagerData(byte[] buf, Random r, int retired,
List<Integer> retirees, long avgCount) {
this.buf = buf;
this.r = r;
this.retired = retired;
this.retirees = retirees;
this.avgCount = avgCount;
}
}
- ↑ 最簡單的雜湊表方案 - “線性探測開放定址法”，“鏈地址法”等 - 在最壞情況下具有 O(n) 的查詢時間，在這種情況下，大多數鍵（意外或惡意地）“碰撞” - 大多數鍵被對映到一個或幾個桶。其他雜湊表方案 - “布穀鳥雜湊”，“動態完美雜湊”等 - 即使在最壞情況下也能保證 O(1) 的查詢時間。當插入一個新鍵時，這些方案會在需要時改變其雜湊函式以避免衝突。
- ↑ 維基百科：程式語言比較（對映） 顯示了多少程式語言提供了雜湊表功能。