哈希表（Hash Table）

📱 手机通讯录——一秒找到人

打开手机通讯录，输入”张三”，秒出结果。你有没有想过——手机是怎么从几千个联系人里这么快找到”张三”的？

如果用最笨的方法（线性搜索），从通讯录的第一个联系人开始逐个比对——当通讯录有 1000 个人时，平均要找 500 次。这显然不合理。

哈希表（Hash Table） 就是解决”快速查找”问题的终极方案——平均 O(1) 的查找速度，不管数据量多大，基本上一次定位。

🚪 类比：快递柜

你去取快递，柜门上写着”请凭取件码取件”。你在屏幕上输入取件码 “0427”——“咔嗒”一声，对应的柜门弹开了。

取件码 0427 → 系统计算 → 3 号柜 → 弹开对应柜门

这就是哈希表的核心思想：把要查的”键”通过一个函数转换成一个”位置”，直接去那个位置找数据。

不需要一个个翻——直接去正确的格子里拿。

---

🔧 哈希表的工作原理

哈希表由三部分组成：

1. 数组——用来存数据的底层结构（一片连续的内存空间）
2. 哈希函数（Hash Function）——把键（key）映射成数组下标的函数
3. 键值对（Key-Value Pair）——数据本身，每个键对应一个值

哈希表的结构：

数组： [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] ...
        ↓     ↓     ↓     ↓     ↓     ↓     ↓
       空    ("张三", 值) 空   ("李四", 值) 空   空

插入过程

# 插入键值对 ("张三", {name:"张三", age:20, phone:"138xxxx"})
# 1. 计算哈希值：hash("张三") → 某个数字
# 2. 计算下标：hash("张三") % 数组长度 → 5
# 3. 存储：table[5] = ("张三", 值)

查找过程

# 查找 "张三"
# 1. 计算哈希值：hash("张三") → 同样数字
# 2. 计算下标：hash("张三") % 数组长度 → 5
# 3. 取数据：table[5] 就是 ("张三", 值)

关键点：插入和查找执行的步骤完全相同——所以哈希表不管有多大，查找时间都是常数。

---

🧮 哈希函数——哈希表的核心

哈希函数把键（可以是任意类型：字符串、数字、对象……）映射成一个固定范围的整数。

一个”好”的哈希函数有三个要求：

要求	说明	不好 vs 好
确定性	同一个键必须算出同样的哈希值	✅ 必须保证
均匀性	不同键尽量均匀分布到各个桶	❌ “很多键算出同一个值”→ 冲突
高效率	计算要快	❌ 太复杂的哈希函数会拖慢速度

Python 中内置的哈希函数：

print(hash("张三"))    # → 某个整数（比如 721849312)
print(hash("李四"))    # → 另一个整数
print(hash(42))        # → 42（小整数哈希就是它本身）

💡 常见的哈希函数：在 Java 中，String.hashCode() 使用多项式哈希；在 C++ 中，std::hash 使用各类型特化的哈希函数。Python 的哈希函数使用 SipHash——安全且高效。

---

💥 哈希冲突——不可避免的问题

假设数组长度是 10，有两个不同的键算出同样的下标：

hash("张三") % 10 = 5
hash("李四") % 10 = 5  ← 冲突！两个键都映射到位置 5

哈希冲突（Hash Collision） 是不可避免的——因为键的数量远大于数组长度（鸽巢原理）。解决冲突有两种主流方式：

方式 1：链地址法（Separate Chaining）

数组中每个位置不是存单个元素，而是存一个链表（或红黑树）的头部：

table[5] → ("张三", 值) → ("李四", 值) → ("王五", 值)
            ↑ 链表的每个节点就是一个键值对

查找时：先定位到 table[5]，然后遍历链表，逐个比对键。

时间复杂度：
- 平均：每个桶的链表长度 ≈ n / 数组大小 = 负载因子
- 理想情况：负载因子很小 → O(1)
- 最坏情况：所有键映射到同一个桶 → O(n)（退化成链表）

方式 2：开放地址法（Open Addressing）

如果目标位置被占了，就找下一个空闲的位置：

线性探测（Linear Probing）：
hash("张三") % 10 = 5 → table[5] 被占了 → 试试 table[6] → 空！放这里

查找 "张三"：hash("张三") % 10 = 5 → table[5] 不是 "张三"
→ 到 table[6] 看 → 是 "张三"！找到了

负载因子（Load Factor）——需要扩容的信号

$$ 负载因子 = \frac{已存储的键值对数}{数组长度} $$

• 负载因子越大 → 冲突越多 → 性能越差
• 一般当负载因子超过 0.75 时，哈希表会扩容（Rehash）——把数组长度加倍，把所有键重新哈希到新的数组中
• 扩容是 O(n) 的，但摊还分析下来，插入的平均复杂度还是 O(1)

---

🗺️ 哈希表 vs 其他查找结构

操作	哈希表	二叉搜索树	数组（有序+二分查找）
查找	O(1) 平均	O(log n)	O(log n)
插入	O(1) 平均	O(log n)	O(n)
删除	O(1) 平均	O(log n)	O(n)
范围查询	❌ 不支持	✅ 支持	✅ 支持
有序遍历	❌ 无序	✅ 有序	✅ 有序

哈希表的优势：等值查找速度极快。 哈希表的局限：数据无序，不支持范围查询。

---

🏢 Python 中哈希表的实际使用

Python 的 dict 和 set 底层就是哈希表：

# dict —— 键值对存储
phone_book = {
    "张三": "138-0000-0001",
    "李四": "139-0000-0002",
    "王五": "137-0000-0003"
}

# 查找 O(1)
print(phone_book["张三"])  # "138-0000-0001"

# 插入 O(1)
phone_book["赵六"] = "136-0000-0004"

# 检查存在 O(1)
if "张三" in phone_book:
    print("找到了")

# set —— 不重复元素的集合
visited = set()
visited.add("北京")   # O(1)
visited.add("上海")
if "北京" in visited:  # O(1)
    print("去过北京")

Python dict 的底层实现细节

Python 的 dict 用的是改良的哈希表——不仅解决冲突，还考虑了内存效率：

1. 背后是一个稀疏数组（Spare Table）
2. 使用开放地址法解决冲突（而不是链地址法）
3. 负载因子约 2/3 时扩容
4. 从 Python 3.6 开始，dict 会保持插入顺序（这是一个附带效果，不是有序字典）

---

📝 小结

概念	一句话
哈希表	键→哈希函数→数组下标，直接定位数据
哈希函数	把任意类型的键映射成整数
哈希冲突	不同键算出相同下标——用链地址法或开放地址法解决
负载因子	键值对数 / 数组长度——超过阈值就扩容
时间复杂度	平均 O(1)，最坏 O(n)
局限性	无序，不支持范围查询

🎯 思考题：Java 8 之后的 HashMap 在链表长度超过 8 且总元素数超过 64 时，会把链表转成红黑树。为什么这么做？如果要构造一个”恶意数据”让哈希表退化成 O(n)，你要怎么做？这和平衡树有什么关系？

为什么先学这个？ 哈希表是最高效的查找结构。接下来进入另一种组织数据的方式——树。二叉树与遍历。