open addressing概念

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

open addressing就是直接將每一筆資料直接放到hash table中，hash table的每一個slot最多一個元素，假設我們有個slot，有個元素，我們要保證才能使用這個方法，也就是，但open addresssing有一個顯而易見的問題，就是必然會發生碰撞，這時候，我們使用探測(Probing)這個方式，來找到下一個為空的slot。

探測的順序不一定要按照這個順序，而是依靠於待插入的，而具體要將元素放到哪一個位置，使用一個特殊的hash function來決定，這個hash function需要兩個參數，一個為，另一個為探測的次數(trial count)，hash function會輸出一個介於到的數字。

我們會希望整個hash table是沒有空間被浪費的，因此上面hash function所產生出的數值所構成的集合，會剛好為到的其中一種排列。

插入(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)，插入第一個元素，為，接著繼續插入元素，如果發生該slot有元素存在，則我們就必須考慮現有的元素數目，也就是修改hash fuction的參數，探測數目，去找到空的slot去執行我們想要的操作。

線性探測(linear probing)

給定一個普通的雜湊函數，線性探測使用的雜湊函數為以下

這個方法使用加了常數，然後藉由來使雜湊值保持在一定的範圍，可以確保我們產生出到的所有排列。可以當作任意雜湊函數，像是除法雜湊法，乘法雜湊法等等。

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

雙重雜湊(double hashing)

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

如果和互質，則可以保證我們產生出到的組合，而要滿足這個條件，我們可以假設 , ，或是另外一個方法，取為質數，令,，其中略小於，若為質數，則必然與~的任何數字互質，而由於是取決於另外一個hash function，因此我們可以產生出更大的群集，使上面線性探測發生的一次群集的發生情況大幅度降低。

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