04 哈希表 — 最快的查找结构

李永乐式比喻：

• 你去图书馆借书，如果书架没有分类，你要挨个书架找 -> O(n)
• 图书馆有索书号系统（A 类文学、B 类数学...）-> 你直接去对应区域 -> O(1)
• 哈希冲突：两个人选的索书号相同怎么办？在这个架子上再加一层小架子（链地址法）
• 负载因子：架子上书太多会影响找书效率，所以要换更大的图书馆（扩容）

---

名词映射

英文	中文	本质	比喻
Hash Table	哈希表	键到值的映射，通过哈希函数定位	索书号系统
Hash Function	哈希函数	把键转换为数组索引的算法	书到索书号的转换规则
Hash Collision	哈希冲突	两个不同键映射到同一位置	两本书索书号相同
Chaining	链地址法	数组每个位置挂一个链表	同索书号的书放同一格
Load Factor	负载因子	元素数 / 数组容量	书架的使用率
Rehashing	重新哈希	容量不够时扩容并重新分布	换更大的图书馆重新编号

---

哈希表结构

---

负载因子与扩容

---

企业场景

• 数据库索引：MySQL 哈希索引（Memory 引擎）-- 等值查询 O(1)
• 缓存系统：Redis / Memcached -- 全部基于哈希表
• 去重：Python 的 set / dict 底层都是哈希表
• 分布式哈希：一致性哈希 -- 缓存分片、负载均衡

---

AI 协作

AI 生成：
  - 实现哈希表（含哈希函数、链地址法、扩容）-- ~100 行 Python
  - LeetCode 1 两数之和 -- 用哈希表降到 O(n)
  - 分析和设计合理的哈希函数

人类决策：
  - 键值对无序 -> 哈希表
  - 需要范围查询（值 > 100）-> 哈希表不行 -> 用树
  - 需要保证顺序 -> 用 LinkedHashMap