图 1：本文封面，点明主题——O(1) 背后站着一整套冲突与扩容设计。
「两数之和」这类题很多人都刷过：用哈希表把 O(n²) 的枚举压成 O(n) 的查询。解题套路就那一招，本文不重复展开；今天换个角度，聊这一招背后的东西——哈希表自己是怎么设计的。真要让它撑起几百万个键，冲突处理、负载因子、扩容再散列这些词，就从面试考点变成了实打实的性能开关。
结论先行：哈希表的 O(1) 不是免费的，它由三层设计托底——冲突处理策略、负载因子驱动的扩容机制、针对退化场景的防御手段。看懂这三层，工业级哈希表的取舍就全在图里了。
第一层：冲突处理的两条路线。
哈希函数再好，两个不同的键落进同一个桶也是必然事件，区别只在概率。处理冲突有两条主流路线。
链地址法：每个桶挂一条链，冲突的元素依次接在链上；查询先定位桶，再沿线逐个比较。优点是直观、装得再满也能工作；代价是链越长查询越慢。工业实现会给链长设防——以 JDK 的 HashMap 为例，链表长度达到 8 且桶数组容量不低于 64 时转成红黑树，单桶查询从 O(n) 压回 O(log n)；元素减到 6 以下再转回链表，避免在阈值附近反复横跳。为什么偏偏是 8？OpenJDK 源码注释给了答案：默认负载下桶内节点数近似服从参数 0.5 的泊松分布，链长达到 8 的概率不足千万分之一——正常散列根本到不了这个长度，真到了，多半是遇上了恶意构造的哈希碰撞，树化就是为这种攻击准备的保险。
开放寻址法：桶里只放一个元素，冲突时按探测序列（线性、二次、双重散列）向后找下一个空槽。不需要额外指针，内存紧凑、缓存友好；但删除是麻烦事——直接清空槽位会把探测链拦腰截断，后面的元素就「找不到了」，所以删除只能放一个墓碑标记，告诉探测序列「这里曾经有过，继续往后走」。墓碑攒多了还得整体清理，这是开放寻址的隐形成本。
第二层：负载因子与扩容再散列。
桶就那么多，键越塞越多，冲突必然加剧。工业哈希表用负载因子（元素数 ÷ 桶数）当水位线：JDK HashMap 的默认值是 0.75，元素数超过「桶数 × 负载因子」就触发扩容——容量约翻倍，所有键按新容量重新散列，初始容量默认是 16。
0.75 是时间与空间的折中：调低，冲突少、查询快，但大量桶空着，浪费内存还拖慢遍历；调高，空间省了，冲突链变长。扩容的代价也要心里有数：所有键重新算位置、重新挂链，是一次 O(n) 的整体搬迁。所以官方文档建议：能预估数据量就一次给足初始容量，比让它自动长大更划算。
还有一个工程上常踩的点：HashMap 的迭代器是 fail-fast 的——遍历过程中发生结构性修改（增删键），直接抛 ConcurrentModificationException。扩容本身就是结构性修改，「边遍历边往里塞」在单线程里也是雷区。
第三层：用代码把论断跑一遍。
下面这份代码实现了一个迷你链地址哈希表，并用它实测负载因子的影响：同样塞入 960 个键，分别用 0.75 和 4.0 的负载因子，看桶数、再散列次数与最长冲突链的差异。用 Node.js 22.15.0 直接运行（node hashtable.js）即可：
'use strict';
// 链地址法哈希表：桶数组 + 冲突链，负载因子超阈值即翻倍再散列
class HashTable {
constructor(capacity = 16, loadFactor = 0.75) {
this.buckets = new Array(capacity).fill(null);
this.size = 0;
this.loadFactor = loadFactor;
this.rehashCount = 0;
}
hash(key) { // 简化版字符串散列（FNV-1a 32 位）
let h = 0x811c9dc5;
for (const ch of String(key)) {
h ^= ch.codePointAt(0);
h = Math.imul(h, 0x01000193);
}
return (h >>> 0) % this.buckets.length;
}
put(key, value) {
const idx = this.hash(key);
for (let node = this.buckets[idx]; node; node = node.next) {
if (node.key === key) { node.value = value; return; }
}
this.buckets[idx] = { key, value, next: this.buckets[idx] };
this.size++;
if (this.size > this.buckets.length * this.loadFactor) this.rehash();
}
get(key) {
for (let node = this.buckets[this.hash(key)]; node; node = node.next) {
if (node.key === key) return node.value;
}
return undefined;
}
rehash() { // 容量翻倍，所有键按新容量重新散列
const old = this.buckets;
this.buckets = new Array(old.length * 2).fill(null);
for (const head of old) {
for (let node = head; node; node = node.next) {
const idx = this.hash(node.key);
this.buckets[idx] = { key: node.key, value: node.value, next: this.buckets[idx] };
}
}
this.rehashCount++;
}
maxChain() {
let max = 0;
for (const head of this.buckets) {
let len = 0;
for (let node = head; node; node = node.next) len++;
if (len > max) max = len;
}
return max;
}
}
// 实验：同样塞入 960 个键，负载因子 0.75 与 4.0 的对比
for (const lf of [0.75, 4.0]) {
const t = new HashTable(16, lf);
for (let i = 0; i < 960; i++) t.put(`key-${i}`, i);
console.log(`负载因子 ${lf}：桶数 ${t.buckets.length}，再散列 ${t.rehashCount} 次，最长冲突链 ${t.maxChain()}`);
}
const t = new HashTable(16, 0.75);
for (let i = 0; i < 100; i++) t.put(`k${i}`, i * 10);
console.log(`rehash 后读 k42 = ${t.get('k42')}（应为 420），读不存在键 = ${t.get('nope')}`);
实测输出：
负载因子 0.75：桶数 2048，再散列 7 次，最长冲突链 4
负载因子 4：桶数 256，再散列 4 次，最长冲突链 9
rehash 后读 k42 = 420（应为 420），读不存在键 = undefined
两行对比把折中摆得明明白白：负载因子放宽到 4，桶数省了八倍（256 对 2048），再散列少了三次，代价是最长冲突链从 4 涨到 9——查询时平均要多比好几个节点。空间与速度，永远是这笔账的两头。
图 2：两条冲突处理路线与扩容再散列的完整流程。
常见误区有三。 一是把 O(1) 当成零成本，忽略了哈希函数要算、冲突链要比、扩容要搬迁，常数因子里全是文章。二是低估 hashCode 质量：散列值分布不均，再好的表设计也救不回来。三是扩容期间改结构或边遍历边增删，撞上 fail-fast 才知道疼。
落到行动建议：用之前预估数据量、一次给足容量；键优先用不可变对象；高并发场景别裸用普通哈希表，换并发实现。
下次再有人问你「哈希表为什么快」，别只答 O(1)——把冲突、负载因子、再散列这三层讲出来，才是完整的答案。你在项目里给哈希表调过容量或负载因子吗？效果怎么样？欢迎聊聊。