哈希表（Hash Table）是工程中最实用的数据结构之一，能在平均 O(1) 时间完成查找、插入、删除。Python 的 dict、JS 的 Object/Map、Java 的 HashMap 本质都是它。
一、核心思想
用哈希函数把 key 映射到数组下标，直接定位数据。
hash("name") → 3
array[3] = "张三"
# 查找：hash(key) → 下标 → 取值，O(1)二、哈希函数
好的哈希函数要：
- 计算快（O(1)）
- 分布均匀（减少冲突）
- 确定性（同一 key 结果相同）
三、哈希冲突
不同 key 可能映射到同一下标（冲突）。解决方法：
- 链地址法（拉链法）：每个槽挂一个链表
- 开放地址法：冲突就找下一个空位（线性探测、双重哈希）
拉链法：
array[3] → [("name","张三"), ("eman","李四")] # 链表四、负载因子与扩容
负载因子 = 元素数 / 数组长度。它越大，冲突越多，性能下降。
# 当负载因子超过阈值（如 0.75）
# → 扩容：数组翻倍，所有元素重新哈希
# 扩容是 O(n)，但均摊到每次插入仍是 O(1)Python dict 的负载因子阈值约 2/3，Java HashMap 是 0.75。超过就扩容，保证查找始终接近 O(1)。
五、性能
操作 平均 最坏（全冲突）
查找 O(1) O(n)
插入 O(1) O(n)
删除 O(1) O(n)六、典型应用
- 字典 / 映射：key-value 存储
- 缓存：Redis、Memcached
- 去重：把元素存哈希表，查重 O(1)
- 数据库索引：哈希索引
- 两数之和：经典面试题，用哈希表降到 O(n)
七、注意事项
- 无序（除非用 LinkedHashMap）
- 不支持范围查询（要用树）
- 哈希计算有开销，数据量小时未必比数组快
八、小结
哈希表是"空间换时间"的典范。理解它的原理，能用好各种语言里的字典/Map，也是算法优化的利器（O(n) → O(1)）。