数组 vs 哈希表#

先想一个数组 arr = ["apple", "banana", "cherry", ...]。如果你知道下标，arr[42] 是 $O(1)$；但如果问「banana 在哪？」，你就得从头扫到尾——$O(n)$。

哈希表换个思路：不要让位置取决于顺序，而让位置取决于内容本身。也就是说，把 “banana” 这个名字算出一个数字，直接用这个数字当位置！

1
# 哈希表的核心思想，简化版：
2
index = hash("banana") % table_size
3
table[index] = ("banana", value)

下次查 “banana”，用同样的 hash 函数算出同一个 index，直接跳到那里——$O(1)$！

哈希函数：魔法背后的数学#

哈希函数要满足几个要求：

1. 确定性：同样的输入永远产生同样的输出
2. 均匀分布：不同的输入要尽量散布在整个表里，减少「撞车」
3. 高效：不能算半天才算出来，那就本末倒置啦

举个简单的例子，Python 里字符串的哈希：

1
>>> hash("banana")
2
-545372479991580235
3
>>> hash("YuKi")
4
-8909234767212052123

当然实际不是拿这么大的数字直接当下标——要先取模：hash(key) % capacity，把它映射到表的大小范围内。

碰撞问题：两个key抢一个位置怎么办？#

因为可能的 key 无限多，表大小有限，碰撞（collision）是不可避免的。那怎么办？有两种经典策略：

1
位置0: → ("apple", v1)
2
位置1: → ("banana", v2) → ("cherry", v3)  ← 碰撞了！
3
位置2: → ("durian", v4)

1
插入 "banana"，hash 后位置 3 被占了 → 看 4 → 也占了 → 看 5 → 空的！放这儿

实际应用遍地开花#

哈希表的影子无处不在：

• 数据库索引：哈希索引精确匹配超快（但范围查询不行，得用 B+ 树）
• 缓存系统：Redis 就是个带持久化的大哈希表
• 去重：想给一万条日志去重？全扔 set() 里，$O(n)$ 搞定
• 路由表：网络路由器用哈希查找目标 IP
• 编译器：符号表（变量名→地址）就是个哈希表
• 区块链：比特币的 Merkle 树和交易索引大量依赖哈希

一点小建议#

写 Python 时别用 list 当字典用——if item in long_list 是 $O(n)$，换成 set 或 dict 就是 $O(1)$ 了。这个优化有时能把几分钟的程序变成几秒钟。

好啦～今天的科技小课堂就到这里！下次打开 Python 的 dict，你会想到那个在后台默默算哈希、绕开碰撞的小引擎吗？💕

早安宝贝们，六一快乐～🎈✨