雜湊表

雜湊表（Hash table），是根據鍵（Key）而直接查詢在記憶體儲存位置的資料結構。也就是說，它通過計算出一個鍵值的函式，將所需查詢的資料對映到表中一個位置來讓人查詢，這加快了尋找速度。這個對映函式稱做雜湊函式，存放記錄的陣列稱做雜湊表。

一個通俗的例子是，為了尋找電話簿中某人的號碼，可以建立一個按照人名首字母順序排列的表（即建立人名 $x$ 到首字母 $F(x)$ 的一個函式關係），在首字母為W的表中尋找「王」姓的電話號碼，顯然比直接尋找就要快得多。這裡使用人名作為關鍵字，「取首字母」是這個例子中雜湊函式的函式法則 $F()$ ，存放首字母的表對應雜湊表。關鍵字和函式法則理論上可以任意確定。

可以將雜湊表理解為一串按順序放的陣列，陣列的下標是從key經過計算得出，陣列每個位置存放 value。這裡有很多將key轉換為下標的函式，比如取模，md5等。可以在雜湊表視覺化頁面直觀操作，理解這裡的資料結構。

基本概念

若關鍵字為 $k$ ，則其值存放在 $f(k)$ 的儲存位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係 $f$ 為雜湊函式，按這個思想建立的表為雜湊表。

對不同的關鍵字可能得到同一雜湊位址，即 $k_{1}\neq k_{2}$ ，而 $f(k_{1})=f(k_{2})$ ，這種現象稱為衝突（英語：Collision）。具有相同函式值的關鍵字對該雜湊函式來說稱做同義詞。綜上所述，根據雜湊函式 $f(k)$ 和處理衝突的方法將一組關鍵字對映到一個有限的連續的位址集（區間）上，並以關鍵字在位址集中的「像」作為記錄在表中的儲存位置，這種表便稱為雜湊表，這一對映過程稱為雜湊造表或雜湊，所得的儲存位置稱雜湊位址。

若對於關鍵字集合中的任一個關鍵字，經雜湊函式映象到位址集合中任何一個位址的概率是相等的，則稱此類雜湊函式為均勻雜湊函式（Uniform Hash function），這就使關鍵字經過雜湊函式得到一個「隨機的位址」，從而減少衝突。

構造雜湊函式

雜湊函式能使對一個資料序列的查詢過程更加迅速有效，通過雜湊函式，資料元素將被更快定位。

直接定址法：取關鍵字或關鍵字的某個線性函式值為雜湊位址。即 $hash(k)=k$ 或 $hash(k)=a\cdot k+b$ ，其中 $a\,b$ 為常數（這種雜湊函式叫做自身函式）
數字分析法：假設關鍵字是以r為基的數，並且雜湊表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成雜湊位址。
平方取中法：取關鍵字平方後的中間幾位為雜湊位址。通常在選定雜湊函式時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關，由此使隨機分布的關鍵字得到的雜湊位址也是隨機的。取的位數由表長決定。
摺疊法：將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為雜湊位址。
亂數法
除留餘數法：取關鍵字被某個不大於雜湊表表長m的數p除後所得的餘數為雜湊位址。即 $hash(k)=k\,{\bmod {\,}}p$ , $p\leq m$ 。不僅可以對關鍵字直接取模，也可在摺疊法、平方取中法等運算之後取模。對p的選擇很重要，一般取素數或m，若p選擇不好，容易產生衝突。

處理衝突

為了知道衝突產生的相同雜湊函式位址所對應的關鍵字，必須選用另外的雜湊函式，或者對衝突結果進行處理。而不發生衝突的可能性是非常之小的，所以通常對衝突進行處理。常用方法有以下幾種：

開放定址法（open addressing）： $hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m$ , $i=1,2...k\,(k\leq m-1)$ ，其中 $hash(key)$ 為雜湊函式， $m$ 為雜湊表長， $d_{i}$ 為增量序列， $i$ 為已發生衝突的次數。增量序列可有下列取法：

d_{i}=1,2,3...(m-1)

稱為線性探測（Linear Probing）；即

d_{i}=i

，或者為其他線性函式。相當於逐個探測存放位址的表，直到尋找到一個空單元，把雜湊位址存放在該空單元。

d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2}

(k\leq m/2)

稱為 平方探測(Quadratic Probing)。相對線性探測，相當於發生衝突時探測間隔

d_{i}=i^{2}

個單元的位置是否為空，如果為空，將位址存放進去。

d_{i}=

偽亂數序列，稱為 偽隨機探測。

