【数据结构与算法】哈希表拾遗
一.什么是哈希表
哈希表是一种基于数组和哈希函数实现的 键值对映射结构，可以实现 常数级别的插入、查找和删除，是高效的数据结构。
其中哈希表的核心思想：把“键”通过哈希函数转换为数组下标，从而将数据直接存储到对应位置上，进而在查找上实现O(1)的复杂度。
eg:
index = hash(key) % 表大小;
table[index] = value;
二.哈希函数
哈希函数的映射方式是：如何将“键”转换为数组中的索引值（，以便将其映射到哈希表的某个位置。下面我们介绍两个最常见的映射方法。
1.直接定址法
直接使用key本身或者某个线性函数作为哈希地址：
hash(key) = key 或 hash(key) = a × key + b
缺点：
- 要求 key 是整数并且范围较小、稠密
- 浪费空间（如果 key 很大但稀疏）
2.除留余数法
将 key 除以哈希表长度，取余作为哈希地址：
hash(key) = key % mod
一般会使用小于等于表长的最大质数作为mod可以减少冲突。
优点：
- 通用性强，适用于整数 key
- 简单易实现
3.多项式哈希
字符串不能直接参与数学运算，需逐字符映射：
hash(s) = s[0] × pⁿ⁻¹ + s[1] × pⁿ⁻² + ... + s[n-1] × p⁰
优点：
- 可适配英文、数字等字符串
- 冲突率低，适合文本类 key
eg:
- 字符串：“abc”
- ASCII值：a=97，b=98，c=99
- 选择一个小的质数 p = 31
hash("abc") = 97 × 31² + 98 × 31¹ + 99 × 31⁰= 97 × 961 + 98 × 31 + 99 × 1= 97 × 961 = 93217 98 × 31 = 3038 99 × 1 = 99合计： 93217 + 3038 + 99 = **96354**如果哈希表长为10007：
96354 % 10007 = 6276
最终哈希表中的桶下标就是 6276。
其中p应该怎么选择呢
- 必须是一个质数 可以减少哈希冲突，比如 31, 33, 131, 1313, 13331 等
- 应大于字符集大小 如果字符是 ASCII，最好 p > 128；如果是 Unicode，p > 65536
- 不宜太大 太大会造成哈希值溢出，计算效率低
常用的p值推荐：
- 31 常用于小写英文字母字符串
- 131 中文支持更好，冲突率低
- 33 GCC 早期使用
- 5381 被著名的 djb2 哈希算法使用
- 65599 sdbm 哈希算法
三.哈希冲突与解决
1.是什么是哈希冲突
不同的键经过哈希函数计算后，映射到了哈希表中的同一个索引位置。
2.开放地址法
当发生冲突的时候使用不同的方法寻找下一个空位置：
1.线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
缺点：
容易产生“聚集”：连续冲突元素形成连续占用空间，导致探测效率下降。
2.平方探测
平方探测法测试按照这样的规则顺序探测：
Hash(key） = (Hash(key) + d) % 11
d = 1^2, -1^2, 2^2, -2^2......
优点：
- 避免一次聚集，冲突分布更均匀
- 比线性探测在高负载下表现更好
缺点：
- 实现略复杂
- 可能出现“二次聚集”
- 如果哈希表大小不是质数，可能无法探测到所有桶（导致无法插入）
在开放地址法哈希表中，删除元素不能直接清空，而是通过设置“删除标志位” 确保查找不会中断，能正常插入。
3.链地址法
每个哈希桶不只存一个元素，而是存一个链表
当多个键通过哈希函数映射到同一个桶时，它们就被链接到该桶的链表上。
C++中的unordered_map/unordered_set实现采用“链地址法 + 链表结构 + 动态 Rehash 机制”相结合的方式。
Rehash（再哈希）的步骤
- 分配一个新的更大数组（通常是原来容量的 2 倍或最接近的质数）
- 重新遍历旧哈希表
- 对每个旧元素重新计算新哈希值（因为 table_size 改变了）
- 插入到新表对应的新桶中（重新分配链表）
- 释放旧表空间