C++ 哈希表原理与实战：从概念到实现

1.4 将关键字转为整数

我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的 Key 是关键字转换成的整数。

二、哈希函数

一个好的哈希函数应该让 N 个关键字被等概率的均匀的散列分布到哈希表的 M 个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。

2.1 除法散列法 / 除留余数法

• 除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M
• 当使用除法散列法时，要尽量避免 M 为某些值，如 2 的幂，10 的幂等。如果是 2^X，那么 key % 2^X 本质相当于保留 key 的后 X 位，那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。如：{63,31} 看起来没有关联的值，如果 M 是 16（即 2^4），那么计算出的哈希值都是 15，因为 63 的二进制后 8 位是 00111111，31 的二进制后 8 位是 00011111。如果是 10^X，就更明显了，保留的都是 10 进值的后 x 位，如：{112,12312}，如果 M 是 100（即 10^2），那么计算出的哈希值都是 12
• 当使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个质数 (素数)

素数：指大于 1 的自然数中，除了 1 和它本身外，无法被其他自然数整除的数

关键特征：最小的素数是 2，也是唯一的偶数素数。大于 2 的素数都是奇数，但奇数不一定是素数（比如 9 能被 3 整除）。素数的因数只有 1 和它自身，没有其他约数

与哈希函数的关联：

在除法散列法中，哈希表大小 M 取素数，能让关键字的哈希值分布更均匀，减少哈希冲突。这也是你之前学习哈希函数时，M 建议取素数的核心原因

需要说明的是，实践中也是八仙过海，各显神通，Java 的 HashMap 采用除法散列法时就是 2 的整数次幂做哈希表的大小 M，这样不用取模，可直接位运算（位运算比模更高效）。但它不是单纯取模，比如 M 是 2^16，本质是取后 16 位，通过 key' = key>>16，再将 key 和 key'异或的结果作为哈希值，尽量让 key 所有位都参与计算，使哈希值更均匀。所以我们上面建议 M 取质数的理论是多数数据结构书籍的理论，实践中需灵活运用，抓住本质，不可死读书。

2.2 乘法散列法（了解）

• 乘法散列法对哈希表大小 M 没有要求，大思路第一步：用关键字 K 乘上常数 A（0<A<1），并抽取出 kA 的小数部分。第二步：后再用 M 乘以 kA 的小数部分，再向下取整**。
• h(key) = floor(M \times ((A \times key)%1.0))，其中 floor 表示对表达式进行下取整，A∈(0,1)，这里最重要的是 A 的值应该如何设定，Knuth ——这位大佬认为 A = (sqrt{5} - 1)/2 = 0.6180339887....)（黄金分割点）比较好。
• 乘法散列法对哈希表大小 M 是没有要求的，假设 M 为 1024，key 为 1234，A = 0.6180339887，Akey = 762.6539420558，取小数部分为 0.6539420558，M×((A×key)%1.0) = 0.65394205581024 = 669.6366651392，那么 h(1234) = 669

2.3 全域散列法（了解）

• 如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
• h_{ab}(key) = ((a×key + b)%P)%M，P 需要选一个足够大的质数，a 可以随机选 [1,P-1] 之间的任意整数，b 可以随机选 [0,P-1] 之间的任意整数，这些函数构成了一个 P*(P-1) 组全域散列函数组。假设 P=17，M=6，a=3，b=4，则 h_{34}(8) = ((3×8 + 4)%17)%6 = 5。
• 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致找不到插入的 key 了

2.4 其他方法（了解）

• 上面的几种方法是《算法导论》书籍中讲解的方法。
• 《殷人昆 数据结构：用面向对象方法与 C++ 语言描述（第二版）》和《数据结构 (C 语言版). 严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数字分析法等，这些方法相对更适用于一些局限的特定场景，有兴趣可以去看看这些书籍

三、处理哈希冲突（重点！）

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放定址法和链地址法（哈希桶）。

3.1 开放定址法

在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于 1 的。这里的规则有三种：线性探测、二次探测、双重探测。

3.1.1 线性探测（含群集/堆积问题）

从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。

线性探测的比较简单且容易实现，线性探测的问题假设，hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集 / 堆积。下面的二次探测可以一定程度改善这个问题。

如果我们要将一些数存放到哈希表中例如：{19,30,5,36,13,20,21,12}

我们就可以发现 30 与 19 发生哈希冲突，30 只能放到下标为 9 的位置，然后 20 又与 30 发生冲突.......这样造成的连续哈希冲突，我们就叫作群集 / 堆积。

那么如何解决呢？接下来讲解二次探测。

3.1.2 二次探测

3.1.3 双重散列

