速度與碰撞的權衡 (Trade-off between Speed and Collision Rate)

不使用加密哈希函數，我們只關注 速度快 和 碰撞率低 的哈希函數。

常數因子很重要 (Constant Factors Matter) ：在處理大量數據時，即使O(1)操作的常數因子差異也會導致巨大的性能差距和金錢成本。

? 靜態哈希方案 (Static Hashing Schemes)：靜態哈希方案的哈希表大小是固定的。如果存儲空間不足，DBMS必須從頭開始重建一個更大的哈希表（通常是原大小的兩倍），這會 非常昂貴 。

線性探測哈希 (Linear Probe Hashing)

實現原理/方法 ：哈希函數計算出槽位后，如果該槽位已被占用，則 線性掃描 到下一個空閑槽位進行插入。查找時，也從哈希到的槽位開始線性掃描，直到找到目標鍵或遇到空槽。為了進行驗證，每個槽位必須存儲原始鍵。

? 優點 ： 最基本也通常是最快 的哈希方案，因為它具有良好的緩存局部性，且分支預測失敗較少。

? 代價 ：刪除操作很復雜。如果直接刪除，會中斷后續鍵的查找鏈； 墓碑標記 (Tombstone) 復雜，在刪除的槽位放置一個“墓碑”標記，表示該槽位邏輯上為空但物理上占用，查找時會跳過此標記繼續掃描。浪費空間，需要后續垃圾回收。將后續的鍵向前移動以填充空位，代價是移動后的鍵可能不再位于其最佳哈希位置的下游，導致查找失敗。

羅賓漢哈希 (Robin Hood Hashing)

實現原理/方法 ：線性探測哈希的一種變體。每個鍵都會記錄它 距離其理想哈希位置的“跳躍”次數 （即貧富程度）。在插入時，如果新鍵比當前占據該槽位的鍵“更貧窮”（即距離其理想位置更遠），新鍵會 “偷走” 這個槽位，而被“偷走”的鍵則會被重新插入到哈希表中。

? 優點 ：旨在 平衡整個哈希表中鍵的距離 ，最小化任何鍵距離其理想位置的最大距離。

? 代價 ： 寫入/插入更昂貴 ，在實踐中，對于內存中的數據結構，通常 比線性探測哈希慢 。

布谷鳥哈希 (Cuckoo Hashing)

實現原理/方法 ：使用 多個哈希表 （通常是兩個）和 不同的哈希函數種子 。插入時，嘗試在每個哈希表中找到一個空閑槽位。如果所有可能的槽位都被占用，則 驅逐 其中一個哈希表中的現有元素，并將其重新哈希以找到新位置，這可能導致連鎖驅逐（像布谷鳥占巢）。

? 優點 ： 查找和刪除總是O(1) ，因為只需檢查每個哈希表中的一個特定位置。

? 代價 ： 插入可能昂貴 ，可能導致“乒乓”效應或連鎖驅逐，甚至陷入 循環 （無限循環）；如果檢測到循環或哈希表變得太滿，就需要 重建所有哈希表 ，使用新的哈希函數種子或更大的表。

? 動態哈希方案 (Dynamic Hashing Schemes)，能夠在需要時 按需調整大小 ，而無需重建整個哈希表。

鏈式哈希 (Chained Hashing / Bucket Hashing)

實現原理/方法 ：每個主槽位都維護一個 桶（bucket）的鏈表 。所有哈希到同一個槽位的鍵都放在該鏈表的桶中。當桶滿時，就 分配并鏈接一個新的桶 。

? 優點 ：實現簡單，且通過不斷添加新桶可以“無限”增長。易于實現線程安全，只需對槽位或單個頁面進行加鎖。

? 代價 ：如果所有鍵都映射到同一個桶鏈，哈希表可能會退化為 O(n)的線性搜索 ，性能顯著下降；可能存在空間浪費，尤其是有許多短鏈時。

可擴展哈希 (Extendible Hashing)

實現原理/方法 ：鏈式哈希的改進變體，它會 分裂桶 而不是讓鏈無限增長。維護一個 全局計數器（global depth） ，指示哈希值需要檢查的位數，以確定在槽數組中的位置。

每個桶也有一個 局部計數器（local depth） 。

當桶溢出時，會觸發分裂。如果局部深度小于全局深度，則重新分配桶中的元素到新的桶中。如果局部深度等于全局深度，則 全局深度會增加，槽數組的大小會加倍 （這個操作是廉價的，因為只是指針數組），然后重新分配桶中的元素。

? 優點 ： 數據移動被局部化 到溢出的桶鏈，其他桶不受影響。槽數組的加倍操作相對廉價，因為它只涉及指針數組的更新，不涉及數據的物理移動。

? 代價 ：槽數組加倍時，需要對整個槽數組 獲取全局鎖 ，這可能成為并發訪問的瓶頸；刪除操作比較復雜，可能需要合并桶并逆向分裂過程

線性哈希 (Linear Hashing)

實現原理/方法 ：維護一個 分裂指針 (split pointer) ，它跟蹤下一個要分裂的桶，而不管哪個桶實際溢出。使用 多個哈希函數 （例如 key % n 和 key % 2n）。

當任何桶溢出時， 分裂指針指向的桶 會被分裂（即使它不是溢出的那個），將其內容重新分配到新的槽位，并添加一個新的哈希函數（key % 2n）。

查詢時，首先使用第一個哈希函數。如果映射到的槽位在分裂指針 之上 （即已被分裂），則需要使用第二個哈希函數來找到實際位置。

? 優點 ：將 調整大小的操作局部化 到分裂指針所指向的桶，避免了對整個哈希表進行全局加鎖，從而減少了并發瓶頸。

? 代價 ：由于分裂的桶不一定是溢出的桶，這可能導致 臨時出現更多的溢出鏈 ；刪除操作很復雜，可能涉及分裂指針的逆向移動和內存回收。

? 線性探測哈希 (Linear Probe Hashing)