---

前言

哈希表（Hash Table）是数据结构中查找效率最高的结构之一，其时间复杂度平均可以达到 O(1)。本文将从基础概念到实际代码实现，系统地讲解哈希表的实现原理及在 C++ 中的应用。

---

一、哈希的基本概念

1.1 什么是哈希（Hash）

哈希（Hash），又称散列，是一种通过 哈希函数（Hash Function）将关键字 key 映射到数组下标位置的技术，从而实现快速查找。

举个例子：

• 假设关键字范围在 [0, 99]，我们可以直接开一个 100 大小的数组，关键字值即为存储下标。
• 对于字符串 [a, z]，我们可以使用 ch - 'a' 作为索引。

这种方式被称为 直接定址法（Direct Addressing），非常高效，但仅适用于关键字范围较小的情况。

示例：
LeetCode 第 387 题「字符串中的第一个唯一字符」

int firstUniqChar(string s) {
    int count[26] = {0};
    for (auto ch : s)
        count[ch - 'a']++;

    for (int i = 0; i < s.size(); ++i)
        if (count[s[i] - 'a'] == 1)
            return i;

    return -1;
}

---

1.2 哈希冲突（Hash Collision）

哈希函数将 key 映射到 [0, M) 范围的下标。
但当两个不同的 key 经过哈希函数计算后得到相同位置时，就会发生哈希冲突（collision）。

冲突是不可避免的，因此我们需要设计：

• 尽量减少冲突的哈希函数；
• 有效的冲突解决策略。

---

1.3 负载因子（Load Factor）

负载因子定义为：

[
\alpha = \frac{N}{M}
]

其中：

• N 为哈希表中存储的元素个数；
• M 为哈希表总的槽位数。

影响：

• 负载因子越大 → 空间利用率高，但冲突概率上升；
• 负载因子越小 → 查找更快，但浪费空间。

一般情况下，α 控制在 0.7 左右。

---

1.4 关键字的整数化

哈希函数的输入必须是整数。
当 key 为字符串、日期等非整型时，需要将其转换为整数，这通常通过字符串哈希（如 BKDR 算法）实现。

---

二、常见哈希函数设计

2.1 除法散列法

定义：

[
h(key) = key % M
]

• 优点：简单直观；
• 缺点：若 M 为 2 或 10 的幂，会造成高位信息丢失，导致冲突集中。

优化建议：
选择一个不接近 2 的整数幂的质数作为 M，例如 97、193、389 等。

实践说明：Java 的 HashMap 实际使用 2 的幂作为 M，但通过异或混合高低位来改善均匀性。

---

2.2 乘法散列法

[
h(key) = \lfloor M \times ((A \times key) \mod 1.0) \rfloor
]

其中 A 为常数，一般取黄金分割点：
[
A = 0.6180339887…
]

不受 M 限制，适合某些特殊场景。

---

2.3 全域散列法

用于防止被恶意攻击（如让所有 key 冲突）。
定义：

[
h_{a,b}(key) = ((a \times key + b) % P) % M
]

• P 为质数；
• a ∈ [1, P-1]，b ∈ [0, P-1]；
• 每次随机选择不同的 (a,b) 组合。

可显著降低恶意冲突风险。

---

三、哈希冲突的解决策略

哈希冲突的处理主要有两类：

1. 开放定址法（Open Addressing）
2. 链地址法（Separate Chaining）

---

3.1 开放定址法

当冲突发生时，继续在表中寻找下一个空位置存储元素。

（1）线性探测（Linear Probing）

[
h_i = (h_0 + i) % M
]

依次向后探测，若到表尾则回绕到开头。
缺点：容易形成“堆积”（群集现象）。

（2）二次探测（Quadratic Probing）

[
h_i = (h_0 \pm i^2) % M
]

探测距离呈平方增长，减轻群集问题。

（3）双重哈希（Double Hashing）

[
h_i = (h_0 + i \times h_2(key)) % M
]

两个哈希函数联合使用，效果最好但实现较复杂。

---

3.2 开放定址法的实现

哈希表结构定义

enum State { EXIST, EMPTY, DELETE };

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

HashFunc 仿函数

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

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

插入、查找与删除

使用线性探测：

while (_tables[hashi]._state == EXIST)
    hashi = (hash0 + i++) % _tables.size();

删除时标记为 DELETE，而非清空数据，以免影响后续查找。

扩容机制

当负载因子超过 0.7 时扩容，扩容后大小取下一个质数：

static const unsigned long primes[] = {
    53, 97, 193, 389, 769, 1543, ...
};

---

3.3 链地址法（拉链法）

思路：

• 哈希表的每个槽位存储一个链表；
• 当多个 key 映射到相同位置时，将其插入该链表。

示意图（ASCII）：

哈希表：
0 → [ ]
1 → [12] → [24]
2 → [13]
3 → [36]
4 → [ ] 
...

优点：

• 实现简单；
• 不受负载因子 < 1 限制；
• 删除操作容易。

缺点：

• 需要额外指针空间；
• 极端情况下链表可能过长。

---

链地址法 C++ 实现（源代码下载）

个人实现的哈希表源代码免费下载：
C++使用链式地址法实现的哈希表HashTable头文件源代码，可用于作为unordered-set和unordered-map的底层容器
我设置的是0积分免费下载，如果变成付费的话，懂的都懂

结构实现

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

插入操作使用头插法：

Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;

删除时调整指针，避免内存泄漏。

扩容时可直接迁移旧节点，无需重新分配，效率更高。

---

极端场景与优化

在极端情况下，某个桶过长时查找效率会退化为 O(n)。
Java 8 中的 HashMap 在链表长度超过 8 时，会自动将该桶转换为红黑树，提高性能。

---

四、总结与实践建议

方法	优点	缺点	使用场景
开放定址法	内存连续，cache友好	删除复杂，负载受限	小规模表
链地址法	删除方便，负载自由	指针开销大	大多数场景
双重哈希	减少冲突	实现复杂	高性能场景

实践建议：

• 实际工程中直接使用 std::unordered_map；
• 若需自定义哈希函数，可通过仿函数 HashFunc；
• 对字符串建议采用 BKDR 或 MurmurHash 等算法。

---

结语

哈希表作为最经典的数据结构之一，是理解 STL 容器底层实现（unordered_map, unordered_set）的关键。
掌握哈希表的底层实现，不仅能帮助你理解 STL 工作机制，更能在算法竞赛与工程开发中写出高效的代码。

---

免责声明

本文内容仅供学习与参考，作者不对因使用本文内容而导致的任何后果承担责任。

封面图来源于网络，如有侵权，请联系删除！