C++ 哈希表详解：开散列与闭散列

1.5 处理哈希冲突

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

1.5.1 开放定址法（闭散列）

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的下一个'空位置中去。

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

1. 线性探测（挨着查找）

1. 从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置（回绕方法就是进行取模）。

2. h(key) = hash0 = key % M , hash0 位置冲突了，则线性探测公式为： hc(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M − 1}，因为负载因子小于 1，则最多探测 M-1 次，一定能找到一个存储 key 的位置。

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

演示 {19,30,5,36,13,20,21,12} 等这一组值映射到 M=11 的表中（key%11） h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1

线性探测法占别人的位置会导致堆积。

2. 二次探测（跳跃着查找）

1. 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。

2. h(key) = hash0 = key % M , hash0 位置冲突了，则二次探测公式为： hc(key, i) = hashi = (hash0 ± i * i) % M，i = {1, 2, 3, ..., M/2（二分之 M）}

3. 二次探测当 hashi = (hash0 − i )%M 时，当 hashi<0 时，需要 hashi += M。

演示 {19,30,52,63,11,22} 等这一组值映射到 M=11 的表中 h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

二次探测法虽然跳跃起来了但是却无法充分利用位置。

3. 双重散列

1. 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。

2. h1 (key) = hash0 = key % M , hash0 位置冲突了，则双重探测公式为： hc(key, i) = hashi = (hash0 + i * h2 (key)) % M，i = {1, 2, 3, ..., M}

也跳跃着查找，但是使用 i*下一个哈希函数算出来的值。

3. 要求 h2 (key) < M 且 h2 (key) 和 M 互为质数，有两种简单的取值方法： a. 当 M 为 2 整数幂时，h2 (key) 从 [0，M-1] 任选一个奇数 b. 当 M 为质数时，h2 (key) = key % (M − 1) + 1

4. 保证 h2 (key) 与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数说无法充分利用整个散列表。 举例来说，若初始探查位置为 1，偏移量为 3，整个散列表大小为 12，那么所能寻址的位置为 {1, 4, 7, 10}，寻址个数为 p = gcd(M, h1 (key)) > 1，那么所能寻址的位置的个数为 M/P < M，使得对于一个关键字来 12/gcd(12, 3) = 4。

演示 {19,30,52} 等这一组值映射到 M=11 的表中，设 h2 (key) = key%10 + 1

上面的三种方法都无法完全解决哈希冲突的问题，只有跳出内卷循环才能解决问题，也就是链地址法。

2. 闭散列实现哈希表

2.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 {
public:
private:
    vector<HashData<K, V>> _tables;//表的空间大小
    size_t _n; // 记录数据个数
};

哈希是通过哈希函数使得元素的存储位置与它的关键码之间能够建立一一映射的关系，需要使用 pair<K,V> 类型进行存储。采用 vector 作为底层逻辑，存储元素类型为哈希节点类型 HashData<K, V>。

这里不采用 size 作为哈希表中有效元素个数，考虑到容器中结构的差异性，是由于_ size 一般用于序列式容器中表示有效元素个数，在关联式容器中命名约定一般规定_n 作为记录有效元素个数。

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

2.2 扩容

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

负载因子 >= 0.7 扩容 n/m 数据个数/表的空间大小。

当哈希表进行扩容时，表的长度发生了变换。这也意味着通过哈希函数 (开发定址法) 得到的位置需要重新安排插入，所以需要再开辟空间和插入数据，重新进行映射到新表中，遍历旧表，将旧表的数据映射到新表，然后再使用新对象去调用插入，把旧表的数据插入到新表，交换新旧表的空间。

素数表：

