iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

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

Day-26 Hash Table-開放定址(Open Addressing)

open addressing概念

前面提到,在Hash table中發生碰撞時,我們會使用chaining的方式處理,也就是在每一個slot中建立一個linked list,但這會涉及到很多指標問題,以及花費額外的時間開銷,以及每一個元素,還要記錄下一個節點的指標,為此,我們使用了另外一種方法,稱為open addressing。

open addressing就是直接將每一筆資料直接放到hash table中,hash table的每一個slot最多一個元素,假設我們有https://chart.googleapis.com/chart?cht=tx&chl=m個slot,有https://chart.googleapis.com/chart?cht=tx&chl=n個元素,我們要保證https://chart.googleapis.com/chart?cht=tx&chl=m%3E%3Dn才能使用這個方法,也就是https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3C%201,但open addresssing有一個顯而易見的問題,就是必然會發生碰撞,這時候,我們使用探測(Probing)這個方式,來找到下一個為空的slot。

探測的順序不一定要按照https://chart.googleapis.com/chart?cht=tx&chl=0%2C1%2C...%2Cm-1這個順序,而是依靠於待插入的https://chart.googleapis.com/chart?cht=tx&chl=key,而具體要將元素放到哪一個位置,使用一個特殊的hash function來決定,這個hash function需要兩個參數,一個為https://chart.googleapis.com/chart?cht=tx&chl=key,另一個為探測的次數(trial count),hash function會輸出一個介於https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的數字。

我們會希望整個hash table是沒有空間被浪費的,因此上面hash function所產生出的數值所構成的集合,會剛好為https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的其中一種排列。

插入(insert), 搜尋(search), 刪除(delete)

探測的目的就是要找到下一個空的slot,下面演示一個陣列和使用探測的方式進行插入

上面這張圖演示使用insert插入元素的形式,如果失敗,則探測次數加1,目的是為了改變hash function所產生的值。

而插入的概念就像是上方所演示的,如果發現slot為NULL,則插入該slot,如果發現Hash table已經滿了,則回傳錯誤

HASH-INSERT(T, k)
i = 0
repeat
    j = h(k, i)
    if T[j] == NULL
        T[j] = k
        return j
    else
        i = i + 1
until i == m
error "hash table overflow"

而搜尋的操作也和插入是一樣的,如果找到就回傳該index,否則回傳NULL。

HASH-SEARCH(T,k)
i = 0
repeat
    j = h(k, j)
    if T[j] == k
        return j
    i = i + 1
until T[j] == NULL or i == m
return NULL

而刪除的部分就比較麻煩了,如果我們將想要刪除的數值標示成NULL,那麼在搜尋時我們就會出問題了,因為HASH-SEARCH會停在當T[j] == NULL時,因此會回傳NULL表示該數值不在Hash table中,而這很明顯是錯誤的,因此,我們必須要有一個特殊的標示符來表示該節點已經被刪除,為此,我們必須修改一點點HASH-SEARCH,當遇到刪除的標示符,繼續遍歷,不做任何行為。

而HASH-INSERT也要做出相似的修改,當遇到NULL或是刪除標示符,就可以將欲插入的數值放入該slot。

而我們可以發現到,當我們在做insert, search, delete時,這些操作都取決於我們的hash function,也就是我們探測的方式(probing),插入第一個元素,為https://chart.googleapis.com/chart?cht=tx&chl=O(1),接著繼續插入元素,如果發生該slot有元素存在,則我們就必須考慮現有的元素數目,也就是修改hash fuction的參數,探測數目,去找到空的slot去執行我們想要的操作。

線性探測(linear probing)

給定一個普通的雜湊函數https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20h'%20%3A%20U%5Crightarrow%5Cbegin%7BBmatrix%7D0%2C1%2C...%2Cm-1%5Cend%7BBmatrix%7D,線性探測使用的雜湊函數為以下

https://chart.googleapis.com/chart?cht=tx&chl=h(k%2C%20i)%20%3D%20(h'(k)%20%2B%20i)%5C%20mod%5C%20m%5C%20%5C%20%2C%20i%20%3D%200%2C1%2C...m-1

這個方法使用加了常數https://chart.googleapis.com/chart?cht=tx&chl=i,然後藉由https://chart.googleapis.com/chart?cht=tx&chl=%5C%20mod來使雜湊值保持在一定的範圍,可以確保我們產生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的所有排列。https://chart.googleapis.com/chart?cht=tx&chl=h'(k)可以當作任意雜湊函數,像是除法雜湊法,乘法雜湊法等等。

雖然這是一個很簡單產生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1排序的做法,但它存在一個問題,稱為一次群集(primary clustering)。表示hash table中某一個區塊的slot都已經有元素了,如果這時候有一個https://chart.googleapis.com/chart?cht=tx&chl=key又被分配到該區域,可能會造成我們需要進行很多次linear probing才找到合適的slot進行操作,因為每一次只移動一格i, k不變,而這連帶會影響到insert, delete和search的效率。

雙重雜湊(double hashing)

雙重雜湊是用於open addressing最好的方法之一,他產生出的排列具有隨機選擇性和許多特性,他的雜湊函數如下

https://chart.googleapis.com/chart?cht=tx&chl=h(k%2C%20i)%20%3D%20(h_1(k)%20%2B%20ih_2(k))%20%5C%20mod%20%5C%20m

如果https://chart.googleapis.com/chart?cht=tx&chl=h_2(k)https://chart.googleapis.com/chart?cht=tx&chl=m互質,則可以保證我們產生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的組合,而要滿足這個條件,我們可以假設https://chart.googleapis.com/chart?cht=tx&chl=m%3D2%5Er , https://chart.googleapis.com/chart?cht=tx&chl=h_2(k)%20%5C%20mod%5C%20k%20%5Cne%200,或是另外一個方法,取https://chart.googleapis.com/chart?cht=tx&chl=m為質數,令https://chart.googleapis.com/chart?cht=tx&chl=h_1(k)%20%3D%20k%20%5C%20mod%5C%20m,https://chart.googleapis.com/chart?cht=tx&chl=%20h_2(k)%20%3D%201%20%2B%20(k%5C%20mod%5C%20m'),其中https://chart.googleapis.com/chart?cht=tx&chl=m'略小於https://chart.googleapis.com/chart?cht=tx&chl=m,若https://chart.googleapis.com/chart?cht=tx&chl=m為質數,則https://chart.googleapis.com/chart?cht=tx&chl=m必然與https://chart.googleapis.com/chart?cht=tx&chl=1~https://chart.googleapis.com/chart?cht=tx&chl=m'的任何數字互質,而由於https://chart.googleapis.com/chart?cht=tx&chl=i是取決於另外一個hash function,因此我們可以產生出更大的群集,使上面線性探測發生的一次群集的發生情況大幅度降低。

參考資料:Introduction to algorithms 3rd, https://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html


上一篇
Day-25 Hash Function(雜湊函數), 乘法雜湊法, 除法雜湊法
下一篇
Day-27 圖論(Graph)基本概念
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言