iT邦幫忙

2021 iThome 鐵人賽

DAY 24
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 24

Day-24 Hash Table(雜湊表)

字典(Dictionary) 抽象資料結構

在字典https://chart.googleapis.com/chart?cht=tx&chl=D裡,有https://chart.googleapis.com/chart?cht=tx&chl=n個物品,每一樣東西都會跟隨著一個https://chart.googleapis.com/chart?cht=tx&chl=key(假設物品和物品之間,不會有相同的https://chart.googleapis.com/chart?cht=tx&chl=key),我們可以透過https://chart.googleapis.com/chart?cht=tx&chl=key去找出我們想要的物品,而在字典這個資料結構,支援了以下三種操作

  • Insert : 把一個物品插入到https://chart.googleapis.com/chart?cht=tx&chl=D
  • Delete : 把一個物品從https://chart.googleapis.com/chart?cht=tx&chl=D中移除
  • Search : 輸入一個https://chart.googleapis.com/chart?cht=tx&chl=key,如果https://chart.googleapis.com/chart?cht=tx&chl=key有對應到的物品,回傳該物品,如果找不到對應的物品,則回傳NULL。

在字典中,如果我們使用Search搜尋不到https://chart.googleapis.com/chart?cht=tx&chl=key對應到的物品,我們是沒有辦法像是二元搜尋樹一樣,找到前一個物品或是下一個物品的。

我們要解決上面這個字典的問題,我們可以使用AVL tree,他可以使Insert, Delete, Search這三個操作的時間複雜度均為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn),但我們希望在Search這個操作,我們希望能夠達到https://chart.googleapis.com/chart?cht=tx&chl=O(1)的時間。

在python中,就存在dictionary這種資料結構,而他的底層細節即是使用雜湊表(hash table)的方式實現的


名詞解釋:

  • satellite data(衛星數據)與key(鍵值): 以C語言作為舉例,假設我們定義學生為一個結構(struct)如下:
sturct student{
    int age;
    char* name;
    int ID;
};

如果我們想要對學生以年紀(age)進行排序,那麼對於排序來說,age就是排序的關鍵字,或是鍵值(key),而name和ID就稱為satellite data(衛星數據)。可以想像成排序時,name和ID等satellite data是跟隨age這個key進行排序。

Direct-address tables(直接尋址表)

運用直接尋址表,可以讓我們在https://chart.googleapis.com/chart?cht=tx&chl=O(1)時間內完成Search的操作。

我們可以想像,我們開出了一個很大的陣列,而這個陣列中存放許多元素,每一個元素對應到的index當作是元素對應到的key,如圖所示。

假設有一個集合https://chart.googleapis.com/chart?cht=tx&chl=U存在有https://chart.googleapis.com/chart?cht=tx&chl=n個元素,https://chart.googleapis.com/chart?cht=tx&chl=U%3D%5Cbegin%7BBmatrix%7D0%2C1%2C2%2C...m-1%5Cend%7BBmatrix%7D,每一個元素皆為keys(對應到陣列的index),且這些keys彼此之間相互獨立。

https://chart.googleapis.com/chart?cht=tx&chl=T為一直接循址表(以陣列的形式存在),記為https://chart.googleapis.com/chart?cht=tx&chl=T%5B0...m-1%5D,其中https://chart.googleapis.com/chart?cht=tx&chl=T中每一個位置(槽, slot),對應到https://chart.googleapis.com/chart?cht=tx&chl=U集合中的key,也就是https://chart.googleapis.com/chart?cht=tx&chl=U集合中的元素。

https://chart.googleapis.com/chart?cht=tx&chl=T%5Bk%5D會指向集合中key值為https://chart.googleapis.com/chart?cht=tx&chl=k的元素,如果不存在,則https://chart.googleapis.com/chart?cht=tx&chl=T%5Bk%5D%3DNULL

