搜索的目标，是在一批数据中根据某个关键字找到对应的元素。
如果数据保存在普通列表中，最直接的方法是从头到尾检查，复杂度通常是 O(n)。哈希法则尝试把关键字转换成一个数组下标，让程序直接跳到可能的位置。
Python 中的 dict 和 set 就是哈希法最常见的应用。
哈希法的核心思想是：用哈希函数把“关键字”转换成“存储位置”，从而把平均搜索成本降到接近 O(1)。
1. 从线性搜索开始
假设有一组用户名和分数：
records = [
("alice", 95),
("bob", 82),
("carol", 91),
]
def linear_search(records, username):
for name, score in records:
if name == username:
return score
return None
print(linear_search(records, "carol")) # 91
如果有 n 条记录，最坏情况下需要检查全部记录，时间复杂度是 O(n)。
当数据量很大、并且程序经常按照用户名查找时，每次从头扫描会比较慢。哈希法会为每个用户名计算一个位置。
2. 哈希函数和哈希值
哈希函数接收一个关键字，输出一个整数：
关键字 → 哈希函数 → 哈希值 → 数组下标
Python 可以使用内置的 hash 函数：
print(hash("alice"))
print(hash(2026))
print(hash((1, 2, 3)))
哈希值可能是很大的整数，所以不能直接把它当数组下标。假设哈希表容量为 capacity，常用的下标计算方式是：
index = hash(key) % capacity
例如：
key = "alice"
capacity = 8
index = hash(key) % capacity
print(index) # 一定在 0 到 7 之间
哈希函数希望满足以下特点：
- 相同的关键字，计算出的哈希值必须相同；
- 不同关键字最好尽量分散；
- 计算速度应该较快；
- 哈希值分布不应该集中在少数几个位置。
注意：哈希函数不是加密函数。哈希值不能用来还原原始数据，也不应该直接当作密码保存方案。
3. Python 中哪些对象可以作为键？
字典的键和集合中的元素必须是可哈希的。简单来说，对象在作为键使用期间，参与比较的内容不能发生变化。
可以作为键的常见对象包括：
data = {
"name": "Alice",
2026: "year",
(1, 2): "tuple",
}
print(data["name"])
print(data[(1, 2)])
列表和字典不能直接作为键，因为它们是可变对象：
# 下面的代码会抛出 TypeError
# data[[1, 2]] = "list"
# data[{"x": 1}] = "dict"
元组只有在其中所有元素都可哈希时，才能作为键：
valid_key = (1, "two", (3, 4))
data[valid_key] = "valid"
4. 哈希冲突
不同关键字可能得到相同的数组下标：
hash("alice") % 8 = 3
hash("bob") % 8 = 3
这种情况叫作哈希冲突。冲突不是哈希法失败，而是哈希表必须处理的正常情况。
常见的冲突处理方法有两类：
4.1 拉链法
每个数组槽位不只保存一个元素，而是保存一个小链表或列表：
槽位 0：空
槽位 1：空
槽位 2：[key_a, value_a] → [key_b, value_b]
槽位 3：空
查找时，先根据哈希值找到槽位，再在槽位中的小链表里逐个比较关键字。
4.2 开放地址法
所有元素都直接放在哈希表数组中。如果目标位置被占用，就按照某种规则继续尝试其他位置：
第一次尝试：index
第二次尝试：index + 1
第三次尝试：index + 2
...
这种“依次向后寻找”的方法叫线性探测。还可以使用二次探测或再次哈希等方法。
两种方法的比较：
| 方法 | 元素存放位置 | 优点 | 代价 |
|---|---|---|---|
| 拉链法 | 槽位对应的链表或列表 | 删除相对直接，实现直观 | 有额外节点或列表空间 |
| 开放地址法 | 哈希表数组内部 | 内存连续，缓存局部性较好 | 删除和探测规则更复杂 |
5. 用 Python 实现拉链法哈希表
下面实现一个简化版的哈希映射。每个槽位保存一个列表，列表中的每一项是 key 和 value：
class ChainedHashMap:
def __init__(self, capacity=8):
if capacity <= 0:
raise ValueError("容量必须大于 0")
self._buckets = [[] for _ in range(capacity)]
self._size = 0
def _index(self, key):
return hash(key) % len(self._buckets)
def put(self, key, value):
bucket = self._buckets[self._index(key)]
for index, (stored_key, _) in enumerate(bucket):
if stored_key == key:
bucket[index] = (key, value)
return
bucket.append((key, value))
self._size += 1
if self._size / len(self._buckets) > 0.75:
self._resize(len(self._buckets) * 2)
def get(self, key, default=None):
bucket = self._buckets[self._index(key)]
for stored_key, value in bucket:
if stored_key == key:
return value
return default
def delete(self, key):
bucket = self._buckets[self._index(key)]
for index, (stored_key, _) in enumerate(bucket):
if stored_key == key:
bucket.pop(index)
self._size -= 1
return
raise KeyError(key)
def _resize(self, new_capacity):
old_items = [
item
for bucket in self._buckets
for item in bucket
]
self._buckets = [[] for _ in range(new_capacity)]
self._size = 0
for key, value in old_items:
self.put(key, value)
def __contains__(self, key):
bucket = self._buckets[self._index(key)]
return any(stored_key == key for stored_key, _ in bucket)
def __len__(self):
return self._size
可以这样使用：
table = ChainedHashMap()
table.put("alice", 95)
table.put("bob", 82)
table.put("alice", 98) # 更新 alice 的值
print(table.get("alice")) # 98
print(table.get("unknown")) # None
table.delete("bob")
print(len(table)) # 1
上面的实现展示了哈希表的主要过程：
- 计算关键字的哈希值；
- 用取模得到槽位；
- 在槽位中搜索相同关键字；
- 找到则更新，找不到则插入；
- 装载因子太高时扩容并重新哈希。
如果哈希表允许存储 None 作为值，contains 不能通过 get 的返回值判断，而应该直接检查键是否存在：
table = ChainedHashMap()
table.put("empty", None)
print("empty" in table) # True
教学实现可以帮助我们理解原理；实际项目中通常直接使用 Python 内置的 dict。
6. Python 的 dict
Python 字典提供了成熟的哈希表实现：
scores = {
"alice": 95,
"bob": 82,
}
scores["carol"] = 91
scores["alice"] = 98
print(scores["alice"]) # 98
print(scores.get("unknown")) # None
print(scores.get("unknown", 0)) # 0
print("bob" in scores) # True
常见操作的平均复杂度：
| 操作 | 平均复杂度 | 说明 |
|---|---|---|
| 根据键读取 | O(1) | 计算哈希并定位 |
| 插入或更新 | O(1) | 平均情况 |
| 删除 | O(1) | 平均情况 |
| 判断是否存在 | O(1) | 平均情况 |
| 遍历全部键值 | O(n) | 必须访问所有元素 |
最坏情况下，如果大量关键字发生冲突，单次操作可能退化到 O(n)。现代实现会通过优秀的哈希函数、扩容和冲突策略降低这种可能性。
7. Python 的 set
集合 set 只保存关键字，不保存对应的值，也使用哈希表实现：
visited = set()
visited.add("home")
visited.add("about")
visited.add("home") # 重复添加不会产生第二个元素
print("home" in visited) # True
visited.remove("about")
集合特别适合做去重和快速存在性检查：
numbers = [3, 1, 3, 2, 1, 5]
unique_numbers = set(numbers)
print(unique_numbers)
如果需要保持首次出现的顺序，可以使用字典的键：
numbers = [3, 1, 3, 2, 1, 5]
unique_in_order = list(dict.fromkeys(numbers))
print(unique_in_order) # [3, 1, 2, 5]
8. 装载因子与扩容
哈希表容量为 m，已经存放 n 个元素时，装载因子可以写成：
α = n / m
装载因子越高，冲突通常越多，搜索一个槽位中的元素可能需要比较更多关键字。
因此哈希表通常不会一直填满。当装载因子超过某个阈值时，会进行扩容：
旧容量：8
新容量：16
重新计算每个元素的位置
扩容需要把已有元素重新放入新表，单次成本可能是 O(n)。但扩容不是每次插入都发生，所以插入操作的长期平均成本仍然可以接近 O(1)。
这和动态数组的摊销复杂度很相似：
- 某一次操作可能很贵；
- 大部分操作很快；
- 长期平均成本较低。
9. 自定义对象作为字典键
自定义类如果希望作为字典键，需要正确实现相等判断和哈希：
class UserKey:
def __init__(self, user_id):
self.user_id = user_id
def __eq__(self, other):
return (
isinstance(other, UserKey)
and self.user_id == other.user_id
)
def __hash__(self):
return hash(self.user_id)
users = {
UserKey(1): "Alice",
}
print(users[UserKey(1)]) # Alice
这里两个 UserKey 对象不是同一个对象，但它们的 user_id 相同，因此被视为相等的键。
重要规则是：
如果两个对象相等，它们的哈希值必须相等。
反过来，哈希值相等的两个对象不一定相等，因为哈希冲突是允许的。
不要让参与哈希的属性在对象作为键期间发生变化：
class MutableKey:
def __init__(self, value):
self.value = value
def __hash__(self):
return hash(self.value)
def __eq__(self, other):
return isinstance(other, MutableKey) and self.value == other.value
key = MutableKey("before")
mapping = {key: "data"}
key.value = "after"
# 此时再用 key 查找，结果可能不符合直觉
修改键的哈希相关内容后，原来的槽位和新的哈希值可能不再对应。
10. 哈希法适合什么时候？
哈希法适合：
- 根据唯一关键字快速查找；
- 统计频次；
- 去重；
- 判断元素是否访问过；
- 缓存计算结果；
- 建立对象编号到对象的映射；
- 处理“两数之和”等需要快速查找的问题。
例如，两数之和可以用集合或字典把复杂度从 O(n²) 降到平均 O(n)：
def two_sum(numbers, target):
seen = {}
for index, value in enumerate(numbers):
complement = target - value
if complement in seen:
return seen[complement], index
seen[value] = index
return None
print(two_sum([2, 7, 11, 15], 9)) # (0, 1)
哈希法不适合：
- 需要按照大小排序；
- 需要查找某个范围内的所有元素；
- 需要频繁获得“下一个更大”或“前一个更小”的键；
- 需要稳定的有序遍历而又不额外维护顺序。
这些场景可以考虑排序数组、二叉搜索树或其他有序结构。
11. 常见错误
误以为哈希查找永远是 O(1)
O(1) 通常指平均复杂度。冲突严重时，最坏情况可能退化到 O(n)。
把哈希值当作固定编号
Python 的字符串哈希可能因为进程级随机化而变化，不应该把 hash("name") 的具体数值写死或保存到文件中。
使用可变对象作为键
列表、字典等可变对象不能直接作为键。自定义对象也不应该在作为键期间改变参与哈希的属性。
误把哈希法当排序结构
哈希表擅长“是否存在”和“根据键取值”，但不擅长按照大小关系组织键。
忽略空间成本
哈希表需要额外数组、槽位和冲突处理结构。用时间换空间是哈希法的重要特点。
12. 小结
- 哈希法通过哈希函数把关键字映射到存储位置；
- 冲突是正常现象，需要使用拉链法或开放地址法处理；
- Python 的 dict 和 set 都建立在哈希表思想之上；
- 字典和集合的查找、插入、删除平均为 O(1)；
- 装载因子过高时需要扩容和重新哈希；
- 键必须是可哈希的，参与哈希的内容不能在使用期间改变；
- 哈希法适合快速查找和去重，不适合范围查询和有序操作。