跳到主要内容C++ 哈希表详解：概念、哈希函数与冲突解决 | 极客日志C++算法
C++ 哈希表详解：概念、哈希函数与冲突解决
系统讲解 C++ 哈希表原理，涵盖哈希函数设计（直接定址、除留余数、多项式哈希等）、负载因子影响及冲突解决策略（开放寻址法中的线性/二次探测、链地址法）。包含完整 C++ 代码实现，涉及扩容质数选择、仿函数定制及节点管理，适合希望深入理解哈希表底层机制的开发者阅读。
SqlMaster1 浏览 
1. 哈希表的概念
哈希表（又称散列表）是一种基于「键值对（Key-Value）」存储的数据结构，其核心目标是通过哈希函数将「键（Key）」直接映射到对应的存储位置，从而实现 O(1) 级别的平均查找、插入和删除效率，是计算机科学中效率最高的数据结构之一。
1.1 哈希函数（Hash Function）
哈希函数是哈希表的核心组件，其本质是一个数学函数，作用是将「任意类型、任意长度的关键字（Key）」转换为「固定范围、可直接作为底层数组索引的整数（哈希值 / Hash Value）」，从而实现'通过 Key 快速定位存储位置'的目标。
1.2 哈希冲突（Hash Collision）
哈希冲突是指不同的 Key 经过哈希函数计算后，得到了相同的哈希值的现象。它不是'设计失误'，而是数学上的必然结果。
1.3 负载因子（Load Factor）
假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么 $\text{Load Factor} = N/M$。负载因子有些地方也翻译为载荷因子/装载因子等。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。负载因子的关键应用是触发哈希表进行扩容。
2. 哈希函数
哈希函数是哈希表的'核心引擎'，作用是：把任意类型的'键（Key）'（比如整数、字符串、对象），转换成一个固定范围的整数（称为'哈希值'或'索引'），这个索引直接对应底层存储数组的位置。
哈希函数的设计要求：
- 确定性：同一个 Key 每次输入哈希函数，必须得到相同的索引（若结果随机，则无法查找）。
- 均匀性：尽量将不同的 Key 映射到不同的索引，减少「哈希冲突」。
- 高效性：哈希函数的计算过程必须快速（如简单的取模、位运算），否则会抵消哈希表的效率优势。
2.1 直接定址法（Direct Addressing）
直接定址法是最直观的哈希函数构造方式，其核心是'关键字与哈希地址直接关联'，无需复杂计算，是理解哈希函数设计的基础。
直接定址法通过关键字本身或关键字的线性变换直接作为哈希地址，它的本质是建立关键字与哈希地址的线性映射关系：每个关键字通过公式计算后，会映射到唯一的哈希地址（数组索引），且不同关键字的哈希地址一定不同，这种'一一对应'的特性决定了：直接定址法不会产生哈希冲突（这是它与其他哈希函数的核心区别）。
理解映射过程：例如我们要统计一个字符串中每个字符出现的次数（确保字符串中都是小写字母），我们可以以字符的 ASCII 码值作为关键字，因为小写字母的 ASCII 码值是从 97 到 123，所以我们可以通过简单的线性变换将其关键字映射到大小为 26 的数组中：
优点：
- 计算高效：仅需一次线性运算（或直接使用关键字），几乎无额外开销，是所有哈希函数中计算最快的；
- 无冲突：由于映射关系是一一对应，完全避免哈希冲突，无需设计冲突解决机制；
- ：无需复杂逻辑，直接通过公式映射，代码实现难度低。
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
实现简单
- 空间利用率极低：仅适用于关键字范围小且连续的场景。若关键字范围大（如
0~10^9），哈希表数组容量需与关键字范围匹配，会导致大量空间浪费（例如存储 100 个数据，可能需要 10 亿大小的数组）；
- 灵活性差：仅支持整数关键字（非整数需先转为整数，且转换后范围仍需满足'小而连续'）；
- 不适合动态数据：若关键字范围不固定（如新增超出原范围的关键字），哈希表需频繁调整数组大小，成本极高。
直接定址法的应用场景非常受限，仅适合关键字范围已知、固定且较小的场景，例如：
- 员工编号（如
1~1000 的整数，连续且范围明确）；
- 月份（
1~12）、日期（1~31）等有限范围的数值；
- 数据库中固定前缀的自增 ID（如
5001~5100，范围明确且连续）。
2.2 除留余数法（Division Method）
除留余数法（也叫除法散列法）是实际开发中最常用的哈希函数构造方法，其核心是通过'取模运算'将关键字压缩到固定范围的地址，能适应大多数关键字场景。
除留余数法通过关键字对'数组大小'取模得到哈希地址，哈希函数为：H(key) = key mod m
key 为原始关键字（整数或经转换后的整数，如字符串转整数）；m 为哈希表底层数组的大小；mod 为取模运算（即求 key 除以 m 的余数），结果范围为 0~m-1，恰好对应数组的索引范围。
因此当我们用哈希表来存储数据时的一个必须的要求就是数据的类型必须能通过某种方式转为整数。
除留余数法的本质是将任意范围的关键字通过取模运算，压缩到 0~m-1 的地址空间（与数组大小匹配）。其核心是通过选择合适的 m，使哈希值在 0~m-1 范围内均匀分布，从而减少哈希冲突。
例如：若 m=13（数组大小 13），关键字 key=123 时，123 mod 13 = 6（因 13×9=117，123-117=6），则哈希地址为 6，落在 0~12 范围内。
当使用除法散列法时，要尽量避免 m 为某些值，如 2 的幂，10 的幂等。如果是 $2^n$，那么 key % 2^n 本质相当于保留 key 的后 n 位，那么后 n 位相同的值，计算出的哈希值都是一样的，就冲突了。如：{63, 31}看起来没有关联的值，如果 m 是 16，也就是 $2^4$，那么计算出的哈希值都是 15，因为 63 的二进制后 4 位是 1111，31 的二进制后 4 位是 1111。如果是 $10^n$，就更明显了，保留的都是 10 进制的后 n 位，如：{112, 12312}，如果 M 是 100，也就是 $10^2$，那么计算出的哈希值都是 12。因此当使用除留余数法时，建议 m 取不太接近 2 的整数次幂的一个质数 (素数)。
需要说明的是，实践中也是八仙过海，各显神通，Java 的 HashMap 采用除法散列法时就是 2 的整数次幂做哈希表的大小 m，这样的话就不用取模，可以直接位运算，相对而言位运算比取模更高效一些。但是他不是单纯的去取模，比如 m 是 2^16 次方，本质是取后 16 位，那么用 key' = key>>16，然后把 key 和 key' 异或的结果作为哈希值。也就是说我们映射出的值还是在 [0,m) 范围内，但是尽量让 key 所有的位都参与计算，这样映射出的哈希值更均匀一些即可。所以上面建议 m 取不太接近 2 的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论，但是实践中需要灵活运用，抓住本质。
对于哈希表来说最常见的数据类型除了整数外还有字符串，那么对于字符串我们该如何处理呢？处理的方法有很多种，如 ASCII 码求和、多项式哈希等等，不过 ASCII 码求和法的冲突率太高，一般不会使用。（下面的方法了解即可）
多项式哈希法是实际开发中最常用的字符串哈希方法，核心是给字符串中不同位置的字符赋予不同权重（基于'基数'的幂次），让位置信息影响哈希值，大幅降低冲突率。
对于字符串 s = s[0]s[1]...s[n-1]，哈希值计算为：hash = s[0] × base^(n-1) + s[1] × base^(n-2) + ... + s[n-2] × base^1 + s[n-1] × base^0
其中：s[i] 表示第 i 个字符的 ASCII 值（或其他整数映射）；base 是一个预设的基数（通常选大质数，如 31、37、10^9+7 等，避免与字符编码范围重叠）；为防止哈希值过大导致溢出，通常会对一个大质数 mod 取模（如 10^9+7、2^61-1），最终结果为 hash % mod。
示例
以 base=31，mod=10^9+7 为例，计算'abc'的哈希值：s[0] = 'a' = 97，权重 31^2 = 961 → 97×961 = 93217；s[1] = 'b' = 98，权重 31^1 = 31 → 98×31 = 3038；s[2] = 'c' = 99，权重 31^0 = 1 → 99×1 = 99；总和 = 93217 + 3038 + 99 = 96354 → 哈希值 = 96354 % (10^9+7) = 96354。
而'cba'的计算为：99×961 + 98×31 + 97×1 = 95139 + 3038 + 97 = 98274 → 与'abc'的哈希值不同，无冲突。
除此之外还有经典的哈希函数 DJB2 与 SDBM，这两种是工业界广泛使用的字符串哈希函数，由实践验证具有低冲突率和高计算效率，常用于哈希表、数据库索引等场景。DJB2 哈希函数：hash = 5381（初始值）；hash = hash * 33 + ASCII(s[i])（迭代）特点：5381 是一个经过验证的优质初始值，33 是高效的乘数（33 = 32 + 1，可优化为 hash << 5 + hash + c），冲突率极低。SDBM 哈希函数：hash = 0（初始值）；hash = hash * 65599 + ASCII(s[i])（迭代）特点：65599 是大质数，分布性优于小基数，适合长字符串，与 DJB2 并称'工业级标准'。
- 适用范围广：可处理任意范围的关键字（整数、字符串、对象等，只需转为整数），无论关键字范围大小；
- 地址范围可控：哈希地址固定在
0~m-1，桶数组大小 m 可灵活设置，避免空间浪费；
- 实现简单：取模运算在计算机中高效（尤其
m 为 2 的幂时，可用位运算 key & (m-1) 替代，速度更快）；
- 可通过
m 优化冲突率：选择合适的 m（如质数）可大幅降低冲突概率。
- 存在哈希冲突：由于关键字范围远大于
m，必然存在不同关键字映射到同一地址的情况，需配合冲突解决方法（如链地址法）；
m 的选择敏感：若 m 选择不当（如偶数、小合数），会导致哈希值分布不均，冲突率激增；- 对字符串等非整数关键字需额外转换：需先将非整数关键字转为整数（如字符串哈希），增加少量计算开销。
除留余数法是工业界最通用的哈希函数构造方法，几乎适用于所有场景，尤其是：
- 关键字范围大且不连续（如用户 ID、订单号，可能是
1~10^9 的整数）；
- 关键字为非整数类型（如字符串、对象，需先转为整数）；
- 动态数据场景（数据量未知或会增长，可通过扩容调整
m 维持性能）。
典型应用：Java HashMap（底层用 key & (m-1) 替代取模，m 为 2 的幂）、Python dict、Redis 哈希表等。
2.3 其他方法
除了直接定址法与除留余数法外，还有许多成熟的哈希函数，这里再简单介绍几种：
全域散列法
如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列法。
hab(key) = ((a × key + b)%P )%M，P 需要选一个足够大的质数，a 可以随机选 [1,P-1] 之间的任意整数，b 可以随机选 [0,P-1] 之间的任意整数，这些函数构成了一个 P * (P-1) 组全域散列函数组。假设 P=17，M=6，a = 3，b = 4, 则 h34>(8) = ((3 × 8 + 4)%17)%6 = 5。
需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致找不到插入的 key 了。
乘法散列法
乘法散列法对哈希表大小 m 没有要求，他的第一思路第一步：用关键字 K 乘上常数 A (0<A<1)，并抽出 k * A 的小数部分。第二步：后再用 m 乘以 k * A 的小数部分，再向下取整。
h(key) = floor(M × ((A × key)%1.0)) 其中 floor 表示对表达式进行下取整，A∈(0,1)，这里最重要的是 A 的值应该如何设定，Knuth 认为 A = (√5 - 1)/2 = 0.6180339887.... (黄金分割点)比较好。
乘法散列法对哈希表大小 M 是没有要求的，假设 m 为 1024，key 为 1234，A = 0.6180339887, A * key = 762.6539420558，取小数部分为 0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 = 669.6366651392，那么 h(1234) = 669。
上面的几种方法是《算法导论》中讲解的方法。《殷人昆 数据结构：面向对象方法与 C++ 语言描述（第二版）》和《[数据结构 (C 语言版)].严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于一些局限的特定场景，有兴趣可以去看看这些书籍。
3. 哈希冲突
哈希冲突的本质是'Key 的取值范围'与'哈希表大小'不匹配：
- Key 的取值范围是无限或极大的（如所有整数、所有字符串、所有对象）；
- 哈希表的大小是有限的（受内存限制，不可能无限大，如初始大小 16、32、64）。
根据'鸽巢原理'（n 个鸽子放入 m 个鸽巢，n>m 时至少有一个鸽巢有 2 只鸽子），当存储的 Key 数量超过哈希表大小时，必然出现多个 Key 映射到同一位置的情况。
实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放寻址法和链地址法。
3.1 开放寻址法（Open Addressing）
不使用额外数据结构（如链表），当发生冲突时，按固定规则在数组中寻找下一个空的位置，将 Key-Value 对存入空位置。查询时，若当前位置的 Key 不匹配，同样按规则继续查找，直到找到目标 Key 或空位置（表示 Key 不存在）。
双重哈希（Double Hashing）：冲突时，用第二个哈希函数计算步长（H_i(Key) = (H1(Key) + i×H2(Key)) % m），进一步降低聚集概率。
第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
二次探测（Quadratic Probing）：冲突时，按平方规律寻找下一个位置（H_i(Key) = (H(Key) + i²) % m），避免线性探测的'连续聚集'；
从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；
h(key) = hash0 = key % M , hash0 位置冲突了，则二次探测公式为： hc(key, i) = hashi = (hash0 ± i²) % M，i = {1, 2, 3, ..., }
二次探测当 hashi = (hash0 - i²) % M 时，当 hashi<0 时，需要 hashi += M。
线性探测（Linear Probing）：冲突时，依次检查下一个位置（H_i(Key) = (H(Key) + i) % m，i=0,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 的位置。
线性探测的比较简单且容易实现，线性探测的问题假设，hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。
下面演示 {19,30,5,36,13,20,21,12} 等这一组值映射到 M=11 的哈希表中的过程：
优点： 无需额外空间存储链表；缓存友好（数据存储在连续数组中，减少 IO）。
缺点： 易产生'聚集效应'（线性探测时，连续桶被占用，后续冲突概率更高）；删除数据需标记'已删除'，否则会断裂查找链。
典型应用： Redis 字典（部分场景）、Clang 编译器的哈希表、早期哈希表实现。
简单的代码实现：
开放寻址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，始终存在互相影响的问题。所以对于开放寻址法，我们选择线性探测实现即可：
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 {
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};
要注意的是这里需要给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。
如下图，我们删除 30，会导致查找 20 失败，当我们给每个位置加一个状态标识 {EXIST,EMPTY,DELETE}，删除 30 就可以不用删除值，而是把状态改为 DELETE，那么查找 20 时是遇到 EMPTY 才能停止，就可以找到 20。
这里我们哈希表负载因子控制在 0.7，当负载因子到 0.7 以后我们就需要扩容了，但是扩容的同时我们要保持哈希表大小是一个质数，第一个是质数，如果扩容 2 倍后就不是质数了，那么该如何解决呢？，一种方案就是上面除法散列中我们讲的 Java HashMap 的使用 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;
}
当 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;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
size_t hash = 0;
for (auto e : key) {
hash *= 131;
hash += e;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
public:
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};
namespace open_address {
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 Hash = HashFunc<K>>
class HashTable {
public:
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;
}
HashTable() {
_tables.resize(__stl_next_prime(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 (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == EXIST) {
newHT.Insert(_tables[i]._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 == nullptr) {
return false;
} else {
ret->_state = DELETE;
--_n;
return true;
}
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};
}
3.2 链地址法（Chaining）
开放寻址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
例如 {19,30,5,36,13,20,21,12,24,96} 这一组值映射到 M=11 的哈希表中：
如果遇到极端情况，某个桶很长，查找效率很低怎么办？这里在 Java8 的 HashMap 中当桶的长度超过一定阈值 (8) 时就把链表转换成红黑树。这样查找的效率就上来了。
优点： 冲突处理简单，不易产生'聚集效应'（多个冲突仅影响单个桶）。
缺点： 链表过长时查询效率下降（遍历需 O(k)，k 为链表长度）；需额外空间存储链表节点。
典型应用： Java HashMap（链表长度 > 8 时转为红黑树）、Python dict、Redis Hash。
简单的代码实现：
开放定址法负载因子必须小于 1，链地址法的负载因子就没有限制了，可以大于 1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl 中 unordered_xxx 的最大负载因子基本控制在 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;
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;
}
public:
HashTable() {
_tables.resize(__stl_next_prime(0), nullptr);
}
~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 hashi_new = hs(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi_new];
newtables[hashi_new] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = 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 hashi = hs(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;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}
4. 小结
- 哈希函数是'Key→地址'的映射工具，其核心是'确定性、均匀性、高效性'，决定了哈希表的基础效率；
- 哈希冲突是 Key 范围远大于桶数组大小导致的必然结果，其解决方法（链地址法 / 开放寻址法）决定了哈希表在冲突后的性能上限；
两者共同构成了哈希表的核心逻辑 —— 优秀的哈希函数 + 高效的冲突解决，才能实现哈希表'平均 O(1) 效率'的核心优势。