https://chart.googleapis.com/chart?cht=tx&chl=U表示所有關鍵字(key)的集合,https://chart.googleapis.com/chart?cht=tx&chl=K表示該關鍵字有對應到的元素的關鍵字(key)集合,https://chart.googleapis.com/chart?cht=tx&chl=T為直接循址表,透過https://chart.googleapis.com/chart?cht=tx&chl=T去查詢到欲尋找的元素,https://chart.googleapis.com/chart?cht=tx&chl=Uhttps://chart.googleapis.com/chart?cht=tx&chl=K集合就是https://chart.googleapis.com/chart?cht=tx&chl=T集合的index。

假設我們有一條紀錄,他的key為15,那我們就去查詢(呼叫Search)是否存在某一條紀錄的key為15,如果存在,則https://chart.googleapis.com/chart?cht=tx&chl=T%5B15%5D存在,並回傳https://chart.googleapis.com/chart?cht=tx&chl=T%5B15%5D.Data,否則為NULL。
而以下為SEARCH, INSERT, DELETE的虛擬碼

DIRECT-ADDRESS-SEARCH(T, k)
return T[k]
DIRECT-ADDRESS-INSERT(T, x)
T[x.key]=x
DIRECT-ADDRESS-DELETE(T,x)
T[x.key] = NULL

而上面這些操作,都只需要https://chart.googleapis.com/chart?cht=tx&chl=O(1)的時間

但是在實務上,會遇到兩個問題

  1. 如果https://chart.googleapis.com/chart?cht=tx&chl=m-1是一個很大的數值,那我們就必須要開一個超大的陣列。
  2. 誠如上面的學生排序問題,如果我們將學生姓名作為key,那會變得非常麻煩。(可以將字串轉成ASCII儲存,或是使用類似prehash的技術)

因為上面我的使用陣列的index作為元素關聯的key。我們希望我們能夠保存數據的同時,讓表的規模越小越好。

https://chart.googleapis.com/chart?cht=tx&chl=T陣列中,每一個空格我們可以把它稱為https://chart.googleapis.com/chart?cht=tx&chl=T的一個槽(slot)。

雜湊表(Hash table)與雜湊函數(Hash function)

為了避免掉直接循址表需要開出超級大的陣列這個問題,我們可以使用雜湊函數(Hash function)這項技術進行處理,使用雜湊函數去運算出key。也就是我們希望把一堆https://chart.googleapis.com/chart?cht=tx&chl=key構成的集合https://chart.googleapis.com/chart?cht=tx&chl=m,變成一個比較小的集合https://chart.googleapis.com/chart?cht=tx&chl=n

在使用直接循址的方式時,具有關鍵字https://chart.googleapis.com/chart?cht=tx&chl=k的元素會被存放在https://chart.googleapis.com/chart?cht=tx&chl=T%5Bk%5D中,也就是https://chart.googleapis.com/chart?cht=tx&chl=Thttps://chart.googleapis.com/chart?cht=tx&chl=k槽。而使用雜湊的方式,元素是存放在雜湊函數https://chart.googleapis.com/chart?cht=tx&chl=h(k)運算出的結果。由關鍵字https://chart.googleapis.com/chart?cht=tx&chl=k透過雜湊函數計算出槽所在的位置,也就是https://chart.googleapis.com/chart?cht=tx&chl=index%20%3D%20h(key),這裡雜湊函數https://chart.googleapis.com/chart?cht=tx&chl=h會將元素為關鍵字的https://chart.googleapis.com/chart?cht=tx&chl=U集合映射(Mapping)到雜湊表https://chart.googleapis.com/chart?cht=tx&chl=Thttps://chart.googleapis.com/chart?cht=tx&chl=T%5B0...m-1%5D,而https://chart.googleapis.com/chart?cht=tx&chl=m的值會比直接循址中https://chart.googleapis.com/chart?cht=tx&chl=U集合的大小來的小的許多。

而此時我們可以說https://chart.googleapis.com/chart?cht=tx&chl=h(k)運算出的值是關鍵字https://chart.googleapis.com/chart?cht=tx&chl=k的雜湊值(Hashing)。

概念上就是有用到的https://chart.googleapis.com/chart?cht=tx&chl=keyhttps://chart.googleapis.com/chart?cht=tx&chl=n個,而整個Table的大小為https://chart.googleapis.com/chart?cht=tx&chl=m,我們希望https://chart.googleapis.com/chart?cht=tx&chl=m%3D%5CTheta(n)

