C++ 哈希表原理与 unordered 容器实战

unordered_multiset / unordered_multimap

这两个容器与 multiset/multimap 类似，主要区别在于支持 Key 冗余。其他特性如底层结构、迭代器行为等与上述单值版本一致。

哈希概念

哈希（Hash）又称散列，是一种组织数据的方式。本质是通过哈希函数将关键字 Key 与存储位置建立映射关系。查找时，通过哈希函数计算出 Key 对应的存储位置，从而实现快速查找。

直接定址法

当关键字范围集中时，例如一组关键字都在 [0, 99] 之间，可以直接开一个 100 个元素的数组，每个关键字的值直接作为存储位置的下标。对于字符类型，如 [a, z]，可开 26 个元素的数组，下标为 ASCII 码 - 'a'。

直接定址法的本质是用关键字计算出一个绝对或相对位置（如计数排序）。但当关键字范围分散时，这种方法会浪费大量内存甚至导致内存不足。

哈希冲突

假设我们只有 N 个数据，要映射到 M 个空间的数组中（一般 M >= N），需借助哈希函数 h(x)。关键字 key 被放到数组的 h(key) 位置，注意 h(key) 必须在 [0, M) 之间。

这里存在一个问题：两个不同的 Key 可能会映射到同一个位置，这就是哈希冲突（Collision）。理想情况是找出完美哈希函数避免冲突，但实际场景中冲突不可避免。我们需要设计优秀的哈希函数减少冲突次数，同时制定解决冲突的方案。

负载因子

假设哈希表中已存储 N 个值，大小为 M，则 负载因子 = N/M。

• 负载因子越大，哈希冲突概率越高，空间利用率越高。
• 负载因子越小，哈希冲突概率越低，空间利用率越低。

将关键字转为 size_t

为了映射到数组位置，通常需要将关键字转为整数。源码中常用仿函数 Hash 将 Key 转换成 size_t。如果遇到 string、Date 等非数值类型无法强转的情况，需要自己实现特化模板。

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

template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto& e : s) {
            // 有效避免 "abcd" 与 "bcad" 冲突
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

哈希函数

一个好的哈希函数应让 N 个关键字被等概率且均匀地散列分布到哈希表的 M 个空间中。虽然很难做到完美，但设计时应尽量往这个方向考量。

除法散列法（除留余数法）

假设哈希表大小为 M，key 除以 M 的余数作为映射位置下标，即 h(key) = key % M。

使用除法散列法时，要避免 M 取某些特定值，如 2 的幂或 10 的幂。如果是 2^x，key % 2^x 相当于保留 key 的二进制后 x 位，后 x 位相同的值哈希值相同，导致冲突。同理，10^x 会保留十进制后 x 位。

建议 M 取不太接近 2 的整数次幂的一个素数。

SGI 版本的哈希表使用了一个近似 2 倍扩容的素数表：

inline unsigned long __stl_next_prime(unsigned long n) {
    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;
}

初始时哈希表大小 M 可为 __stl_next_prime(0)，即 M=53。扩容后 M=97，实现了近似 2 倍扩容且不接近 2 的幂。

处理哈希冲突：开放定址法

在开放定址法中，所有元素都放入哈希表。当关键字 key 计算出的位置发生冲突时，按照某种规则寻找下一个未存储数据的位置。规则主要有三种：线性探测、二次探测、双重探测。此方法要求负载因子小于 1。

线性探测

1. 从发生冲突的位置开始，依次线性向后探测，直到找到空位置。若走到表尾则回绕到表头。
2. 公式：hc(key, i) = (hash0 + i) % M，其中 hash0 = key % M，i = {1, 2, ..., M-1}。
3. 如果 hash0 位置连续冲突，后续映射到该区域的值都会争夺下一个空位，这种现象叫群集（Clustering）。二次探测可在一定程度上改善。

二次探测

1. 从冲突位置开始，左右按二次方跳跃式探测，直到找到空位置。若越界则回绕。
2. 公式：hc(key, i) = (hash0 ± i²) % M，i = {1, 2, ..., M/2}。
3. 若 (hash0 - i²) % M 结果为负，需加 M 修正。

开放定址法线性探测代码实现

给每个存储位置增加状态标识至关重要，否则删除数据后会影响后续冲突值的查找。例如删除 30，查找 20，若求得下标为 9 且为空，直接返回未找到，但实际上 20 可能在后面。因此需引入状态：{EXIST, DELETE, EMPTY}。

• 查找 key，若位置状态为 EMPTY，说明整个表中无 key。
• 若为 EXIST 或 DELETE，继续探测。

控制负载因子到 0.7 时进行扩容。

#include <vector>
#include <string>
#include <utility>
using namespace std;

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

template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto& e : s) {
            hash += e;
            hash *= 131;
        }
        return hash;
    }
};

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

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        if (_n * 10 / _tables.size() >= 7) { // 扩容
            HashTable<K, V, Hash> newht;
            newht._tables.resize(__stl_next_prime(_tables.size() + 1));
            for (auto& e : _tables) {
                if (e._state == EXIST) newht.Insert(e._kv);
            }
            _tables.swap(newht._tables);
        }
        Hash hash;
        size_t hash0 = hash(kv.first) % _tables.size();
        size_t hashi = hash0;
        size_t i = 1;
        while (_tables[hashi]._state == EXIST) {
            hashi = (hash0 + i) % _tables.size();
            i++;
        }
        _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) {
        HashData<K, V>* ret = Find(key);
        if (ret) {
            ret->_state = DELETE;
            return true;
        }
        return false;
    }

