哈希表演算法深度解析：從原理到實戰應用

在資料查找的領域中，我們常見的方法主要有三類：針對空間連續的資料可採用二分查找；空間不連續時可使用排序二叉樹；但當資料量龐大且空間不連續時，上述兩種方法便顯得力不從心。此時，哈希表憑藉陣列易於定位、鏈表易於增刪的雙重優勢，成為最佳選擇。

什麼是 Hash？

Hash，中文常譯為「散列」，也有直接音譯為「哈希」。簡單來說，它是一種將任意長度的輸入（預映射，pre-image）透過散列演算法轉換為固定長度輸出（散列值）的函數。這是一種壓縮映射，散列值空間通常遠小於輸入空間，不同輸入可能產生相同輸出（碰撞），且無法從散列值唯一反推輸入值。在資訊安全領域，Hash 常用於加密演算法，將不同長度資訊轉換為 128 位的雜亂編碼。從資料結構角度看，Hash 建立了資料內容與儲存地址之間的映射關係。

哈希表的經典實現：拉鏈法

陣列尋址容易但插入刪除困難；鏈表插入刪除容易但尋址困難。哈希表結合兩者優點，最常用的實現是「拉鏈法」，可理解為「鏈表的陣列」。陣列每個成員包含一個指標，指向一條鏈表的頭部。根據元素特徵（透過散列函數）將元素分配到不同鏈表，查找時先定位鏈表，再在鏈表中尋找目標元素。

三種常見的散列函數

1. 除法散列法

最直觀的方法，公式為 index = value % 16。求模運算本質上是除法運算，故名。圖 1 即使用此法。

2. 平方散列法

乘法比除法快，公式為 index = (value * value) >> 28（右移 28 位，相當於除以 2^28）。若數值分佈均勻效果不錯，但某些數據（如圖 1 的元素）算出的 index 全為 0，效果極差。雖然 value * value 可能溢出，但此處不關心乘積結果，只取高位作為 index，故溢出不影響正確性。

3. 斐波那契散列法

平方法缺點明顯，能否找到理想乘數？答案是肯定的，這與黃金分割法則及斐波那契數列相關：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946…
對 32 位整數，理想乘數為 2654435769，公式為：
index = (value * 2654435769) >> 28
使用此法後，元素分佈明顯優於取模法（見圖 2）。

適用範圍與核心要點

• 適用範圍：快速查找、刪除的基礎資料結構，通常要求總資料量可放入記憶體。
• 核心要點：Hash 函數選擇（針對字串、整數、排列等）；碰撞處理——開放散列（拉鏈法）與閉合散列（開放定址法）。

擴展：d-left hashing

以 2-left hashing 為例：將哈希表分為等長兩半 T1、T2，各配一個哈希函數 h1、h2。存儲新 key 時同時計算兩個位置，選擇負載較小的一側存放；查找時需雙向查詢。此策略有效平衡負載，提升性能。

本文出自「驛落黃昏」博客，轉載請保留出處：https://yiluohuanghun.blog.51cto.com/3407300/1258577