//素数表
inline unsigned long __stl_next_prime(unsigned long n) {
    // Note: assumes long is at least 32 bits.
    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
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

扩容代码：

//扩容
// 负载因子 >= 0.7 扩容 n/m 数据个数/表的空间大小
//为了方便计算分子 n*10
if (_n * 10 / _tables.size() >= 7) {
    //创建一个新的哈希表 newht 哈希表里本来就有 vector
    HashTable<K, V> newht;
    //*2 是无法一直保持素数的
    //newht._tables.resize(_tables.size() * 2);
    //使用素数表来获取比素数表的值大一点的值
    newht._tables.resize(__stl_next_prime(_tables.size() + 1));
    for (auto& data : _tables) {
        // 遍历旧表，旧表的数据映射到新表
        if (data._state == EXIST) {
            //使用新对象去调用插入，把旧表的数据插入到新表
            newht.Insert(data._kv);
        }
    }
    //交换新旧表的空间
    _tables.swap(newht._tables);
}

2.3 插入

在插入过程，元素通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入。

bool Insert(const pair<K, V>& kv) {
    //如果值已经存在
    if (Find(kv.first)) return false;
    Hash hash;//仿函数，用于转换成为无符号整形
    //插入值之后从起始位置 hash0 去用插入的值对表的大小取模算出值对应的位置
    size_t hash0 = hash(kv.first) % _tables.size();//hash0 是第一次算出来的位置
    size_t hashi = hash0;
    size_t i = 1;
    int flag = 1;
    while (_tables[hashi]._state == EXIST)//如果 hashi 的状态为存在
    {
        //进行线性探测
        //如果到达表的最后一个位置那么就模一下表的空间大小
        hashi = (hash0 + i) % _tables.size();
        ++i;
        //二次探测
        /*hashi = (hash0 + (i*i*flag)) % _tables.size();
        if (hashi < _tables.size()) hashi += _tables.size();
        if (flag == 1) {
            flag = -1;
        } else {
            ++i;
            flag = 1;
        }*/
    }
    //当遇到空的位置就插入
    _tables[hashi].kv = kv;
    _tables[hashi]._state = EXIST;//将插入的位置标记为存在
    ++_n;
    return true;
}

2.4 查找

HashData<K, V>* Find(const K& key) {
    Hash hash;
    size_t hash0 = hash(key) % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    while (_tables[hashi]._state != EMPTY) {
        if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
            && _tables[hashi]._kv.first == key) {
            return &_tables[hashi];
        }
        // 线性探测
        hashi = (hash0 + i) % _tables.size();
        ++i;
    }
    return nullptr;
}

2.5 删除

删除只用改变位置状态就可以了。

bool Erase(const K& key) {
    HashData<K, V>* ret = Find(key);
    if (ret) {
        ret->_state = DELETE;
        return true;
    } else {
        return false;
    }
}

2.6 闭散列代码

//定义一个枚举来记录数组的三个状态
enum State { EXIST,//存在 EMPTY,//空 DELETE//删除 };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;//状态为空
};
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};
/* 1. 将 string 类型转换成无符号整形 (BKDR_Hash)
   2. 字符串转换成整形，可以把字符 ascii 码相加即可
   3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
   4. 这里我们使用 BKDR 哈希的思路，用上次的计算结果去 乘以一个质数，这个质数一般去 31, 131 等效果会比较好 */
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        // BKDR
        size_t hash = 0;
        for (auto ch : s) {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};

inline unsigned long __stl_next_prime(unsigned long n) {
    // Note: assumes long is at least 32 bits.
    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
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

namespace open_address//开发定址法
{
    //加上一个仿函数 Hash，用于转换成为无符号整形
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    public:
        HashTable() :_tables(__stl_next_prime(0))//给一个 0 去获取>=0 的素数
            , _n(0)//数据个数 {}

        bool Insert(const pair<K, V>& kv) {
            //如果值已经存在
            if (Find(kv.first)) return false;
            //扩容
            // 负载因子 >= 0.7 扩容 n/m 数据个数/表的空间大小
            //为了方便计算分子 n*10
            if (_n * 10 / _tables.size() >= 7) {
                //创建一个新的哈希表 newht 哈希表里本来就有 vector
                HashTable<K, V> newht;
                //*2 是无法一直保持素数的
                //newht._tables.resize(_tables.size() * 2);
                //使用素数表来获取比素数表的值大一点的值
                newht._tables.resize(__stl_next_prime(_tables.size() + 1));
                for (auto& data : _tables) {
                    // 遍历旧表，旧表的数据映射到新表
                    if (data._state == EXIST) {
                        //使用新对象去调用插入，把旧表的数据插入到新表
                        newht.Insert(data._kv);
                    }
                }
                //交换新旧表的空间
                _tables.swap(newht._tables);
            }
            Hash hash;//仿函数，用于转换成为无符号整形
            //插入值之后从起始位置 hash0 去用插入的值对表的大小取模算出值对应的位置
            size_t hash0 = hash(kv.first) % _tables.size();//hash0 是第一次算出来的位置
            size_t hashi = hash0;
            size_t i = 1;
            int flag = 1;
            while (_tables[hashi]._state == EXIST)//如果 hashi 的状态为存在
            {
                //进行线性探测
                //如果到达表的最后一个位置那么就模一下表的空间大小
                hashi = (hash0 + i) % _tables.size();
                ++i;
                //二次探测
                /*hashi = (hash0 + (i*i*flag)) % _tables.size();
                if (hashi < _tables.size()) hashi += _tables.size();
                if (flag == 1) {
                    flag = -1;
                } else {
                    ++i;
                    flag = 1;
                }*/
            }
            //当遇到空的位置就插入
            _tables[hashi].kv = kv;
            _tables[hashi]._state = EXIST;//将插入的位置标记为存在
            ++_n;
            return true;
        }

        HashData<K, V>* Find(const K& key) {
            Hash hash;
            size_t hash0 = hash(key) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state != EMPTY) {
                if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
                    && _tables[hashi]._kv.first == key) {
                    return &_tables[hashi];
                }
                // 线性探测
                hashi = (hash0 + i) % _tables.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            auto* ret = Find(key);
            if (ret) {
                ret->_state = DELETE;
                return true;
            }
            return false;
        }

    private:
        vector<HashData<K, V>> _tables;//表的空间大小
        size_t _n; // 记录数据个数
    };
}

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;
    }
};
/* 1. 将 string 类型转换成无符号整形 (BKDR_Hash)
   2. 字符串转换成整形，可以把字符 ascii 码相加即可
   3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
   4. 这里我们使用 BKDR 哈希的思路，用上次的计算结果去 乘以一个质数，这个质数一般去 31, 131 等效果会比较好 */
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        // BKDR
        size_t hash = 0;
        for (auto ch : s) {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};