上面的操作我們會發現一件事情,如果關鍵字經過雜湊函數後得到的雜湊值和其他關鍵字得到的雜湊值相同時,他們會存取到相同的數值,發生這樣的情況,我們稱為衝突(collision)。例如一個Table中,有兩筆資料存到同一個slot中。

會發生衝突的原因,在於我們給的關鍵字https://chart.googleapis.com/chart?cht=tx&chl=k可以任意數值($U$集合中),但是我們產生出的雜湊值需要在一定的範圍內,也就是在https://chart.googleapis.com/chart?cht=tx&chl=T的index內,因此會發生衝突。舉例如下:

假設我們定義hash function為https://chart.googleapis.com/chart?cht=tx&chl=h(item)%20%3D%20(item)%20%5C%20mod%5C%20%20(table.size),假設https://chart.googleapis.com/chart?cht=tx&chl=table.size%20%3D%208,則如果我們要放入57和65這兩個item,則經過hash function,https://chart.googleapis.com/chart?cht=tx&chl=h(57)%20%3D%2057%20%5C%20mod%5C%208%20%3D%201,https://chart.googleapis.com/chart?cht=tx&chl=h(65)%20%3D%2065%20%5C%20mod%5C%20%208%20%3D%201,這兩個數值會存入到hash table中相同的slot,而這就是衝突。

衝突定義:https://chart.googleapis.com/chart?cht=tx&chl=h(k_i)%20%3D%20h(k_j)%2C%20k_i%20%5Cneq%20k_j

鏈接法(chaining)

鏈接法,概念為如果有超過一個以上的元素經過hash function後,儲存到同樣的slot,則在該slot使用linked list(鏈結串列)將資料全部儲存在槽(slot)中,如下圖所示

在使用這樣的方法後,雜湊表$T$上的字典操作大概如下

CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(x.key)]
CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T[h(k)]
CHAINED-HASH-DELETE
delete x from the list T[h(x.key)]

插入和刪除的操作皆為https://chart.googleapis.com/chart?cht=tx&chl=O(1)(假設為雙向鏈結串列),在最壞的情況下,就是所有資料都在同一個槽裡面,而這時候Search的操作就會是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n),那雜湊表的效率就跟鏈結串列的效率差不多了,但是在實務上,最壞情況幾乎不會發生,他的平均情況是非常好的。

鏈接法效率分析

上面提到,Search的最差情況就是所有元素都在同一個槽(slot)中,而Search的時間會取決於鏈結串列的長度。我們假設有一個具有https://chart.googleapis.com/chart?cht=tx&chl=m個槽位的雜湊表https://chart.googleapis.com/chart?cht=tx&chl=T,總共有https://chart.googleapis.com/chart?cht=tx&chl=n個元素,有https://chart.googleapis.com/chart?cht=tx&chl=n個元素要放入https://chart.googleapis.com/chart?cht=tx&chl=m個槽位。

接著再做出一個假設,所有的https://chart.googleapis.com/chart?cht=tx&chl=key再經過雜湊函數運算後,他們被映射到雜湊表中每一個槽的機率皆是相等的,機率皆為https://chart.googleapis.com/chart?cht=tx&chl=1%2Fm,且每一次均為獨立事件,我們可以估計在使用鏈接法的情況下,https://chart.googleapis.com/chart?cht=tx&chl=T中每一個槽的鏈結串列平均長度為https://chart.googleapis.com/chart?cht=tx&chl=n%2Fm(每一個元素映射到槽的機率為https://chart.googleapis.com/chart?cht=tx&chl=1%2Fm,總共https://chart.googleapis.com/chart?cht=tx&chl=n個元素),而https://chart.googleapis.com/chart?cht=tx&chl=n%2Fm我們會稱他為雜湊表https://chart.googleapis.com/chart?cht=tx&chl=T的裝載因子(load factor),https://chart.googleapis.com/chart?cht=tx&chl=n%2Fm會簡稱為https://chart.googleapis.com/chart?cht=tx&chl=%5Calphahttps://chart.googleapis.com/chart?cht=tx&chl=%5Calpha可以大於,等於,或是小於1,如果https://chart.googleapis.com/chart?cht=tx&chl=n%3Dm,則https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3D%201,也就是當https://chart.googleapis.com/chart?cht=tx&chl=m%20%3D%20%5CTheta(n)https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3D%20%5CTheta(1)成立。

