雜湊表(Hash Table)又稱哈希表，是透過雜湊函式(Hash Function)來計算出一個鍵(key)與值(value)所對應的位置，進而建立雜湊表格，而後也能夠過雜湊函式來搜尋找出鍵值存放在表格的位置。由於動作都需要先經由雜湊函式來執行，若不被知道雜湊函式情況下，保密性就極高，因此很常被應用在加密、解密、壓縮、驗證等領域。

概念如下圖所示:

雜湊表一些專有名詞

• 桶(Bucket):雜湊表中儲存資料的位置，每一個位置對應唯一位址(Bucket Address)。
• 槽(Slot):每一個桶中的資料欄位，例如：一筆資料有2個欄位，則代表桶中有2個槽。
• 碰撞(Collision):若2筆資料經過雜湊函數運算後的雜湊值相同，也就是對應到相同位址時，稱為碰撞。
• 溢位(Overflow):資料經過雜湊函數運算後，雜湊值所指向的桶位址已滿，無法再儲存，稱為溢位。

雜湊函式設計原則

• 盡可能降低碰撞與溢位的產生
• 不宜過於複雜，越容易計算越佳
• 盡可能把文字轉換成數字的鍵值
• 得到的雜湊值，盡可能分布均勻在每個桶中，不要過於集中。

常見的雜湊函式(Hash Function)

1.除法(Mod/Division)
相除取餘數來當作雜湊值。
例如:有11個Bucket，若有數值4。
4 mod 11 = 4，雜湊值為4。

2.中間平方法(Middle Square)
將值平方後，再取適當的中間位數作為雜湊值。
例如:有1000個Bucket，若有數值235。
235 X 235 = 55225，取中間三位數，雜湊值為522。

3.折疊相加法(Folding Addition)
相加方式分為兩種:

• Shift(移位)
  例如:一個大數值987586265，拆分成3段相加，987+586+265，雜湊值為1838。
• Boundary(邊界)
  例如:一個大數值987586265，拆分成3段，可分為基數段反轉或偶數段反轉，偶數段反轉為: 987+685+265，雜湊值為1937。

4.數位分析法(Digits Analysis)
假設欄位資料已知，又屬於同一位數，若很集中則捨棄該位，若很分散則挑選該位。
例如: 手機號碼欄位，都是09開頭+8位號碼，捨去09，取用8位號碼作為雜湊值。

碰撞(Collision)與溢位(Overflow)常見的處理方式

1.線性探測法(Linear Probing)
假設2筆資料得出一樣的雜湊值，將以線性方式往後尋找直到有空的Bucket為止，一般來說也會視為環狀結構，若後面Bucket都滿了，可以循環到前面尋找。

2.平方探測法(Quadratic Probing)
透過 (H(x) ± i²) mod b，b為bucket數，1 ≤ i ≤ (b-1)/2，用此公式去尋找其他有空的Bucket。
第一次尋找: (H(x) + 1²) mod b
第二次尋找: (H(x) - 1²) mod b
第三次尋找: (H(x) + 2²) mod b
第四次尋找: (H(x) - 2²) mod b…...以此類推。

3.鏈結法(Chaining)
使用鏈結串列(Linked List)資料結構在每一組Bucket中。

鏈結串列的介紹可以參考此篇。

4.再雜湊法(Rehashing)
準備多個雜湊函式，當一個發生溢位時，則使用第二個函式，以此類推。

雜湊表初始的陣列規模若太小，容易造成碰撞次數增加，而需要多次的碰撞處理;若規模太大，容易造成過多未儲存數據的陣列空間，因此初始設定適當的陣列規模相當重要。