四、全面解析开放定址法（结构到细节的实战）

开放定址法在实践中，不如下面讲的链地址法，因为开放定址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测实现即可。

4.1 哈希表结构的实现

enum State { EXIST, EMPTY, DELETE }; 
template<class K, class V> struct HashData { 
    pair<K, V> _kv; 
    State _state = EMPTY; 
}; 
template<class K, class V> class HashTable { 
private: 
    vector<HashData<K, V>> _tables; 
    size_t _n = 0; // 表中存储数据个数 
};

要注意的是这里需要给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。如下图，我们删除 30，会导致查找 20 失败，当我们给每个位置加一个状态标识 {EXIST,EMPTY,DELETE}，删除 30 就可以不用删除值，而是把状态改为 DELETE，那么查找 20 时是遇到 EMPTY 才能，就可以找到 20。

4.2 扩容问题

这里我们哈希表负载因子控制在 0.7，当负载因子到 0.7 以后我们就需要扩容了，我们还是按照 2 倍扩容，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2 倍后就不是质数了。那么如何解决了，一种方案就是上面 2.1 除法散列中我们讲的 Java HashMap 的使用 2 的整数次幂，但是计算时不能直接取模的改进方法。另外一种方案是 sgi 版本的哈希表使用的方法（我们要讲解的版本），给了一个近似 2 倍的质数表，每次去质数表获取扩容后的大小。

static const int __stl_num_primes = 28; 
static const unsigned long __stl_prime_list[__stl_num_primes] = { 
    53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 
    196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 
    50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 
    3221225473, 4294967291 
}; 
inline unsigned long __stl_next_prime(unsigned long n) { 
    const unsigned long* first = __stl_prime_list; 
    const unsigned long* last = __stl_prime_list + __stl_num_primes; 
    // >= n 
    const unsigned long* pos = lower_bound(first, last, n); 
    return pos == last ? *(last - 1) : *pos; 
}

4.3 key 不能取模的问题

当 key 是 string/Date 等类型时，key 不能取模，那么我们需要给 HashTable 增加一个仿函数，这个仿函数支持把 key 转换成一个可以取模的整形，如果 key 可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个 Key 不能转换为整形，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量 key 的每值都参与到计算中，让不同的 key 转换出的整形值不同。string 做哈希表的 key 非常常见，所以我们可以考虑把 string 特化一下。

template<class K> struct HashFunc { 
    size_t operator()(const K& key) { 
        return (size_t)key; 
    } 
}; 
// 特化 
template<> struct HashFunc<string> { 
    // 字符串转换成整形，可以把字符 ascii 码相加即可 
    // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 
    // 这里我们使用 BKDR 哈希的思路，用上次的计算结果去乘以一个质数， 
    // 这个质数一般去 31, 131 等效果会比较好 
    size_t operator()(const string& key) { 
        size_t hash = 0; 
        for (auto ch : key) { 
            hash += ch; 
            hash *= 131; 
        } 
        return hash; 
    } 
}; 
template<class K, class V, class Hash = HashFunc<K>> class HashTable { 
public: 
private: 
    vector<HashData<K, V>> _tables; 
    size_t _n = 0; // 表中存储数据个数 
};

五、链地址法

5.1 为什么用链地址法

开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

链地址法本质就是：完全避免哈希冲突

⚠️思考：链地址法这么好用，为什么还要学习开放地址发，直接学开放地址法不就行了吗，那么链地址法就真的没有弊端吗？

示例：将{19,30,5,36,13,20,21,12,24,96}插入到 M=11 的表中

5.2 扩容

开放定址法负载因子必须小于 1，链地址法的负载因子没有限制，可以大于 1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就扩容，我们下面实现也使用这个方式。

思考：哈希表如果扩容了，那么原来在同一个桶里挂的节点还在一起吗？

5.3 极端场景

如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但假设不是被针对，用了全域散列法，却偶然出现某个桶很长、查找效率很低的情况怎么办？在 Java8 的 HashMap 中，当桶的长度超过阈值 (8) 时，会把链表转换成红黑树。一般情况下，不断扩容后单个桶很长的场景比较少，下面我们实现时不搞这么复杂，大家了解这个解决极端场景的思路即可。

哈希桶有一个缺点：当我们插入的数据越来越多的时候，它会突然有波动，而随着数据越来越多，这种波动就会越来越剧烈。

5.4 哈希桶的实现

5.4.1 哈希桶的结构

template<class T> struct HashNode { 
    T _data; 
    HashNode<T>* _next; 
    HashNode(const T& data) :_data(data) , _next(nullptr) { } 
};

5.4.2 插入