我們發現到使用雜湊表,它的效率取決於雜湊函數將https://chart.googleapis.com/chart?cht=tx&chl=key分布在https://chart.googleapis.com/chart?cht=tx&chl=Thttps://chart.googleapis.com/chart?cht=tx&chl=m個槽位的均勻程度,我們在上面假設了每一個元素出現在https://chart.googleapis.com/chart?cht=tx&chl=m個槽位的機率皆是相等的,且為獨立事件,我們稱這個假設為簡單均勻雜湊(simple uniform hashing)

雜湊表https://chart.googleapis.com/chart?cht=tx&chl=T每一個槽的平均長度,可以使用期望值以下面形式表示

對於https://chart.googleapis.com/chart?cht=tx&chl=j%3D0%2C1%2C...m-1, https://chart.googleapis.com/chart?cht=tx&chl=T%5Bj%5D的鏈結串列長度以https://chart.googleapis.com/chart?cht=tx&chl=n_j表示,則https://chart.googleapis.com/chart?cht=tx&chl=n%3Dn_0%2Bn_1%2B...n_%7Bm-1%7D,並且https://chart.googleapis.com/chart?cht=tx&chl=n_j的期望值為https://chart.googleapis.com/chart?cht=tx&chl=E%5Bn_j%5D%3D%5Calpha%3Dn%2Fm

而當我們使用Search尋找https://chart.googleapis.com/chart?cht=tx&chl=keyhttps://chart.googleapis.com/chart?cht=tx&chl=k的元素,會有兩種情況,第一種為在https://chart.googleapis.com/chart?cht=tx&chl=T%5Bh(k)%5D中沒有找到一個元素的key為https://chart.googleapis.com/chart?cht=tx&chl=k,第二種為成功找到key為https://chart.googleapis.com/chart?cht=tx&chl=k的元素。

  • 在第一次尋找不成功的情況下,我們要遍歷鏈結串列的平均長度為https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha,而假設計算雜湊函數需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1)的時間,則Search平均所需要的時間https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1%2B%5Calpha)
  • 在第一次就成功尋找到,我們需要考慮到每一個槽中的鏈結串列被尋找到的機率並不是均等的,所含元素越多的鏈結串列,被尋找到的機率越大。但是,Search的期望值仍然為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1%20%2B%20%5Calpha)

證明 : 假設欲尋找的元素是n個元素中任意一個,且每一個元素被尋找到的機率皆均等。在一次就成功尋找到元素https://chart.googleapis.com/chart?cht=tx&chl=x的情況下,我們需要遍歷的元素數量為https://chart.googleapis.com/chart?cht=tx&chl=x前面的元素數量加1,因為https://chart.googleapis.com/chart?cht=tx&chl=x之前的元素都是在https://chart.googleapis.com/chart?cht=tx&chl=x之後插入在鏈接串列中,為了確保https://chart.googleapis.com/chart?cht=tx&chl=x之前的元素都有被遍歷到,對https://chart.googleapis.com/chart?cht=tx&chl=x所在的鏈結串列,對https://chart.googleapis.com/chart?cht=tx&chl=x以前插入到鏈結串列元素數量的期望值加1,在對所有https://chart.googleapis.com/chart?cht=tx&chl=n個元素https://chart.googleapis.com/chart?cht=tx&chl=x取平均,得到平均情況的機率。

