哈希表

02-25

簡介

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash) 函數。

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

數組的特點是：定址容易，插入和刪除困難；而鏈表的特點是：定址困難，插入和刪除容易

元素特徵轉變為數組下標的方法就是散列法。三種比較常用的：

1. 除法散列法

最直觀的一種，上圖使用的就是這種散列法，公式：

index = value % 16

2. 平方散列法

求index是非常頻繁的操作，而乘法的運算要比除法來得省時，公式：

index = (value * value) >> 28 （右移，除以2^28。記法：左移變大，是乘。右移變小，是除。）

3. 斐波那契（Fibonacci）散列法