4. 链地址法（开散列/哈希桶）

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

演示 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到 M=11 的表中 h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1,h(24) = 2,h(96) = 88

4.1 链地址法的基础框架

namespace hash_bucket//哈希桶
{
    template<class K, class V>
    struct HashNode//给一个节点用来挂节点
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
        //构造
        HashTable() :_tables(11), _n(0) {}
    private:
        vector<Node*> _tables; // 指针数组
        size_t _n = 0;// 表中存储数据个数
    };
}

4.2 插入

bool Insert(const pair<K, V>& kv) {
    Hash hs;
    size_t hashi = kv.first % _tables.size();
    // 头插
    //让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
    Node* newnode = new Node(kv);//创建一个新节点 new Node
    //将新节点的下一个节点指向原来的第一个节点的地址
    //第一个节点的地址在哈希表里
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;//再把新节点给与_tables[hashi] 里存储的指针
    ++_n;
    return true;
}

4.3 扩容

开放定址法负载因子必须小于 1，链地址法的负载因子就没有限制了，可以大于 1。 负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。

// 负载因子 == 1 时扩容
if (_n == _tables.size()) {
    vector<Node*> newTatble(_tables.size() * 2);
    //遍历旧表
    for (size_t i = 0; i < _tables.size(); i++) {
        Node* cur = _tables[i];
        while (cur) {
            Node* next = cur->_next;
            // 旧表数据头插到新表
            size_t hashi = cur->_kv.first % newTatble.size();
            cur->_next = newTatble[hashi];
            newTatble[hashi] = cur;
            cur = next;
        }
        //交换
        _tables[i] = nullptr;
    }
    _tables.swap(newTatble);
}

4.4 查找

Node* Find(const K& key) {
    Hash hash;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            return &cur->_kv.first;
        } else {
            cur = cur->_next;
        }
    }
    return nullptr;
}

4.5 删除

两种情况：一种是删除第一个节点，另一种是删除其他节点 prev->_next = cur->_next。 在删除节点需要前后兼顾，保存下前驱指针指向节点。

bool Erase(const K& key) {
    Hash hash;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _tables[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;
            return true;
        } else {
            prev = cur;
            cur = cur->_next;
        }
    }
    return false;
}

4.6 开散列代码

namespace hash_bucket//哈希桶
{
    template<class K, class V>
    struct HashNode//给一个节点用来挂节点
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
        //构造
        HashTable() :_tables(11), _n(0) {}

        bool Insert(const pair<K, V>& kv) {
            // 负载因子 == 1 时扩容
            if (_n == _tables.size()) {
                vector<Node*> newTatble(_tables.size() * 2);
                //遍历旧表
                for (size_t i = 0; i < _tables.size(); i++) {
                    Node* cur = _tables[i];
                    while (cur) {
                        Node* next = cur->_next;
                        // 旧表数据头插到新表
                        size_t hashi = cur->_kv.first % newTatble.size();
                        cur->_next = newTatble[hashi];
                        newTatble[hashi] = cur;
                        cur = next;
                    }
                    //交换
                    _tables[i] = nullptr;
                }
                _tables.swap(newTatble);
            }
            size_t hashi = kv.first % _tables.size();
            // 头插
            //让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
            Node* newnode = new Node(kv);//创建一个新节点 new Node
            //将新节点的下一个节点指向原来的第一个节点的地址
            //第一个节点的地址在哈希表里
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;//再把新节点给与_tables[hashi] 里存储的指针
            ++_n;
            return true;
        }

        Node* Find(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur) {
                if (cur->_kv.first == key) {
                    return &cur->_kv.first;
                } else {
                    cur = cur->_next;
                }
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            Node* prev = nullptr;
            while (cur) {
                if (cur->_kv.first == key) {
                    if (prev == nullptr) {
                        _tables[hashi] = cur->_next;
                    } else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                } else {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

    private:
        vector<Node*> _tables; // 指针数组
        size_t _n = 0;// 表中存储数据个数
    };
}