哈希表介绍
一、什么是哈希表
哈希表是一种通过键（Key）来直接访问值（Value）的数据结构，它利用一个叫做哈希函数的魔法公式，把任意大小的键（比如一个字符串、一个数字或一个对象）转换成一个固定大小的数字，这个数字被称为哈希值或哈希码。然后，用这个哈希值作为数组的索引，将值存储在这个索引对应的数组位置上。
核心组件
一个哈希表主要由以下三个核心部分组成：
-
键（Key）： 你要存储和查找数据时使用的标识符。比如，在电话簿中，人名就是键。
-
值（Value）： 与键相关联的实际数据。在电话簿中，电话号码就是值。
-
哈希函数（Hash Function）： 将键映射到数组索引的数学函数。它是哈希表的心脏。
-
工作原理
（以上摘自菜鸟教程）
如果你学过操作系统，你会发现这个很像内存地址映射，也就是虚拟内存通过页表映射到真实物理地址。唉，东西学多了，很多自然就串起来了😎
二、哈希函数
哈希函数（Hash Function）：是一种将元素的关键字映射为哈希表存储位置的函数。
哈希函数是一个哈希表的核心，它需要具备以下要求！
✅ 计算快 ✅ 结果均匀分布（避免扎堆！） ❌ 不能有规律（否则冲突爆炸！）
常见的哈希函数如下：
-
直接定址：直接取关键字本身或其线性函数作为哈希地址，即
Hash(key)=key或者Hash=a*key+b,其中a和b是常数。该方法计算极为简单，且不会产生冲突，适用于关键字分布连续的场景。如果关键字分布稀疏，则会造成空间浪费。
-
除留余数法：设哈希表长度为 m，选取不大于 m 的质数 p，用
Hash(key)=key%p计算哈希地址。这是最常用的哈希函数之一。关键在于 pp 的选择，通常取质数或与 mm 接近的数，以减少冲突。
比如将数组：7个数比如[0, 1, 2, 3, 4, 5, 6]存放到一个长度为11的哈希表中。
-
平方取中法：先对关键字平方，再取中间若干位作为哈希地址。例如
Hash(key)=key**2//100%1000，即先平方，去掉末尾两位，再取中间三位。
- 基址转换：将一个数视为某一进制然后转换成另一进制再取部分。
三、哈希冲突
1.开放地址法
指的是当发生哈希冲突时，通过探查哈希表中其他空地址来存放冲突元素，直到找到空地址为止。
利用公式表示就是：
- 核心思想：所有元素必须存在哈希表的数组槽位中（不允许用额外链表！）
- 关键规则：冲突时按固定规则探测新位置，直到找到空槽！
三大探测策略（找空位的方法）
1️⃣ *线性探测（Linear Probing）*
- 规则：冲突后顺序往后找（
h(key) + 1,+2,+3…） - 公式：
h_i(key) = (h(key) + i) % 表长度（i=1,2,3...） - 缺点：容易聚集（连续占用导致后续冲突更严重！）
2️⃣ *二次探测（Quadratic Probing）*
- 规则：冲突后按平方步长跳跃（
+1²,-1²,+2²,-2²…） - 公式：
h_i(key) = (h(key) +- i**2) % 表长度 - 优点：减少线性聚集
- 缺点：可能找不到空位（即使表未满！需表长为质数且负载因子<0.5）
3️⃣ *双重哈希（Double Hashing）*
- 规则：用第二个哈希函数计算步长（
h(key) + i * h₂(key)） - 公式：
h_i(key) = (h₁(key) + i * h₂(key)) % 表长度 - 要求：
h₂(key)必须与表长度互质（通常选质数表长） - 优点：探测序列更随机，冲突率最低！
2.链地址法
通过链表将有冲突的的元素放在相同位置。这个也更加常用。
计算哈希值
h(key) = key % 表长度 → 定位到数组下标 i
-
插入：在 bucket[i] 的链表头部或尾部添加新节点
-
查找：遍历 bucket[i] 的链表找目标键
-
删除：从 bucket[i] 的链表中移除节点（直接删！不用标记！）
比如存[10, 22, 31, 4, 15, 28, 17]到长度11的哈希表。
那么我们会经历这么样的过程。
| 元素 | `h(key)` | 链表变化 ||------|-----------|-------------------------|| 10 | 10 | `bucket[10] → [10]` || 22 | 0 | `bucket[0] → [22]` || 31 | 9 | `bucket[9] → [31]` || 4 | 4 | `bucket[4] → [4]` || 15 | 4 | `bucket[4] → [15→4]` | ← 冲突！插到头部| 28 | 6 | `bucket[6] → [28]` || 17 | 6 | `bucket[6] → [17→28]` | ← 冲突！插到头部最终的结果是这个样子的
bucket[0]: 22 → NULLbucket[4]: 15 → 4 → NULLbucket[6]: 17 → 28 → NULLbucket[9]: 31 → NULLbucket[10]: 10 → NULL其他bucket: NULL四、对比
| 特性 | 链地址法 | 开放地址法 |
|---|---|---|
| 内存布局 | 分散（数组+堆内存链表） | 紧凑（纯数组） |
| 删除操作 | ✅ 直接删 | ❌ 必须标记DELETED |
| 负载因子上限 | 无限制（但建议<1） | 必须<0.75（线性探测） |
| 适用场景 | 动态数据、频繁删除 | 内存敏感、静态数据 |
链地址法 = 哈希表 + 链表缝合怪！ 适用场景：
- 数据量动态变化（比如用户注册系统）
- 需要频繁删除（比如缓存淘汰）
绝对禁忌：
- 别用单链表存超多数据（Java HashMap链表>8转红黑树！）
- 别忽略内存开销（嵌入式系统慎用！）
部分信息可能已经过时