Hash_table

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

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

## 基本概念

* 若關鍵字為 $k$ ，則其值存放在 $f(k)$ 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係 $f$ 為雜湊函數，按這個思想建立的表為**雜湊表**。
* 對不同的關鍵字可能得到同一雜湊地址，即 $k_{1}\neq k_{2}$ ，而 $f(k_{1})=f(k_{2})$ ，這種現象稱為**衝突**（英語：Collision）。具有相同函數值的關鍵字對該雜湊函數來說稱做**同義詞**。綜上所述，根據雜湊函數 $f(k)$ 和處理衝突的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置，這種表便稱為**雜湊表**，這一映射過程稱為雜湊造表或雜湊，所得的存儲位置稱雜湊地址。
* 若對於關鍵字集合中的任一個關鍵字，經雜湊函數映象到地址集合中任何一個地址的概率是相等的，則稱此類雜湊函數為均勻雜湊函數（Uniform Hash function），這就使關鍵字經過雜湊函數得到一個「隨機的地址」，從而減少衝突。

## 構造雜湊函數

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

1. 直接定址法：取關鍵字或關鍵字的某個線性函數值為雜湊地址。即 $hash(k)=k$ 或 $hash(k)=a\cdot k+b$ ，其中 $a\,b$ 為常數（這種雜湊函數叫做自身函數）
2. 數字分析法：假設關鍵字是以 _r_ 為基的數，並且哈希表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成哈希地址。
3. 平方取中法：取關鍵字平方後的中間幾位為哈希地址。通常在選定哈希函數時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關，由此使隨機分布的關鍵字得到的哈希地址也是隨機的。取的位數由表長決定。
4. 摺疊法：將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址。
5. 隨機數法
6. 除留餘數法：取關鍵字被某個不大於雜湊表表長 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 的餘數為雜湊函數法則。

　
: 第一次衝突發生在填裝 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. 雜湊函數是否均勻；
2. 處理衝突的方法；
3. 雜湊表的載荷因子（英語：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` 記載其元信息：

整個 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` 放在該鍊表的前部。

## 參考文獻