顯示線性探測填裝一個雜湊表的過程：

關鍵字為{89,18,49,58,69}插入到一個雜湊表中的情況。此時線性探測的方法是取

d_{i}=i

。並假定取關鍵字除以10的餘數為雜湊函式法則。

雜湊位址	插入89	插入18	插入49	插入58	插入69
0			49	49	49
1				58	58
2					69
3
4
5
6
7
8		18	18	18	18
9	89	89	89	89	89

第一次衝突發生在填裝49的時候。位址為9的單元已經填裝了89這個關鍵字，所以取

i=1

，往下尋找一個單位，發現為空，所以將49填裝在位址為0的空單元。第二次衝突則發生在58上，取

i=3

，往下尋找3個單位，將58填裝在位址為1的空單元。69同理。

表的大小選取至關重要，此處選取10作為大小，發生衝突的機率就比選擇質數11作為大小的可能性大。越是質數，mod取余就越可能均勻分布在表的各處。

聚集（Cluster，也翻譯做「堆積」）的意思是，在函式位址的表中，雜湊函式的結果不均勻地占據表的單元，形成區塊，造成線性探測產生一次聚集（primary clustering）和平方探測的二次聚集（secondary clustering），雜湊到區塊中的任何關鍵字需要尋找多次試選單元才能插入表中，解決衝突，造成時間浪費。對於開放定址法，聚集會造成效能的災難性損失，是必須避免的。

單獨鏈結串列法：將雜湊到同一個儲存位置的所有元素儲存在一個鏈結串列中。實現時，一種策略是雜湊表同一位置的所有衝突結果都是用棧存放的，新元素被插入到表的前端還是後端完全取決於怎樣方便。

雙雜湊。

再雜湊： $hash_{i}=hash_{i}(key)$ , $i=1,2...k$ 。 $hash_{i}$ 是一些雜湊函式。即在上次雜湊計算發生衝突時，利用該次衝突的雜湊函式位址產生新的雜湊函式位址，直到衝突不再發生。這種方法不易產生「聚集」（Cluster），但增加了計算時間。

建立一個公共溢位區。

常式

在C語言中，實現以上過程的簡要程式^[1]：

開放定址法：

// HashTable
InitializeTable(int TableSize) {
    HashTable H;
    int i;
    // 為散列表分配空間
    // 有些编譯器不支持為struct HashTable 分配空間，聲稱這是一個不完全的結構，
    // 可使用一个指向HashTable的指針為之分配空間。
    // 如：sizeof(Probe)，Probe作为HashTable在typedef定義的指針。
    H = malloc(sizeof(struct HashTable));
    // 散列表大小为一个質数
    H->TableSize = Prime;
    // 分配表所有地址的空間
    H->Cells = malloc(sizeof(Cell) * H->TableSize);
    // 地址初始為空
    for (i = 0; i < H->TableSize; i++)
        H->Cells[i].info = Empty;
    return H;
}

尋找空單元並插入：

// Position
Find(ElementType Key, HashTable H) {
    Position Current;
    int CollisionNum;
    // 冲突次数初始为0
    // 通過表的大小對關鍵字進行處理
    CollisionNum = 0;
    Current = Hash( Key, H->TableSize );
    // 不為空時進行查詢
    while (H->Cells[Current].info != Empty &&
            H->Cells[Current].Element != Key) {
        Current = ++CollosionNum * ++CollisionNum;
        // 向下查找超過表範圍時回到表的開頭
        if (Current >= H->TableSize)
            Current -= H->TableSize;
    }
    return Current;
}

分離連接法

尋找效率

雜湊表的尋找過程基本上和造表過程相同。一些關鍵碼可通過雜湊函式轉換的位址直接找到，另一些關鍵碼在雜湊函式得到的位址上產生了衝突，需要按處理衝突的方法進行尋找。在介紹的三種處理衝突的方法中，產生衝突後的尋找仍然是給定值與關鍵碼進行比較的過程。所以，對雜湊表尋找效率的量度，依然用平均尋找長度來衡量。

尋找過程中，關鍵碼的比較次數，取決於產生衝突的多少，產生的衝突少，尋找效率就高，產生的衝突多，尋找效率就低。因此，影響產生衝突多少的因素，也就是影響尋找效率的因素。影響產生衝突多少有以下三個因素：

雜湊函式是否均勻；
處理衝突的方法；
雜湊表的載荷因子（英語：load factor）。

載荷因子

雜湊表的載荷因子定義為： $\alpha$ = 填入表中的元素個數 / 雜湊表的長度

