C++ 哈希表底层原理与实现：从散列函数到冲突处理

扩容优化

上面的实现并不是那么好。如果当映射的元素 _n / _tables.size() 大于负载因子时，显然是需要扩容的。如果选择 2 倍扩容，原本的 11 空间变为 22 空间，看似没有毛病。但前面我们说过，使用除法散列法时，要避免 M 为 2 的整数次幂。因此，不能直接地选择 2 倍扩容的方式来放大空间。

代码该如何实现呢？

1. 提前造好一些数据：这些数据得保证是质数，且是不太接近 2 的整数次幂的一个质数。
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;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

在上面这段程序中，哈希表默认初始空间是 28（实际上通常取列表中的第一个有效值或特定值），当大于负载因子时进行扩容，第一次扩容是 53，第二次是 97……可以发现，每次扩容都是以近乎 2 倍扩容且满足不太接近 2 的整数次幂的一个质数。这种手动造数据的方法看似笨拙，实则这是利用其特性下的一种取巧。

线性探测

• 在映射数据的时候可能会存在哈希冲突，此时从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止。如果走到哈希表尾，则回绕到哈希表头的位置。
• $h(key) = hash0 = key % M$，hash0 位置冲突了，则线性探测公式为：$hc(key, i) = hashi = (hash0 + i) % M$，$i = {1, 2, 3, ..., M - 1}$。保证线性探测时能从队尾走到队头，且因为负载因子小于 1，则最多探测 M-1 次，一定能找到一个存储 key 的位置。

可以发现线性探测的问题会占用其他值可能映射到的空间，会导致原本不冲突的值产生哈希冲突。严重的话可能会使多个 hash0、hash1、hash2、hash3 的值都争夺 hash3 位置，这种现象叫做群集/堆积。

线性探测实现

bool Insert(const pair<K, V>& kv) {
    // 扩容 --> 负载因子大于 0.7
    if ((double)_n / (double)_tables.size() > 0.7) {
        HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1));
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]._status == EXIST) {
                newHT.Insert(_tables[i]._kv);
            }
        }
        _tables.swap(newHT._tables);
    }

    size_t hash0 = kv.first % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    
    // 如果该点存在 --> 线性探测
    while (_tables[hashi]._status != EMPTY) {
        if (_tables[hashi]._status == EXIST && _tables[hashi]._kv.first == kv.first) {
            _tables[hashi]._kv = kv;
            return true;
        }
        hashi = (hashi + i) % _tables.size();
        i++;
    }
    
    _tables[hashi]._kv = kv;
    _tables[hashi]._status = EXIST;
    ++_n;
    return true;
}

查找和删除

• 查找规律：巧妙利用线性探测的特性，遇到 EMPTY 停止，遇到 DELETE 继续。
• 删除规律：采用 Find 函数寻找该值是否存在，如果存在标记为 DELETE，返回 true；否则，返回 false。

完整代码实现

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;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

enum Status { EMPTY, EXIST, DELETE };

template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    Status _status = EMPTY;
};

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size), _n(0) {}

    bool Insert(const pair<K, V>& kv) {
        // 扩容 --> 负载因子大于 0.7
        if ((double)_n / (double)_tables.size() > 0.7) {
            HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1));
            for (size_t i = 0; i < _tables.size(); i++) {
                if (_tables[i]._status == EXIST) {
                    newHT.Insert(_tables[i]._kv);
                }
            }
            _tables.swap(newHT._tables);
        }

        size_t hash0 = kv.first % _tables.size();
        size_t hashi = hash0;
        size_t i = 1;
        // 如果该点存在 --> 线性探测
        while (_tables[hashi]._status != EMPTY) {
            if (_tables[hashi]._status == EXIST && _tables[hashi]._kv.first == kv.first) {
                _tables[hashi]._kv = kv;
                return true;
            }
            hashi = (hashi + i) % _tables.size();
            i++;
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._status = EXIST;
        ++_n;
        return true;
    }

    HashData<K, V>* Find(const K& key) {
        size_t hash0 = key % _tables.size();
        size_t hash1 = hash0;
        size_t i = 1;
        while (_tables[hash1]._status != EMPTY) {
            if (_tables[hash1]._kv.first == key && _tables[hash1]._status != DELETE) {
                return &_tables[hash1];
            }
            hash1 = (hash1 + i) % _tables.size();
            ++i;
        }
        return nullptr;
    }

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

private:
    vector<HashData<K, V>> _tables;
    size_t _n;
};

链地址法

