哈希表：用一次计算换一次查找
数组靠下标 O(1) 定位，但下标只能是「第几个」。哈希表想要的是：用任意的键（字符串、对象）也能 O(1) 定位。办法是造一个函数，把键算成一个数组下标——这个函数叫哈希函数，这个数组叫桶数组。查找从「逐个比对」变成「算一下地址、直接去拿」，这是哈希表存在的全部理由。
面试问哈希表，考点从来不是「它是 O(1)」，而是那些让 O(1) 破功的地方：哈希冲突怎么解决、负载因子到多少要扩容、扩容为什么要 rehash、以及 O(1) 什么时候会退化成 O(n)。HashMap 的源码题、Redis 的渐进式 rehash、布隆过滤器，全从这几个点长出来。
一、哈希函数：把键压成下标
哈希函数干两件事：先把键算成一个大整数（hashCode），再把这个整数映射到 [0, 桶数) 的下标（通常取模或位与）。好的哈希函数要满足：
- 确定性：同一个键每次算出同一个值。
- 均匀性：不同键尽量散开，别扎堆到同一个桶。扎堆就退化成链表。
- 快：它在每次增删查前都要跑一遍，本身不能慢。
字符串常用多项式哈希（如 hash = hash*31 + c,Java String.hashCode 就是 31 这个乘子——奇质数、且 31*x 能被编译成 (x<<5)-x）。把大整数落到桶下标，若桶数是 2 的幂，可以用 hash & (n-1) 代替 hash % n（位与比取模快，且等价）。这正是 Java HashMap 桶数恒为 2 的幂的原因。
HashMap 还做了个「扰动」：h ^ (h >>> 16),把高 16 位混进低位。因为落桶用的是低位（& (n-1)），如果哈希值只有高位有差异、低位都一样，不扰动就会大量冲突。扰动一步用极小代价让高位也参与决定桶号。
二、冲突：两个键落到同一个桶
抽屉原理保证冲突不可避免——键空间无穷、桶有限。解决冲突有两条主流路线：
链地址法（拉链）。 每个桶挂一条链表，落到同一桶的键串起来。查找时先定位桶，再在链上逐个 equals 比对。Java HashMap、大多数语言的 map 用这个。冲突多时链变长，查找从 O(1) 滑向 O(链长)。Java 8 起做了优化：单桶链表长度 ≥ 8 且桶数 ≥ 64 时转红黑树,把最坏单桶从 O(n) 压到 O(log n)，退化到 ≤ 6 再退回链表。这是防「哈希碰撞攻击」（构造大量同桶键把 map 打成链表）的护栏。
开放寻址法。 不挂链，冲突了就往后找下一个空桶（线性探测 +1、二次探测 +i²、双重哈希）。所有数据都在桶数组里，cache 友好，没有链表节点的指针开销。代价是删除麻烦（不能直接置空，否则探测链断掉，要用「墓碑」标记），且负载因子一高，探测链变长，性能塌得比拉链快。Python 的 dict、Go 的 map（变体）走这条路。
两条路线的取舍：拉链对高负载更稳、删除简单；开放寻址内存紧凑、cache 友好但对负载因子敏感。
三、负载因子与扩容：O(1) 的维持费
负载因子 = 元素数 / 桶数，衡量桶数组多满。装得越满，冲突越多，链越长。所以哈希表设一个阈值（Java HashMap 默认 0.75），一旦 size > 桶数 × 0.75 就扩容：桶数翻倍，然后把所有已有元素**重新哈希（rehash）**到新桶数组。
为什么必须 rehash？因为落桶用的是 hash & (n-1),n 变了，下标就变了，旧位置在新表里是错的。扩容是 O(n) 操作（每个元素都要重算位置搬家），但它摊到大量插入里，均摊后单次插入仍是 O(1)——和动态数组扩容是同一套均摊逻辑。
0.75 是空间和时间的折中：太小（比如 0.5）冲突少但浪费桶、扩容频繁；太大（比如 0.95）省内存但冲突飙升。Java 选 0.75 是「泊松分布下单桶元素数落在 8 的概率极低」的经验值，也解释了为什么转树阈值定在 8。
扩容的代价是一次性抖动：某次插入正好触发扩容，这一次要搬 n 个元素，延迟尖峰。对延迟敏感的系统，Redis 用渐进式 rehash化解：扩容时同时保留新旧两张表，每次增删查顺带迁移一小部分桶，把 O(n) 的搬家摊到很多次操作里，避免一次卡顿。查找时新旧表都查。这是「大 O 均摊」在生产系统里的真实落地。
四、执行走查：put 一个已存在的 key
以 Java HashMap 风格走一遍 put("b", 20),假设桶数 16，"b" 落到桶 5，桶 5 上已有链 ("b",9) -> ("r",7)：
| 步骤 | 动作 | 状态 |
|---|---|---|
| 1 | 算 hash，扰动，& 15 得桶号 5 | 定位到桶 5 |
| 2 | 遍历桶 5 的链，equals 比对 key | 第一个节点 key=="b" 命中 |
| 3 | key 已存在 → 覆盖 value，不新增节点 | ("b",20) -> ("r",7),size 不变 |
| 4 | 未触发扩容（size 未过阈值） | 返回旧值 9 |
关键点：哈希相等只是「可能同一个键」，必须再用 equals 确认。哈希是快速筛选，equals 是最终判定。这直接推出那条铁律：重写 equals 必须同时重写 hashCode。若两个逻辑相等的对象 hashCode 不同，它们会落到不同桶，put 进去的对象再也 get 不出来——map 里存了却查不到，是最隐蔽的 bug 之一。反过来，hashCode 相同、equals 不同是允许的（就是冲突），只是会同桶。
**改一行验证：**若把可变对象当 key（比如一个字段会被修改的对象），put 之后改了参与 hashCode 的字段，它的哈希变了、该去的桶变了，但它人还在旧桶——get 用新哈希去新桶找，找不到。所以哈希表的 key 应当是不可变的（String、Integer 天然不可变，正是好 key 的原因）。
五、哈希表能变出什么
- HashSet 就是「只用 key 的 HashMap」，value 塞个占位对象。集合去重、判存在，都是它。
- LinkedHashMap 在哈希桶之外再用一条双链表串起插入/访问顺序，于是能「有序遍历」或做 LRU（按访问顺序淘汰）。这是「哈希表 + 链表」的经典组合：哈希给 O(1) 定位，链表给顺序。
- 一致性哈希 解决分布式缓存扩缩容时「哪些 key 要搬家」。普通取模
hash % 机器数,加一台机器几乎所有 key 重新分布（缓存雪崩）；一致性哈希把节点和 key 映射到一个环上，加减节点只影响相邻区间，搬家量最小。 - 布隆过滤器：用多个哈希函数 + 一个位数组，判断「元素一定不在或可能在」。它省内存、快，代价是有假阳性（说在的可能不在），没有假阴性（说不在的一定不在）。缓存穿透防护、爬虫去重、大数据集判存在用它——牺牲精确性换空间。
六、面试收口
- 哈希表为什么 O(1)？ 哈希函数把键直接算成下标，省掉逐个比对。前提是哈希均匀、负载因子受控。
- 什么时候退化成 O(n)？ 冲突严重（哈希差或被碰撞攻击），单桶链过长。Java 8 用「链长 ≥8 转红黑树」把最坏压到 O(log n) 兜底。
- 为什么要扩容和 rehash？ 负载因子超阈值（默认 0.75）冲突变多；桶数变了下标就变，必须重算位置搬家。均摊仍 O(1)，但有一次性抖动，Redis 用渐进式 rehash 化解。
- equals 和 hashCode 为什么要一起重写？ 哈希定桶、equals 定相等；两者不一致会导致「存进去查不出来」。key 必须不可变。
- 判存在但内存吃紧怎么办？ 布隆过滤器：位数组 + 多哈希，有假阳性无假阴性，防缓存穿透。
哈希表的桶数组是数组（见「数组与链表」），冲突链是链表，转树用的红黑树是「图/树」那条线里的平衡二叉搜索树——它是好几种基础结构拼出来的复合体，也是「用空间换时间」最典型的例子。