pair<Iterator, bool> Insert(const T& data) { 
    KeyOfT kot; 
    if (auto it = Find(kot(data)); it != End()) return { it, false }; 
    Hash hs; 
    // 负载因子 == 1 就开始扩容 
    if (_n == _tables.size()) { 
        std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); 
        for (size_t i = 0; i < _tables.size(); i++) { 
            // 遍历旧表，旧表节点重新映射，挪动到新表 
            Node* cur = _tables[i]; 
            while (cur) { 
                Node* next = cur->_next; 
                // 头插 
                size_t hashi = hs(kot(cur->_data)) % newtables.size(); 
                cur->_next = newtables[hashi]; 
                newtables[hashi] = cur; 
                cur = next; 
            } 
            _tables[i] = nullptr; 
        } 
        _tables.swap(newtables); 
    } 
    size_t hashi = hs(kot(data)) % _tables.size(); 
    // 头插 
    Node* newnode = new Node(data); 
    newnode->_next = _tables[hashi]; 
    _tables[hashi] = newnode; 
    ++_n; 
    return { Iterator(newnode, this), true }; 
}

5.4.3 查找

Iterator Find(const K& key) { 
    KeyOfT kot; 
    Hash hs; 
    size_t hashi = hs(key) % _tables.size(); 
    Node* cur = _tables[hashi]; 
    while (cur) { 
        if (kot(cur->_data) == key) { 
            return { cur, this }; 
        } 
        cur = cur->_next; 
    } 
    return { nullptr, this }; 
}

5.4.4 删除

bool Erase(const K& key) { 
    KeyOfT kot; 
    Hash hs; 
    size_t hashi = hs(key) % _tables.size(); 
    Node* prev = nullptr; 
    Node* cur = _tables[hashi]; 
    while (cur) { 
        if (kot(cur->_data) == key) { 
            // 删除 
            if (prev == nullptr) { 
                // 桶中第一个节点 
                _tables[hashi] = cur->_next; 
            } else { 
                prev->_next = cur->_next; 
            } 
            --_n; 
            delete cur; 
            return true; 
        } 
        prev = cur; 
        cur = cur->_next; 
    } 
    return false; 
}

六、完整代码：

HashTable.h：

