資料結構與算法（Hash表）

下面的内容有自己的了解， 未必正确， 歡迎探讨。

一、Hash是什麼?

Hash是一個集合到另一集合的映射， 比如集合U = {'Alice', 'Bob', 'Carol', 'Dave'}存在一個函數h(x)使得：

h('Alice') = 0

h('Bob') = 1

h('Carol') = 2

h('Dave') = 3

令M={1,2,3,4}, 我們就可以說h(x)是U到M的哈希函數， 0， 1， 2， 3叫做Hash槽或者Hash桶

二、Hash表的原理

下面用一個例子說明， Hash表的工作原理。

假設我有好友U = {'Alice', 'Bob', 'Carol', 'Dave'}, 我現在想用一個資料結構儲存他們的電話号碼， 結合前面的Hash， 我們可以設計一個高效的資料結構， 讓增删改查的時間複雜度都是O(1). C++代碼實作如下：

class PhoneNumberHashTable {
public:
    void insert(std::string name, std::string phoneNumber) {
        hashTable[hash(name)] = new std::string{phoneNumber};
    }

    void remove(std::string name) {
        delete hashTable[hash(name)];
    }

    void update(std::string name, std::string phoneNumber) {
        *hashTable[hash(name)] = phoneNumber;
    }

    std::string get_phone_number(std::string name) {
        return *hashTable[hash(name)];
    }

private:
    static const int HASH_SIZE = 26;
    std::string* hashTable[HASH_SIZE] = {};

    int hash(std::string key) {
        return key[0] - 'A';
    }
};
           

當然， 段示例代碼有很多問題， 這裡隻是用來揭示hash表的原理。我們繼續看一下代碼， 如果我又有了一個新朋友Baby, 添加Baby号碼會發生什麼事情呢？ 對了， Bob的号碼被沖掉了。 原因是Bob和Baby都被映射到同一個槽了， 這個現象叫做Hash碰撞。如何解決hash碰撞的問題呢？ Hash表允許不同的元素被映射到相同的Hash槽， 映射到相同Hash槽的這些元素可以用一個連結清單來存儲。可以證明這時Hash表的平均時間複雜度仍然為O(1). 下面給了一個改進版本的C++實作：

struct NamePhone {
    std::string name;
    std::string phone;
};

class PhoneNumberHashTable {
public:
    void insert(std::string name, std::string phoneNumber) {
        // 擷取哈希槽的list
        auto& list = hashTable[hash(name)];

        // 如果list已經包含了這個名字， 隻做更新， 否則插入
        auto it = std::find_if(std::begin(list), std::end(list),
                            [name](const NamePhone& np) {
                                return np.name == name;});
        if (it != std::end(list)) {
            it->phone = phoneNumber;
        }
        else {
            list.push_back({name, phoneNumber});
        }
    }

    void remove(std::string name) {
        // 擷取哈希槽的list
        auto& list = hashTable[hash(name)];
        list.remove_if([name](const NamePhone& np) {return np.name == name;});
    }

    std::string find(std::string name) {
        auto& list = hashTable[hash(name)];
        auto it = std::find_if(std::begin(list), std::end(list),
                               [name](const NamePhone& np){return np.name == name;});
        return it->phone;
    }

private:
    static const int HASH_SIZE = 26;
    std::list<NamePhone> hashTable[HASH_SIZE] = {};

    int hash(std::string key) { return std::toupper(key[0]) - 'A'; }
};
           

可以看到改進之後的版本還需要存儲key。

三、常見的Hash函數實作

現在已經知道， Hash表的核心就是Hash函數。可以嘗試總結一下什麼是好的Hash函數：

1. 碰撞越少越好。 如果存在一個函數能将集合U映射到集合S， 沒有碰撞。我們就說這個hash函數是完美hash。

2. 在有碰撞的情況下， 碰撞越均勻越好。

3. hash函數的計算越快越好。

實作1：

U = {0, . . . , p − 1} p是一個質數
S = {0, . . . , s − 1} s ≤ p
ha: U → S | ha(x) = (a(x+b) mod p) mod s, 1 ≤ a ≤ p − 1
           

實作2：

(A[x1,x2..xk] + b) mod p) mode s
           

這種方式用于字元串的hash，下面用代碼示範一下：

class StringHash {
private:
    static constexpr int MAXP = 46337;
    std::list<int> al;
    int b;
    int size_;

public:
    StringHash(int size)
        :b(rand()%MAXP), size_(size){
    }

    int hash(std::string s) {
        int sum = b;
        auto it = std::begin(al);
        for(auto c : s) {
            if (it == std::end(al)) {
                it = al.insert(it, rand() % MAXP);
            }
            sum += *it * c % MAXP;
            ++it;
        }
        return sum % size_;
    }
};
           

總結： 假設有n個元素， 哈希表的大小是s， 支援的操作是find, insert, delete, 那麼用上面的方法，每個操作的時間複雜度是O(1 + n/s), 空間複雜度是O(n + s).