private:
    vector<HashData<K, V>> _tables;
    size_t _n; // 记录数据个数
};
}

测试验证：

#include "HashTable.h"
int main() {
    open_address::HashTable<int, int> ht;
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12};
    for (auto e : a) {
        ht.Insert({e, e});
    }
    if (ht.Find(13)) ht.Erase(13);
    else cout << "没找到" << endl;
    return 0;
}

若 Key 为日期类，需自定义仿函数：

struct Date {
    int _year, _month, _day;
    Date(int year = 1, int month = 1, int day = 1)
        : _year(year), _month(month), _day(day) {}
    bool operator==(const Date& d) {
        return _year == d._year && _month == d._month && _day == d._day;
    }
};

struct DateHashFunc {
    size_t operator()(const Date& d) {
        size_t hash = 0;
        hash += d._year; hash *= 131;
        hash += d._month; hash *= 131;
        hash += d._day; hash *= 131;
        return hash;
    }
};

int main() {
    open_address::HashTable<Date, int, DateHashFunc> ht2;
    ht2.Insert({{2026, 1, 2}, 1});
    ht2.Insert({{2026, 2, 1}, 2});
    return 0;
}

处理哈希冲突：链地址法

开放定址法将所有元素放入哈希表，而链地址法（拉链法/哈希桶）中，哈希表只存指针。若无数据映射，指针为空；若有多个数据映射到同一位置，则链接成链表挂在下面。

链地址法对负载因子无严格要求，通常控制在 1。若某个桶过长（如长度大于 8），可将链表转为红黑树以提升性能。

代码实现

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(__stl_next_prime(0)), _n(0) {}

    // 拷贝构造
    HashTable(const HashTable<K, V, Hash>& ht) {
        _tables.resize(ht._tables.size());
        for (int i = 0; i < ht._tables.size(); i++) {
            Node* htcur = ht._tables[i];
            while (htcur) {
                Node* newnode = new Node(htcur->_kv);
                Node* cur = _tables[i];
                if (cur == nullptr)
                    _tables[i] = newnode;
                else {
                    while (cur->_next) cur = cur->_next;
                    cur->_next = newnode;
                }
                htcur = htcur->_next;
            }
        }
        _n = ht._n;
    }

    ~HashTable() {
        for (int i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
    }

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        Hash hash;
        if (_n == _tables.size()) { // 扩容
            vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
            for (int i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    size_t hashi = hash(cur->_kv.first) % newTable.size();
                    // 头插
                    cur->_next = newTable[hashi];
                    newTable[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newTable);
        }
        size_t hashi = hash(kv.first) % _tables.size();
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_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;
            cur = cur->_next;
        }
        return nullptr;
    }

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

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

