哈希表

是什么，为什么存在

哈希表保存键值条目，并支持按精确键查找。它不扫描全部条目，而是根据键计算哈希值，用这个数字选出一小部分存储区域，再在其中用相等规则确认哪个条目才是目标。

这种结构适合反复回答同一类问题：哪个客户拥有某个 ID、某个令牌是否出现过，或者某个单词出现了几次。线性扫描每次查询需要 O(n) 次比较。运行良好的哈希表能让插入、查找和删除达到预期 O(1)，因此工作量通常不会随条目总数一起增长。

「预期」二字才是实际契约。多个键可能选中同一存储位置，实现仍必须区分它们。存储容量也有限，所以表会定期增长，并重新分布已有条目。

当操作是精确键查找，且没有有用的顺序时，映射很合适。如果需要前驱查询、范围查询或有序遍历，排序数组或平衡树通常更合适。如果键本来就是较小已知范围内的稠密非负整数，直接使用数组索引会更简单。

多数语言提供类似字典的接口，同时隐藏具体表示。Python dict、Java HashMap 和许多其他集合采用哈希表技术，但内部布局并不相同。ECMAScript 要求 Map 提供平均次线性访问，却没有要求引擎必须使用哈希表；本主题只用 JavaScript Map 展示规范规定的键行为，需要观察内部机制时则构建一个教学实现。

接口背后的契约

每个键都要经过两项判断。哈希函数决定去哪里查找，相等规则决定候选项是不是同一个逻辑键。两者都不能安全地取代另一个。

可哈希（hashable） 的键具有足够稳定的哈希与相等行为，能满足集合规则。核心一致性规则是单向的：如果两个键相等，它们必须产生相同哈希值。不同的键可以产生相同哈希值，因为表具有冲突处理策略。

哈希表不只是缓存。它还能实现索引、符号表、邻接映射、频率计数器、连接、去重集合和注册表。在这些场景中，最难的设计选择往往是键代表什么，而不是调用哪个集合方法。

工作原理

最简单的哈希表拥有一个桶数组。哈希函数把键转换为整数，再通过 hash % capacity 一类缩减运算选择数组索引。选中的桶保存零个或多个可能共用该索引的条目。

查找与插入

一次查找沿着很窄的路径完成：

1. 用表配置的哈希函数计算键的哈希值。
2. 根据当前容量把哈希值缩减为桶索引。
3. 沿着表的冲突处理路径检查候选条目。
4. 用配置的相等规则，把候选键与请求键比较。
5. 返回匹配值，或者报告键不存在。

插入从同样的搜索开始。如果相等的键已经存在，映射就更新该条目的值，而不增加大小。否则，它会添加一个不同条目，并可能触发扩容。

删除必须保留查找所依赖的搜索路径。从链中删除节点很直接。开放寻址表通常需要墓碑标记或修复簇，因为直接清空槽位可能让后面的冲突条目无法到达。

冲突是正常现象

不同键得到相同哈希值或桶索引时，就发生 哈希冲突（hash collision） 。键空间通常远大于桶数组，所以从数学上说冲突不可避免。正确性来自相等检查与冲突处理，而不是期待哈希值唯一。

拉链法（separate chaining） 在每个桶中保存一个条目集合，查找只遍历选中的链。它实现简单，删除不会干扰其他桶，但每条链会增加分配与指针遍历开销。

开放寻址把条目直接保存在桶数组中。发生冲突时，它根据线性探测、二次探测或双重哈希等规则检查其他位置。这种布局可以改善局部性，但必须谨慎处理探测行为、删除标记以及接近满载的表。

负载与增长

负载因子（load factor） 等于已存条目数除以桶数。对于拉链法，它预示平均链压力；对于开放寻址，它预示寻找空槽的难度。不同实现会选择不同阈值，因为布局、缓存行为与内存目标并不相同。

超过阈值后，表通常会分配更大的桶数组，再重新插入或移动已有条目。按旧索引直接复制条目是错误的，因为容量参与了索引选择。同一个完整哈希值在容量变化后可能映射到不同桶。

执行扩容的那次操作具有 O(n) 成本。几何增长把这些偶发复制分摊到许多廉价插入上，因此正常假设下，插入具有 摊还 O(1)（amortized O(1)） 成本，但并非每一次插入都是常数时间。

相等规则定义键标识

不同运行时暴露不同的相等策略。Java 集合可以接收 相等比较器（equality comparer） ；Python 键使用相互兼容的 __eq__ 与 __hash__；JavaScript Map 使用 同值零相等（SameValueZero） 。在 SameValueZero 下，NaN 等于 NaN，正零与负零相等，不同对象则按标识比较。

对于 { warehouse, sku } 这样的业务键，对象标识往往不是预期含义。可以改用规范化的不可变字符串、驻留键对象，或者支持值相等的语言功能。表示必须没有歧义：直接用分隔符连接字段时，只要字段自身能包含该分隔符，编码就会失效。

成本模型

这些界限只计算表本身的工作，不包括计算键哈希值的成本。除非哈希已被缓存，对长字符串求哈希的成本与检查的字符数成正比。把表操作称为「常数时间」时，不能隐藏无界键长度的成本。

示例

下面的示例把可观察的语言语义与教学用内部机制分开。三个文件都用本地 Node 24 运行，后面的输出均为实际捕获结果。

观察键相等规则

JavaScript Map 能展示对象标识和 SameValueZero，而无需暴露桶。同字段的两个对象仍是不同键；重复的 NaN 与带符号零则会定位到已有条目。

第二次 NaN 赋值更新了第一次的条目，+0 也能找到用 -0 保存的值。新的对象字面量找不到 firstOrder，因为字段相同不会改变对象标识。这个结果不能证明引擎使用桶，只展示规范定义的键关系。

