哈希表核心原理与 C++ 实战实现

哈希概念

哈希（Hash），又称散列，本质上是一种组织数据的方式。它的核心思想是通过哈希函数建立关键字 Key 与存储位置之间的映射关系。查找时，只需通过同样的哈希函数计算出 Key 对应的存储位置，即可快速定位数据。

基于这种映射思想，数据结构中实现了哈希表（散列表）。需要注意的是，哈希是一种思想，而哈希表是实现该思想的特定数据结构，二者不能简单等同。

哈希冲突与哈希函数

假设我们要将 N 个值映射到大小为 M 的数组中（通常 M >= N），就需要借助好的映射方法，使关键字 key 被放到数组的 h(key) 位置。这里必须保证 h(key) 的计算结果在 [0, M) 之间。

一个不可避免的问题是，两个不同的 key 可能会映射到同一个位置，这就是哈希冲突（或哈希碰撞）。我们将数据与存储位置之间的映射表达式称为哈希函数（hash function）。一个好的哈希函数应让 N 个关键字等概率、均匀地散列分布到哈希表的 M 个空间中。虽然实际中很难做到完美的等概率，但设计时应尽量往这个方向靠拢。

负载因子

假设哈希表中已存储了 N 个值，哈希表大小为 M，那么 N/M 就是负载因子（Load Factor）。

负载因子越大，哈希冲突的概率越高，但空间利用率也越高；反之，负载因子越小，冲突概率越低，但空间浪费越多。在实际工程中，我们需要在冲突率和空间占用之间寻找平衡点。

关键字转为整数

哈希函数的计算通常基于整型。如果关键字不是整型（例如字符串），我们需要想办法将其转换为整型。这一细节将在后续代码实现中展示。讨论哈希函数时，若关键字非整数，文中的 Key 均指转换后的整数值。

哈希函数设计

在实际应用中，我们根据具体场景确定如何映射。为了后续能准确找到数据，插入、查找等一系列过程必须使用同一个哈希函数，中途不能更改，否则会导致前后不一致。

直接定址法

当关键字范围比较集中时，直接定址法非常高效。例如关键字都在 [0, 99] 之间，可以直接开一个 100 个元素的数组，每个关键字的值直接作为下标。

对于字符类型，比如小写字母 [a, z]，可以开一个 26 个元素的数组，利用 ascii 码 - 'a' 的差值作为相对位置。这本质是用关键字计算出绝对或相对位置。这种方法在计数排序和某些字符串处理场景中很常见。

缺点也很明显：如果关键字范围分散（例如最大值与最小值差值达 10 亿，但只有 20 个数据），直接开辟大数组会极度浪费内存甚至导致内存不足。对于分散数据，需采用其他映射方式。

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

这是最常用的方法之一。假设哈希表大小为 M，哈希函数为：h(key) = key % M。

注意事项：

1. 尽量避免 M 取 2 的幂或 10 的幂。如果是 2 的幂，key % M 相当于保留二进制后 X 位，若低位相同则冲突严重。
2. 建议 M 取不太接近 2 的整数次幂的质数。
3. 实践中也有例外，如 Java HashMap 采用 2 的幂做大小，配合位运算优化效率，并通过异或操作让高位参与计算来减少冲突。

总的来说，映射出的值仍在 [0, M) 范围内，关键是尽量让 key 的所有位都参与计算，使分布更均匀。

乘法散列法

对哈希表大小 M 没有严格要求。思路是：

1. 用关键字 K 乘以常数 A (0 < A < 1)，抽取小数部分。
2. 再用 M 乘以该小数部分并向下取整。

公式：h(key) = floor(M × ((A × key)%1.0))。 Knuth 建议 A 取黄金分割点相关值（约 0.618），实验表明这能使数据分布较均匀。

全域散列法

为了防止恶意攻击者针对确定的散列函数构造冲突数据集，可以给散列函数增加随机性。即从一组函数中随机选取一个使用，后续增删查改固定使用该函数。

公式示例：h(key) = ((a × key + b)%P )%M。其中 P 为大质数，a、b 随机选取。这样攻击者无法预先构造最坏情况的数据集。

处理哈希冲突

无论选择什么哈希函数，只要 M 小于数据量，冲突就不可避免。解决冲突主要有两种策略：开放定址法和链地址法。

开放定址法

所有元素都放入哈希表中。当发生冲突时，按某种规则寻找下一个空位存储。此方法要求负载因子严格小于 1。

线性探测

从冲突位置开始，依次向后探测，直到找到空位。若到达表尾则回绕到表头。

问题：容易产生'群集'现象。多个连续冲突的数据会抢占后续数据的存储位置，导致后续数据需要遍历更多空位才能找到存放处。因此实际中通常保持负载因子小于 0.7，超过则扩容。

开放定址法的结构与查找设计

由于删除操作会影响查找逻辑（直接清空位置会导致后续冲突数据无法被找到），我们需要给每个位置增加状态标识：EXIST（存在）、EMPTY（空）、DELETE（已删除）。查找时遇到 EMPTY 才停止，遇到 DELETE 则继续。

enum State { EXIST, EMPTY, DELETE };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;
};

仿函数与 Key 转换

当 Key 为 string 等非整型时，需要仿函数将其转换为可取模的整形。STL 的 unordered 系列针对 string 做了特化，我们实现时也可以自定义仿函数。常用的 BKDR 哈希思路是将字符串字符累加并乘上质数（如 31 或 131），以减少不同顺序字符串的冲突。

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认强转
    }
};

// 针对 string 的特化
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto e : key) {
            hash *= 131;
            hash += e;
        }
        return hash;
    }
};

插入、删除与扩容

插入时需检查是否已存在。若负载因子过高（如大于 0.7），需扩容。扩容通常将表大小翻倍，并将旧数据重新映射到新表。

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(_tables.size() * 2);
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]._state == EXIST) {
                newHT.Insert(_tables[i]._kv);
            }
        }
        _tables.swap(newHT._tables);
    }
    
    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();
    while (_tables[hashi]._state == EXIST) {
        ++hashi;
        hashi %= _tables.size();
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}

二次探测与双重散列

线性探测容易聚集，二次探测通过平方级跳跃（±i²）来缓解这一问题。双重散列则使用第二个哈希函数计算偏移量，进一步打乱探测序列。这两种方法都能在一定程度上改善堆积现象，但实现复杂度略高。

链地址法

开放定址法中所有元素竞争同一块空间，而链地址法（拉链法）将哈希表中的每个位置视为一个桶（Bucket）。若有多个数据映射到同一位置，则将这些数据链接成链表挂在下面。

结构设计与扩容

链地址法对负载因子限制较少，理论上可以大于 1。但因子过大导致链表过长，查找效率下降。通常控制在 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;
    vector<Node*> _tables;
    size_t _n = 0;
    
public:
    ~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;
        }
    }

    bool Insert(const pair<K, V>& kv) {
        Hash hs;
        size_t hashi = hs(kv.first) % _tables.size();
        
        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 newHashi = hs(cur->_kv.first) % newtables.size();
                    cur->_next = newtables[newHashi];
                    newtables[newHashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
            hashi = hs(kv.first) % _tables.size();
        }
        
        // 头插法
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }
    
    // Find 和 Erase 实现类似，遍历链表查找匹配项
    // ... (省略具体遍历代码)
};
} // namespace hash_bucket

极端场景处理

如果某个桶特别长，查找效率会急剧下降。Java 8 的 HashMap 引入了红黑树机制，当链表长度超过阈值（如 8）时将链表转为红黑树。当然，在一般工程实践中，合理控制负载因子和扩容策略，极少会遇到这种情况。