元数据卡
- 前置知识：数组、链表（第2章）
- 预计时间：12 分钟
- 完成标志：能理解哈希函数和哈希表的基本原理
你的进度
你在森林里遇到了一片诡异的树林。每一棵树都长着一个钥匙孔。你没有钥匙，只有一堆五花八门的物品：一支笔、一个苹果、一条蛇、一块石头……
你需要把这些东西塞进树洞里，然后下次拿着相同的东西一碰树洞，它立刻就能把东西吐出来。不需要翻箱倒柜，不需要逐个比对，直接拿到。
这片森林叫做哈希森林。
问题：从数组到哈希
假如你要存一个电话本：人名 → 电话号码。用数组怎么存？
python
# 用数组存电话本：需要遍历查找
phone_book = [("Alice", "123"), ("Bob", "456"), ("Charlie", "789")]
# 要找 Bob 的电话：遍历整个数组，O(n)太慢了。如果能直接把"Bob"变成数组下标（比如 1），那访问就是 O(1)。这就是哈希表的核心思想。
哈希函数把一个任意大小的输入（"Bob"）映射到一个固定范围内的整数（数组下标）。
python
# 最简单的哈希函数：把字符串转成下标
def simple_hash(key, table_size):
total = 0
for char in key:
total += ord(char) # 字符的 ASCII 值
return total % table_size
# "Bob" → (66 + 111 + 98) % 10 = 275 % 10 = 5
# 直接把 Bob 的电话存在数组下标 5 的位置哈希表的核心操作
python
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # 每个槽放一个链表
def _hash(self, key):
return hash(key) % self.size # Python 内置 hash 函数
def put(self, key, value):
index = self._hash(key)
# 检查 key 是否已存在
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
raise KeyError(key)核心操作复杂度：
| 操作 | 平均 | 最差 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 查找 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
平均情况 O(1) 是因为哈希函数把 key 均匀分布到各个槽。最差 O(n) 是所有 key 都映射到同一个槽——比如哈希函数设计得不好。
哈希函数要满足什么
一个好的哈希函数应该：
- 确定性：相同的输入永远产生相同的输出
- 均匀分布：不同的输入尽量均匀分布在各个槽
- 高效：计算速度快
python
# 不好的哈希函数
def bad_hash(key, size):
return len(str(key)) % size # 很多 key 长度相同，全挤一个槽
# 好的哈希函数
def good_hash(key, size):
h = 0
for i, char in enumerate(str(key)):
h = (h * 31 + ord(char)) & 0xFFFFFFFF # 乘以质数 31
return h % sizeJava 的 String.hashCode() 正是用 h = h * 31 + char 这个公式计算的。
旅人笔记
哈希表用哈希函数把 key 映射到数组下标，实现 O(1) 的平均查找时间。核心三要素：哈希函数（均匀映射）、数组（O(1) 随机访问）、冲突处理（解决多个 key 落在同一槽）。
→ 下一步：哈希冲突解决
好的哈希函数也不能完全避免冲突。当两个 key 映射到同一个槽时，怎么处理？