测试：

int main() {
    int a[] = {19, 30, 5, 36, 13, 20, 21, 12, 24, 96};
    hash_bucket::HashTable<int, int> ht;
    for (auto& e : a) ht.Insert({e, e});
    ht.Insert({100, 100});
    ht.Insert({101, 101});
    cout << ht.Find(19) << endl;
    cout << ht.Find(36) << endl;
    cout << ht.Find(96) << endl;
    cout << ht.Find(101) << endl << endl;
    ht.Erase(19); ht.Erase(36); ht.Erase(96); ht.Erase(101);
    cout << ht.Find(19) << endl;
    cout << ht.Find(36) << endl;
    cout << ht.Find(96) << endl;
    cout << ht.Find(101) << endl << endl;
    return 0;
}

哈希表封装 unordered_set 和 unordered_map

与红黑树封装 set/map 类似，HashTable 也实现了泛型。其中 HashTable 用链地址法实现，仿函数 KeyOfT 取出 T 类型对象的 Key，仿函数 Hash 转为 size_t。

代码实现

// UnorderedSet.h
#include "HashTable.h"
namespace mine {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
public:
    typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

    iterator begin() { return _ht.Begin(); }
    iterator end() { return _ht.End(); }
    const_iterator begin() const { return _ht.Begin(); }
    const_iterator end() const { return _ht.End(); }

    pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
    iterator find(const K& key) { return _ht.Find(key); }
    bool erase(const K& key) { return _ht.Erase(key); }

private:
    hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};

void print(const unordered_set<int>& us) {
    unordered_set<int>::const_iterator cit = us.begin();
    while (cit != us.end()) {
        cout << *cit << " ";
        ++cit;
    }
    cout << endl;
}
}

测试 mine::unordered_set：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "UnorderedSet.h"

int main() {
    int a[] = {3, 11, 86, 7, 88, 82, 1, 881, 5, 6, 7, 6};
    mine::unordered_set<int> us;
    for (auto e : a) us.insert(e);
    auto it = us.begin();
    while (it != us.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    mine::print(us);
    return 0;
}

unordered_map 封装

// UnorderedMap.h
#include "HashTable.h"
namespace mine {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) { return kv.first; }
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

    iterator begin() { return _ht.Begin(); }
    iterator end() { return _ht.End(); }
    const_iterator begin() const { return _ht.Begin(); }
    const_iterator end() const { return _ht.End(); }

    V& operator[](const K& key) {
        auto ret = insert({key, V()});
        return ret.first->second;
    }
    pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
    iterator find(const K& key) { return _ht.Find(key); }
    bool erase(const K& key) { return _ht.Erase(key); }

private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};

void print(const unordered_map<string, string>& um) {
    unordered_map<string, string>::const_iterator cit = um.begin();
    while (cit != um.end()) {
        cout << cit->first << ":" << cit->second << endl;
        ++cit;
    }
    cout << endl;
}
}

测试 mine::unordered_map：

int main() {
    mine::unordered_map<string, string> dict;
    dict.insert({"sort", "排序"});
    dict.insert({"字符串", "string"});
    dict.insert({"left", "左"});
    dict.insert({"right", "右"});
    for (auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    dict["left"] = "左，剩余";
    dict["insert"] = "插入";
    dict["string"];
    auto it = dict.begin();
    while (it != dict.end()) {
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;
    mine::print(dict);
    return 0;
}

将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online