#include<vector>
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = { 
    53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 
    196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 
    50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 
    3221225473, 4294967291 
};
inline unsigned long __stl_next_prime(unsigned long n) { 
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    // >= n 
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}
template<class K> struct HashFunc { 
    size_t operator()(const K& key) { 
        return (size_t)key; 
    } 
}; 
// 特化 
template<> struct HashFunc<string> { 
    // 字符串转换成整形，可以把字符 ascii 码相加即可 
    // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 
    // 这里我们使用 BKDR 哈希的思路，用上次的计算结果去乘以一个质数， 
    // 这个质数一般去 31, 131 等效果会比较好 
    size_t operator()(const string& key) { 
        size_t hash = 0; 
        for (auto ch : key) { 
            hash += ch; 
            hash *= 131; 
        } 
        return hash; 
    } 
}; 
namespace hash_bucket { 
    template<class T> struct HashNode { 
        T _data; 
        HashNode<T>* _next; 
        HashNode(const T& data) :_data(data) , _next(nullptr) { } 
    }; 
    // 前置声明 
    template<class K, class T, class KeyOfT, class Hash> class HashTable; 
    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct HTIterator { 
        typedef HashNode<T> Node; 
        typedef HashTable<K, T, KeyOfT, Hash> HT; 
        typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self; 
        Node* _node; 
        const HT* _pht; 
        HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) { } 
        Ref operator*() { return _node->_data; } 
        Ptr operator->() { return &_node->_data; } 
        Self& operator++() {//9:11 
            if (_node->_next) // 当前桶没走完 
            { 
                _node = _node->_next; 
            } else // 当前桶走完了，找到下一个桶的第一个节点 
            { 
                KeyOfT kot; 
                Hash hs; 
                // 算出当前桶的位置 
                size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); 
                ++hashi; 
                while (hashi < _pht->_tables.size()) { 
                    if (_pht->_tables[hashi]) // 找到下一个不为空的桶 
                    { 
                        _node = _pht->_tables[hashi]; 
                        break; 
                    } else { 
                        ++hashi; 
                    } 
                } 
                if (hashi == _pht->_tables.size()) // 最后一个桶走完了，要++到 end() 位置 
                { 
                    // end() 中_node 是空 
                    _node = nullptr; 
                } 
            } 
            return *this; 
        } 
        bool operator!=(const Self& s) const { return _node != s._node; } 
        bool operator==(const Self& s) const { return _node == s._node; } 
    }; 
    // hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht; 
    // hash_bucket::HashTable<K, K, SetKeyOfT> _ht; 
    template<class K, class T, class KeyOfT, class Hash> class HashTable { 
        // 友元声明 
        template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct HTIterator; 
        typedef HashNode<T> Node; 
    public: 
        typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator; 
        typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator; 
        Iterator Begin() { 
            if (_n == 0) { return End(); } 
            for (size_t i = 0; i < _tables.size(); i++) { 
                if (_tables[i]) { return Iterator(_tables[i], this); } 
            } 
            return End(); 
        } 
        Iterator End() { return Iterator(nullptr, this); } 
        ConstIterator Begin() const { 
            if (_n == 0) { return End(); } 
            for (size_t i = 0; i < _tables.size(); i++) { 
                if (_tables[i]) { return ConstIterator(_tables[i], this); } 
            } 
            return End(); 
        } 
        ConstIterator End() const { return Iterator(nullptr, this); } 
        HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) { } 
        ~HashTable() { 
            for (size_t i = 0; i < _tables.size(); i++) { 
                Node* cur = _tables[i]; 
                while (cur) { 
                    Node* next = cur->_next; 
                    delete cur; 
                    cur = next; 
                } 
                _tables[i] = nullptr; 
            } 
            _n = 0; 
        } 
        pair<Iterator, bool> Insert(const T& data) { 
            KeyOfT kot; 
            if (auto it = Find(kot(data)); it != End()) return { it, false }; 
            Hash hs; 
            // 负载因子 == 1 就开始扩容 
            if (_n == _tables.size()) { 
                std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); 
                for (size_t i = 0; i < _tables.size(); i++) { 
                    // 遍历旧表，旧表节点重新映射，挪动到新表 
                    Node* cur = _tables[i]; 
                    while (cur) { 
                        Node* next = cur->_next; 
                        // 头插 
                        size_t hashi = hs(kot(cur->_data)) % newtables.size(); 
                        cur->_next = newtables[hashi]; 
                        newtables[hashi] = cur; 
                        cur = next; 
                    } 
                    _tables[i] = nullptr; 
                } 
                _tables.swap(newtables); 
            } 
            size_t hashi = hs(kot(data)) % _tables.size(); 
            // 头插 
            Node* newnode = new Node(data); 
            newnode->_next = _tables[hashi]; 
            _tables[hashi] = newnode; 
            ++_n; 
            return { Iterator(newnode, this), true }; 
        } 
        Iterator Find(const K& key) { 
            KeyOfT kot; 
            Hash hs; 
            size_t hashi = hs(key) % _tables.size(); 
            Node* cur = _tables[hashi]; 
            while (cur) { 
                if (kot(cur->_data) == key) { 
                    return { cur, this }; 
                } 
                cur = cur->_next; 
            } 
            return { nullptr, this }; 
        } 
        bool Erase(const K& key) { 
            KeyOfT kot; 
            Hash hs; 
            size_t hashi = hs(key) % _tables.size(); 
            Node* prev = nullptr; 
            Node* cur = _tables[hashi]; 
            while (cur) { 
                if (kot(cur->_data) == key) { 
                    // 删除 
                    if (prev == nullptr) { 
                        // 桶中第一个节点 
                        _tables[hashi] = cur->_next; 
                    } else { 
                        prev->_next = cur->_next; 
                    } 
                    --_n; 
                    delete cur; 
                    return true; 
                } 
                prev = cur; 
                cur = cur->_next; 
            } 
            return false; 
        } 
    private: 
        std::vector<Node*> _tables; // 指针数组 
        size_t _n; 
        // std::vector<std::list<K, V>> _tables; 
    }; 
}

Test.cpp：

#include<iostream>
#include<unordered_map>
using namespace std;
#include"HashTable.h"
void Print(const hash_bucket::HashTable<int, int>& s) {
    hash_bucket::HashTable<int, int>::Iterator it = s.Begin();
    while (it != s.End()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
int main() {
    hash_bucket::HashTable<int, int> us;
    us.Insert(3);
    us.Insert(1000);
    us.Insert(2);
    us.Insert(102);
    us.Insert(2111);
    us.Insert(22);
    hash_bucket::HashTable<int, int>::Iterator it = us.Begin();
    while (it != us.End()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    Print(us);
    hash_bucket::HashTable<string, string> dict;
    dict.Insert({ "string", "字符串" });
    dict.Insert({ "left", "左边" });
    dict.Insert({ "right", "右边" });
    dict.Insert({ "map", "图" });
    for (auto& [k, v] : dict) {
        cout << k << ":" << v << endl;
    }
    return 0;
}