开放定址法无论怎样势必会造成哈希冲突，因其占用的都是哈希表中的空间，始终存在互相影响问题。那如何解决这种弊端呢？链地址法为了解决这种冲突，不是再将所有的数据直接存储在哈希表中，而是通过指针的方式让每一个值都映射到对应空间，即使产生冲突会用指针的方式将它们悬挂起来，挂在哈希表该位置下面。当然我们形象地称这种方法为拉链法或哈希桶。

但是在一些极端场景下，如有人恶意造出一段数据让它都映射到同一个位置，导致某个桶特别长，查询时间复杂度达到了 O(N)。有大佬提出，如果这个桶的长度超过一定阈值(8) 时就把链表转换成红黑树。（用全域散列法也可）

链地址法的结构实现

// 手动造数据见上面
template<class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_next(nullptr), _kv(kv) {}
};

template<class K, class V>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr), _n(0) {}
private:
    vector<Node*> _tables;
    size_t _n;
};

特殊情况：插入元素不是数字

如果插入元素是浮点数、负数情况呢？仿函数的作用再次体现出来了。无论是整数、浮点数、负数，统一强转成正数来处理，找到该映射的位置，对查找、删除等操作都不会受到影响，因为我们同样需要将目标值强制转成正数映射到对应位置。

// 仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // --> 针对浮点、负数等情况
    }
};

针对字符串

但是字符串的处理，并不能直接强转成正数来处理，这并不被允许。因此，在这里采用特化的思想进行特殊处理，实现如下。

// 针对字符串
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash0 = 0;
        for (auto& ch : key) {
            // 对不同字符串但 hash0 相同的处理，减少冲突
            hash0 *= 131;
            hash0 += ch;
        }
        return hash0;
    }
};

改动

template<class K, class V, class Hash = HashFunc<K>>

扩容

开放定址法负载因子必须小于 1，链地址法的负载因子就没有限制了。在 STL 中的实现最大负载因子基本控制在 1，大于 1 就扩容，我们同样采用此逻辑进行扩容。扩容操作时，开一个新的哈希表，需要将旧表上的值都重新映射到新表中。

1. 方法一：由于是链地址法的实现，一个位置下可能会挂着多个值（即哈希桶），那么就需要遍历该位置中桶的每个结点，将每个结点的值重新映射到新表中，而每次操作都需要申请新结点，并把旧表中该结点释放掉。显然，这种方式是非常浪费的，且效率非常低效。
2. 方法二：正是由于采用的是链地址法的实现，由于哈希表中每个位置都是一个指针，那么我们只需要遍历旧表中结点映射在新表中的位置，使其指向旧表中该结点。最后，将旧表置为空，交换新旧链表，完成扩容操作。

bool Insert(const pair<K, V>& kv) {
    // 不允许冗余
    if (Find(kv.first)) return false;
    Hash hs;
    // 需要扩容
    if (_n == _tables.size()) {
        /* 也可以，但是扩容新开辟节点，释放旧节点，有点浪费
        HashTable<K, V> newHT(__stl_next_prime(_tables.size() + 1));
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                newHT.Insert(cur->_kv);
                cur = cur->_next;
            }
        }
        _tables.swap(newHT._tables);*/
        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 hash0 = hs(cur->_kv.first) % newtables.size();
                cur->_next = newtables[hash0];
                newtables[hash0] = cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newtables);
    }
    size_t hash0 = hs(kv.first) % _tables.size();
    Node* newnode = new Node(kv);
    // 头插
    newnode->_next = _tables[hash0];
    _tables[hash0] = newnode;
    ++_n;
    return true;
}

删除

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

完整代码实现

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;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

template<class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_next(nullptr), _kv(kv) {}
};

// 仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // --> 针对浮点、负数等情况
    }
};

// 针对字符串
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash0 = 0;
        for (auto& ch : key) {
            // 对不同字符串但 hash0 相同的处理，减少冲突
            hash0 *= 131;
            hash0 += ch;
        }
        return hash0;
    }
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr), _n(0) {}

    bool Insert(const pair<K, V>& kv) {
        // 不允许冗余
        if (Find(kv.first)) return false;
        Hash hs;
        // 需要扩容
        if (_n == _tables.size()) {
            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 hash0 = hs(cur->_kv.first) % newtables.size();
                    cur->_next = newtables[hash0];
                    newtables[hash0] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hash0 = hs(kv.first) % _tables.size();
        Node* newnode = new Node(kv);
        // 头插
        newnode->_next = _tables[hash0];
        _tables[hash0] = newnode;
        ++_n;
        return true;
    }

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

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

    ~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;
        }
    }

private:
    vector<Node*> _tables;
    size_t _n;
};