$\alpha$ 是雜湊表裝滿程度的標誌因子。由於表長是定值， $\alpha$ 與「填入表中的元素個數」成正比，所以， $\alpha$ 越大，表明填入表中的元素越多，產生衝突的可能性就越大；反之， $\alpha$ 越小，標明填入表中的元素越少，產生衝突的可能性就越小。實際上，雜湊表的平均尋找長度是載荷因子 $\alpha$ 的函式，只是不同處理衝突的方法有不同的函式。

對於開放定址法，荷載因子是特別重要因素，應嚴格限制在0.7-0.8以下。超過0.8，查表時的CPU快取不命中（cache missing）按照指數曲線上升。因此，一些採用開放定址法的hash庫，如Java的系統庫限制了荷載因子為0.75，超過此值將resize雜湊表。

舉例：Linux核心的bcache

Linux作業系統在物理檔案系統與塊裝置驅動程式之間引入了「緩衝區快取」（Buffer Cache，簡稱bcache）。當讀寫磁碟檔案的資料，實際上都是對bcache操作，這大大提高了讀寫資料的速度。如果要讀寫的磁碟資料不在bcache中，即快取不命中（miss），則把相應資料從磁碟載入到bcache中。一個快取資料大小是與檔案系統上一個邏輯塊的大小相對應的（例如1KiB位元組），在bcache中每個快取資料塊用struct buffer_head記載其元資訊：

struct buffer_head {
    char *b_data;               // 指向缓存的数据块的指针
    unsigned long b_blocknr;    // 逻辑块号
    unsigned short b_dev;       // 设备号
    unsigned char b_uptodate;   // 缓存中的数据是否是最新的
    unsigned char b_dirt;       // 缓存中数据是否为脏数据
    unsigned char b_count;      // 这个缓存块被引用的次数
    unsigned char b_lock;       // b_lock表示这个缓存块是否被加锁
    struct task_struct *b_wait; // 等待在这个缓存块上的进程
    struct buffer_head *b_prev; // 指向缓存中相同hash值的下一个缓存块
    struct buffer_head *b_next; // 指向缓存中相同hash值的上一个缓存块
    struct buffer_head *b_prev_free; // 缓存块空闲链表中指向下一个缓存块
    struct buffer_head *b_next_free; // 缓存块空闲链表中指向上一个缓存块
};

整個bcache以struct buffer_head為基本資料單元，組織為一個封閉定址（close addressing，即「單獨鏈結串列法」解決衝突）的雜湊表struct buffer_head * hash_table[NR_HASH]; 雜湊函式的輸入關鍵字是b_blocknr（邏輯塊號）與b_dev（裝置號）。計算hash值的雜湊函式表達式為：

(b_dev ^ b_blocknr) % NR_HASH

其中NR_HASH是雜湊表的條目總數。發生「衝突」的struct buffer_head，以b_prev與b_next指標組成一個雙向（不迴圈）鏈結串列。bcache中所有的struct buffer_head，包括使用中不空閒與未使用空閒的struct buffer_head，以b_prev_free和b_next_free指標組成一個雙向迴圈鏈結串列free_list，其中未使用空閒的struct buffer_head放在該鏈結串列的前部。

參考文獻

^ Data Structures and Algorithm Analysis in C (2nd edition).. [2017-02-16]. （原始內容存檔於2020-11-09）.

[例程-1] Data Structures and Algorithm Analysis in C (2nd edition).. [2017-02-16]. （原始內容存檔於2020-11-09）.

[1]

閱論編資料結構
類型	集合容器
抽象類型	關聯陣列多重關連陣列（英語：Multimap）串列前向串列堆疊佇列雙端佇列優先佇列雙端優先佇列集合多重集併查集可持久化資料結構線段樹
陣列	字串位陣列環形緩衝區動態陣列雜湊表雜湊陣列樹（英語：Hashed array tree）稀疏矩陣
鏈（英語：Linked data structure）	關聯表（英語：Association list）鏈結串列跳躍列表鬆散鏈結串列（英語：Unrolled linked list）互斥或鏈結串列
樹	線段樹自平衡二元搜尋樹 B樹二元樹 AA樹 AVL樹紅黑樹平衡樹伸展樹二元搜尋樹堆二元堆積左偏樹二項堆斐波那契堆 R樹 R*樹 R+樹希爾伯特R樹（英語：Hilbert R-tree）希爾伯特字首樹雜湊樹
圖	有向圖有向無環圖二元決策圖無向圖確定性非迴圈有限自動機（英語：Deterministic acyclic finite state automaton）
資料結構術語列表