priceByKey.get() 也无法区分缺失键与值为 undefined 的已有键。这个区别会影响行为时，应使用 priceByKey.has(key)。如果外围 API 能安全保留一个特殊值，也可以使用哨兵值。

处理冲突与扩容

这个小型映射接收字符串键，使用拉链法，并在负载因子超过 0.75 时增长。它只是教学实现，不能替代运行时集合：其中省略了删除、校验、迭代 API 与生产级哈希加固。

class StringHashMap {
  constructor(capacity = 4) {
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }
  hash(key) {
    let hash = 2166136261;
    for (const character of key) {
      hash = Math.imul(hash ^ character.codePointAt(0), 16777619) >>> 0;
    }
    return hash;
  }
  set(key, value) {
    const bucket = this.buckets[this.hash(key) % this.buckets.length];
    const entry = bucket.find(([storedKey]) => storedKey === key);
    if (entry) {
      entry[1] = value;
      return;
    }
    bucket.push([key, value]);
    this.size += 1;
    if (this.size / this.buckets.length > 0.75) this.resize();
  }
  get(key) {
    const bucket = this.buckets[this.hash(key) % this.buckets.length];
    return bucket.find(([storedKey]) => storedKey === key)?.[1];
  }
  resize() {
    const entries = this.buckets.flat();
    this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
    this.size = 0;
    for (const [key, value] of entries) this.set(key, value);
  }
}
const balances = new StringHashMap();
[["apples", 5], ["pears", 3], ["plums", 8], ["melon", 2]]
  .forEach(([key, value]) => balances.set(key, value));
console.log(`capacity: ${balances.buckets.length}`);
console.log(`values: ${balances.get("apples")}, ${balances.get("plums")}`);
console.log(`bucket sizes: ${balances.buckets.map((bucket) => bucket.length).join(",")}`);

capacity: 8
values: 5, 8
bucket sizes: 1,0,1,0,2,0,0,0

第四个不同键插入后，负载从 3/4 变成 4/4，超过阈值，容量翻倍为八。每个旧条目都再次经过 set()，因此会按新容量取得索引。重新插入前把 size 清零，可以保证计数正确。

最终桶大小中出现了一个 2：扩容以后，"apples" 与 "melon" 仍在第四号桶发生冲突。桶保留了完整键，get() 也会检查相等性，因此两次查找都正确。如果只保存哈希值，就会丢失这种区别。

哈希循环使用 Unicode 码点和 32 位乘法，让示例结果保持确定。这并不表示 FNV 风格哈希适合恶意输入，也不是在复现 JavaScript 引擎的内部哈希。生产集合可能会随机化哈希值或采用其他防御措施。

构建复合业务键

当调用方会重建键对象时，JavaScript 对象标识无法表达值相等。只要编码能保留字段边界，就可以使用规范化字符串。长度前缀避免了直接用 ":" 连接字段造成的歧义。

function canonicalSkuKey({ warehouse, sku }) {
  return `${warehouse.length}:${warehouse}${sku.length}:${sku}`;
}

const stock = new Map();
const parisWidget = { warehouse: "PAR", sku: "W-7" };
stock.set(canonicalSkuKey(parisWidget), 12);

const lookup = { sku: "W-7", warehouse: "PAR" };
console.log(`key: ${canonicalSkuKey(lookup)}`);
console.log(`stock: ${stock.get(canonicalSkuKey(lookup))}`);

lookup.sku = "W-8";
console.log(`after mutation: ${stock.get(canonicalSkuKey(lookup))}`);
console.log(`original: ${stock.get(canonicalSkuKey(parisWidget))}`);

key: 3:PAR3:W-7
stock: 12
after mutation: undefined
original: 12

属性顺序没有影响，因为函数按固定顺序读取具名字段。修改 lookup 会改变后续查找生成的键，但无法移动或破坏已经保存的字符串键。原始记录仍能生成原来的键。

规范化还必须定义类型、归一化、大小写规则和缺失值。如果仓库标识不区分大小写，就要在编码前归一化，并在每个插入与查找路径应用同一规则。对于任意结构化数据，应优先使用明确规定的序列化格式或值键功能，避免自行发明不完整的编码。

陷阱

把哈希值当作标识

**修复：**保留完整键或同样不会冲突的规范表示，并按定义好的相等规则比较候选项。构造两个必定冲突的键，确认两个值都仍然可以访问。

破坏哈希与相等契约

**修复：**从同一组不可变字段和归一化步骤推导相等与哈希规则。优先使用不可变键类型；否则应在修改键字段前删除条目，修改后再重新插入。

把常数时间说成最坏情况保证

**修复：**准确说法是在负载受控、哈希分布充分时，预期成本为 O(1)。限制不可信键的长度，使用运行时提供的加固集合；延迟很重要时，要基准测试代表性分布与对抗性分布。

扩容后不重新哈希

**修复：**按新表的几何结构，重新插入或正确移动每个活动条目。在每个增长边界前后立即查找全部条目，并覆盖发生冲突的键。

混淆缺失与已存值

**修复：**使用集合的成员检查操作，例如 Map.has()；也可以返回带标签的结果，明确区分是否存在和值本身。测试要包含每一种假值与一个缺失键。

把普通对象用作不可信字典

**修复：**键可以是任意值时使用 Map；如果必须与字符串属性互操作，则创建无原型对象。在信任边界校验键，并使用自有属性检查，而不是继承成员检查。

延伸阅读

• ECMAScript 语言规范：Map 对象
• Java SE 25 API：HashMap
• Python 3.14 文档：映射类型
• Go 编程语言规范：映射类型
• MDN Web Docs：Map