【数据结构与算法】哈希表拾遗-EW帮帮网

一.什么是哈希表

哈希表是一种基于数组和哈希函数实现的键值对映射结构，可以实现常数级别的插入、查找和删除，是高效的数据结构。
其中哈希表的核心思想：把“键”通过哈希函数转换为数组下标，从而将数据直接存储到对应位置上，进而在查找上实现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 改变了）
插入到新表对应的新桶中（重新分配链表）
释放旧表空间

【数据结构与算法】哈希表拾遗