Leetcode 第 705 和 706 題要求你設計一個 hash set 和 hash map，在 C++ 中可以使用 unordered_set 和 unordered_map，或者在輸入資料範圍不大的情況下，可以直接用陣列當作 hash table。但這題不是要求你直接使用現成的資料結構，而是讓你思考如何設計一個 hash table，這促使我想寫下這篇文章，來探討如何設計 Hash Table。

什麼是 hash table

hash table 採用 array 可以在 O(1) 時間 access 的特性為基準，透過 hash function 將 input data 轉換成 key（array 的 index），將 input data 存在對應的位置上。在查詢時，也是透過 hash function 將 input data 轉換成 key，快速到該 index 位置上取出值。

Hash table 有三個基本條件：

hash function 計算出來的值是非負整數
如果 key1 = key2 ，則 hash (key1) = hash (key2)
如果 key1 ≠ key2 ，則 hash (key1) ≠ hash (key2)

第三個條件是相當難辦到的，即便是知名的 hash function，如 MD5 和 SHA 也無法達成，因此必須處理 hash table 的衝突狀況。

如何處理 Collision

處理衝突有以下幾種常見方法：

開放尋址法 Open addressing

如果遇到衝突，就以同樣的策略繼續找出空閒的位置插入，策略又分為

Linear Probing

遇到衝突時，檢查下一個 index 位置是否有空位，如果有就放進去，没有就再往下找。當要尋找元素時後，遇到 collision 的話，還需要往後去搜尋元素，直到遇到空的位置，才知道要停止搜尋。

但衍生出另外一個問題， hash table 也支援刪除操作，直接刪除元素會導致原本應該要繼續的搜尋中止，因此刪除元素要特別做標記。

Quadratic probing 二次探測

linear probing 有一個問題，當今天元素插入很多後，會造成搜尋所需要時間越來越多，最後甚至逼近 O(n) 的狀況。二次探測將原本遇到衝突後的處理步驟由原本的 hash(key)+1, hash(key)+2, hash(key)+3, ... 變成 hash(key)+ 1^2 , hash(key)+ 2^2, ... 變成每次都以2次方來移動。

Double Hashing

不只有一個 hash function，還有第二個、第三個等，當使用 hash1 function 發生衝突時，再用 hash2 function 來找尋空閒位置，依此類推...

優點：

open addressing 法沒有 linked list ，資料都存在 array 中，有利於透過 cache 加快存取速度。

缺點：

刪除資料比較麻煩，需要特別標注要刪除的數據。
所有資料都存在同一個 hash table 中，衝突後的代價比較高，所以 load factor 不宜太高，也因此這種方法比較浪費記憶體

總結適合使用 open addrssing 方法的資料為資料量不大且 load factor 不大的 input data 。

Seperate Chaining

對於有一樣 hash key 的 value ，將這些 value 都放到同一 bucket 內。這些 bucket 可以用不同的資料結構來儲存，例如 Linked list, 紅黑樹或 skip list 等 ...

linked list 法

每個 array 的位置都會對應一條 linled list ，時間複雜度將變為 O(k) ，k 為 linked list 的長度。

linked list 法相對於 open addressing 方法，可以容忍較大的 load factor ，即便 load factor 很大，也只是讓 linked list 變長而已，當然也會造成查詢時間增長，但是比起 sequential 方式搜尋還是比較快。

linked list 因為需要額外的 pointer ，如果存儲的資料小於一個 pointer 大小，那這樣使用 linked list 等於是多耗費一倍的記憶體來儲存資料，但若是要存的資料遠遠大於一個 Pointer 大小，那這樣使用 Pointer 的額外消費就可以忽略不計了。事實上，可以對 linked list 加以改造，後面可以接紅黑樹、 skip list 等，那最終 hash table 的 look up 時間只需要 O(log n) 。

因此 linked list 法比較適合儲存資料量大、單一筆資料大小較大的資料，而且它也支援更多元的優化策略，可以搭配紅黑樹等一起使用。

2-Choice Hashing

設計兩個 hash function ，會得到 hash1(key) 和 hash2(key)，選擇 bucket 內資料數量較少的 bucket 來插入。 Search 時候就需要去搜尋兩個 bucket 了。

這個方法的優點是可以讓資料更均勻的分布。

如何設計 hash function

Hash function 的設計大大影響碰撞的機率，若 Hash function 設計過於複雜的話，勢必會消耗太多計算時間而影響到性能，其次，hash function 的 output 要盡可能均勻分布，避免時常碰到 collision 狀況，常見方法有

取餘數法: 這是很直覺的作法，尤其當 input data 是單純的 integer 時，其中選取質數作為除數是更好的選擇，可以有效分散資料的分布。
數據分析法：以學號後兩碼作為 key ，可以均勻分配學生。或是手機號碼後四碼等方式。
將字串的字元以 ASCII 碼來計算，並做除法或取餘數等動作。

Load Factor

hash table 在增加許多資料後，原本的空間不敷使用而造成碰撞發生機率大幅發生，這時候需要做 hash table 的擴張，這裡介紹 load factor ，用來衡量 hash table 裡還有多少空位，越大代表空位剩下越少，可以用來衡量是否需要擴張 Hash Table 。

load factor = 填入表中的個數 / 表的長度

動態擴張

如果今天資料都是已知的，就可以根據 input data 的特點、分布等，設計出合適的 hash function ，但若資料都是動態新增的，無法事先設計出一個足夠大的 hash table ，勢必面臨需要擴張 hash table 的挑戰，

當 load factor 過大，需要擴張 hash table ，而不像我們在動態擴張陣列直接加大陣列就好，擴張 hash table 還必須重新分配資料。

這裡衍生出一個問題，試想當前有 1GB 的資料放在 hash table ，新插入資料到 hash table 時，觸發了需要擴張 hash table 到 2GB 的 threshold，需要重新安插 1 GB 的資料到新的 hash table 中，這會讓 user 在做這個操作時候感到困擾，因為這個操作所需要時間將變得太長，這種時候一次性的擴張策略就不適合，應該將擴張的策略分散到各個操作中，均攤時間複雜度到 O(1) 。

如何實作一個適合的 hash table

想要實現一個好的 hash table，需要考量以下三點

設計適合的 hash function
選擇合適的方法處理 hash 衝突
設定適合的 load factor threshold ，並設計動態擴張的策略。(load factor threshold 訂得太大，collision 會發生比較多，訂得太小，容易造成記憶體浪費)

Leetcode #706 Design HashMap

由於這題並沒有說明 input data 有哪一種特性，因此，hash function 採取取餘數法，解決衝突採用 sepeate chaining 的 linked list 方法。

class MyHashMap {
public:
    int modulo = 2081;
    vector<list<pair<int, int>>> table;
    MyHashMap() {
        table.resize(modulo+1);
    }

    void put(int key, int value) {
        int index = key%modulo;
        for (auto &element:table[index]) {
            if (element.first == key) {
                element.second = value;
                return;
            }
        }
        table[index].emplace_back(make_pair(key, value));
    }

    int get(int key) {
        int index = key%modulo;
        for (auto &element:table[index]) {
            if (element.first == key) {
                return element.second;
            }
        }
        return -1;
    }

    void remove(int key) {
        int index = key%modulo;
        for (auto it=table[index].begin(); it!= table[index].end(); it++) {
            if (it->first == key) {
                table[index].erase(it);
                return;
            }
        }
    }
};

Reference

数据结构与算法之美

設計一個 hash table – 陪你刷題

什麼是 hash table

如何處理 Collision