为什么你需要一个哈希表

从一个问题说起

假设你有一个存了 100 万个用户的数组，现在要查找用户「张三」。
用数组挨个遍历，最坏要比较 100 万次。这效率，甲方看了都要沉默。
哈希表说：给我一次，就一次。

核心思想

哈希表 = 数组 + 哈希函数

"张三" ──哈希函数──→  index = 42 ──→ users[42]

1. 把 key 扔进哈希函数，算出一个下标
2. 直接跳到数组对应位置取值
3. 不比较、不遍历，一步到位

理想 vs 现实

理想情况：查找 O(1)

现实：哈希冲突 —— 两个 key 算出同一个下标。

• 解决办法（知道名字就行）：
• 链地址法：冲突的位置挂一条链表
• 开放寻址法：换个空位继续放

# Python 中的哈希表（字典）
scores = {"张三": 90, "李四": 85}
print(scores["张三"])  # O(1)，一步到位

常见场景

场景	为什么用哈希表
统计词频	key 是单词，value 是次数
缓存（Cache）	快速判断数据是否存在
两数之和（LeetCode 1）	边遍历边查”另一半”

一句话总结

用空间换时间：数组管”存得下”，哈希函数管”找得快”。