https://chart.googleapis.com/chart?cht=tx&chl=x_i為插入到鏈結串列中第https://chart.googleapis.com/chart?cht=tx&chl=i個元素,並設https://chart.googleapis.com/chart?cht=tx&chl=k_i%3Dx_i.key。對於https://chart.googleapis.com/chart?cht=tx&chl=k_ihttps://chart.googleapis.com/chart?cht=tx&chl=k_j,定義指示器隨機變數https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D%3DI%5Cbegin%7BBmatrix%7Dh(k_i)%3Dh(k_j)%5Cend%7BBmatrix%7D,表示經過雜湊函數,出現在雜湊表中同一個slot的情況,如果為真則https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D%3D1,反之為0。在前面的簡單均勻雜湊的假設之下,https://chart.googleapis.com/chart?cht=tx&chl=Pr%5Cbegin%7BBmatrix%7Dh(k_i)%3Dh(k_j)%5Cend%7BBmatrix%7D%3D1%2Fm,發生兩個https://chart.googleapis.com/chart?cht=tx&chl=key經過雜湊函數映射到雜湊表中同一個slot機率的期望值https://chart.googleapis.com/chart?cht=tx&chl=E%5Cbegin%7Bbmatrix%7DX_%7Bij%7D%5Cend%7Bbmatrix%7D%3D1%2Fm,因此,在一次成功就尋找到元素,期望遍歷過的元素總數的期望值可以用以下式子進行表示:

n個元素選一個,遍歷整個Hash table(https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bi%3D1%7D%5En),每個Hash table需要檢查的元素數量(https://chart.googleapis.com/chart?cht=tx&chl=1%2B%5Csum_%7Bj%3Di%2B1%7D%5En)

https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%7BE%5B%5Cfrac%201%20n%20%5Csum_%7Bi%3D1%7D%5En(1%2B%5Csum_%7Bj%3Di%2B1%7D%5EnX_%7Bij%7D)%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cdisplaystyle%20%5Cfrac%201%20n%5Csum_%7Bi%3D1%7D%5En(1%2B%5Csum_%7Bj%3Di%2B1%7D%5EnE%5BX_%7Bij%7D%5D)
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D%5Cfrac%201%20n%20%5Csum_%7Bi%3D1%7D%5En(1%2B%5Csum_%7Bj%3Di%2B1%7D%5En%5Cfrac%201%20m)%20
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D1%2B%5Cfrac%201%20%7Bnm%7D%5Csum_%7Bi%3D1%7D%5En(n-i)%20
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D1%2B%5Cfrac%201%20%7Bnm%7D(%5Csum_%7Bi%3D1%7D%5Enn-%5Csum_%7Bi%3D1%7D%5Eni)%20
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D1%2B%5Cfrac%201%20%7Bnm%7D(n%5E2-%5Cfrac%20%7Bn(n%2B1)%7D%202)%20
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D1%2B%5Cfrac%20%7Bn-1%7D%20%7B2m%7D%20
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%3D1%2B%5Cfrac%20%5Calpha%202%20-%5Cfrac%20%5Calpha%20%7B2n%7D%7D

因此,一次成功尋找到元素所需要的全部時間就是遍歷元素個數的期望值加上計算雜湊函數的時間。

https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5CTheta(1)%20%2B%20%5CTheta(1%2B%5Cfrac%20%5Calpha%202%20-%5Cfrac%20%5Calpha%20%7B2n%7D)%20%3D%20%5CTheta(2%2B%5Cfrac%20%5Calpha%202%20-%5Cfrac%20%5Calpha%20%7B2n%7D)%20%3D%5CTheta(1%2B%5Calpha)

因此,成功一次就尋找到元素和第一次沒有成功尋找到,他們的平均情況皆為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1%2B%5Calpha)

經過上面的證明,得到當每一個slot中皆為雙向鏈結串列時,Insert, Delete, Search的操作皆為https://chart.googleapis.com/chart?cht=tx&chl=O(1)的時間可以完成。當然,上面這些證明是基於這是一個簡單均勻雜湊的條件下。

不是hash table都會是https://chart.googleapis.com/chart?cht=tx&chl=O(1),實際上是取決於裝載因子https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha(如果有很多元素,但Hash table很小,那他必定不會是常數時間,如果能夠保證Hash table隨著元素的數量增長,才能夠說他是常數時間)。Hash table之所以好用,就是因為我們可以在常數時間內完成動態集合的字典操作。

參考資料:Introduction to algorithms 3rd


上一篇
Day-23 AVL Tree
下一篇
Day-25 Hash Function(雜湊函數), 乘法雜湊法, 除法雜湊法
系列文
從0開始啃Introduction of algorithms心得與記錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言