雜湊表(Hash Table)又稱哈希表,是透過雜湊函式(Hash Function)
來計算出一個鍵(key)與值(value)
所對應的位置,進而建立雜湊表格
,而後也能夠過雜湊函式來搜尋找出鍵值存放在表格的位置。由於動作都需要先經由雜湊函式來執行,若不被知道雜湊函式情況下,保密性就極高,因此很常被應用在加密、解密、壓縮、驗證
等領域。
概念如下圖所示:
桶(Bucket):
雜湊表中儲存資料的位置,每一個位置對應唯一位址(Bucket Address)。槽(Slot):
每一個桶中的資料欄位,例如:一筆資料有2個欄位,則代表桶中有2個槽。碰撞(Collision):
若2筆資料經過雜湊函數運算後的雜湊值相同,也就是對應到相同位址時,稱為碰撞。溢位(Overflow):
資料經過雜湊函數運算後,雜湊值所指向的桶位址已滿,無法再儲存,稱為溢位。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)
相加方式分為兩種
:
4.數位分析法(Digits Analysis)
假設欄位資料已知,又屬於同一位數,若很集中則捨棄該位,若很分散則挑選該位。
例如: 手機號碼欄位,都是09開頭+8位號碼,捨去09,取用8位號碼作為雜湊值。
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)
準備多個雜湊函式,當一個發生溢位時,則使用第二個函式,以此類推。
雜湊表初始的
陣列規模若太小,容易造成碰撞次數增加
,而需要多次的碰撞
處理;若規模太大,容易造成過多未儲存數據的陣列空間
,因此初始設定適當的陣列規模
相當重要。