iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 9

【Day9】[資料結構]-雜湊表Hash Table

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

概念如下圖所示:
https://ithelp.ithome.com.tw/upload/images/20210917/20121027auspOHzYk5.jpg


雜湊表一些專有名詞

  • 桶(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都滿了,可以循環到前面尋找。
https://ithelp.ithome.com.tw/upload/images/20210917/20121027ScabqSVxft.jpg

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…...以此類推。
https://ithelp.ithome.com.tw/upload/images/20210917/20121027YslMDxMQbP.jpg

3.鏈結法(Chaining)
使用鏈結串列(Linked List)資料結構在每一組Bucket中。
https://ithelp.ithome.com.tw/upload/images/20210917/20121027hdzcEEqGsx.jpg

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

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

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


上一篇
【Day8】[資料結構]-佇列Queue-實作
下一篇
【Day10】[資料結構]-雜湊表Hash Table-實作
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言