哈希表:空间换时间

如果只能选一种数据结构陪你去面试,那一定是哈希表。它把"查找"从 O(n) 降到平均 O(1),代价只是多花一点内存。理解哈希表,你就掌握了算法优化里最核心的一招——空间换时间。

1. 从数组查找说起

在无序数组里找一个数,只能逐个比较,O(n)。如果数据本身是整数且范围不大,可以开一个"计数数组"直接按下标取——这就是哈希表的雏形:用一个哈希函数把任意键映射到数组下标。

# 模拟一个简易哈希表:只处理字符串键
def simple_hash(key, size):
    total = 0
    for ch in key:
        total += ord(ch)
    return total % size

print(simple_hash("cat", 10))   # 3
print(simple_hash("act", 10))   # 3  ← 冲突了!

看到问题了吗?"cat" 和 "act" 的字符和相同,映射到了同一个槽位,这就是哈希冲突。

2. 冲突怎么解决

链地址法:每个槽位挂一条链表,冲突的键都存进去;查找时先定位槽,再在链表里找。Java 的 HashMap、Python 的 dict 都基于此(链表过长时升级为红黑树/扩容)。
开放寻址法:冲突了就往后找空位,适合数据量可控的场景。

优秀的哈希函数应让键分布均匀;装载因子过高时触发扩容,保持平均 O(1)。

3. Python 中的 dict 与 set

# dict:键值对,查找 / 插入 / 删除都是平均 O(1)
scores = {"Ada": 95, "Bob": 87}
scores["Cindy"] = 92           # 插入
print(scores.get("Ada"))       # 95,不存在返回 None 而不报错
print("Bob" in scores)         # True,成员判断 O(1)

# set:只存键,天然去重
words = ["a", "b", "a", "c"]
print(len(set(words)))         # 3,去重后数量
print("b" in set(words))       # True

注意:dict 的键必须是可哈希的(不可变类型,如 str、int、tuple),list 和 dict 不能当键。

4. 经典应用:两数之和

LeetCode 第 1 题:在数组中找两个数,使它们的和等于 target。暴力是 O(n²);用哈希表记录"已经见过的数及其下标",一遍遍历即可:

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]

这就是典型的空间换时间:多用一个 O(n) 的哈希表,把时间从 O(n²) 压到 O(n)。

5. 更多高频套路

题目类型	哈希表用法	时间收益
两数之和 / 三数之和	记录已见值,查补数	O(n²) → O(n)
字符出现次数	Counter 统计频率	O(n) 直出
找重复元素 / 去重	set 判重	O(n²) → O(n)
LRU 缓存	哈希表 + 双向链表	O(1) 读写

6. 使用注意事项

哈希表不保证顺序(Python 3.7+ 的 dict 才按插入序);需要有序请用有序结构。
内存敏感时,权衡一下:数据量小,暴力未必吃亏。
面试时主动说一句"这里用哈希表,平均 O(1),但最坏是 O(n)",显得你懂底层。

💡 学习建议:把"两数之和"用暴力、排序+双指针、哈希表三种方法各写一遍,再思考"三数之和"怎么扩展——理解套路比刷题量重要。