哈希表

讲解

哈希表把「键」通过一个哈希函数映射到桶里，实现平均 O(1) 的插入、删除、查找。它的思想一句话：用空间换时间——把键的存在性直接「记住」，查找时不再遍历。JavaScript 里的 Map 和 Set 就是工程化的哈希表：Map 保序、键可以是任意类型；Set 只存键。日常算法题里，「见过没有」「出现过几次」「对应的下标在哪」这三类问题的第一直觉都该是哈希表。

用哈希表解题有两个关键设计。一是键的设计：字母异位词分组，键选排序后的字符串；判断数独合法性，键选「行号+数字」这样的组合。键选对了，问题就归约成了查表。二是写入时机：两数之和中，「先查后存」保证不会把同一个元素用两次；和为 K 的子数组中，「先存 0:1」这个初始项保证从头开始的子数组能被算到。这些顺序细节是哈希表题目最易错的地方。

理论层面了解两点即可。哈希冲突：不同键映射到同一桶，工程上靠链地址法或开放寻址法解决，负载因子过高时 rehash 扩容——这是 Map 查找「平均」O(1) 而非「最坏」O(1) 的原因。设计题里的 LRU 缓存则是哈希表的进阶形态：哈希表负责 O(1) 定位，双向链表负责 O(1) 维护使用顺序，两者合体才是完整答案。面试中 LRU 出现频率极高，值得练到肌肉记忆。

示例

三件套：两数之和（先查后存）、字母异位词分组（键的设计）、LRU 缓存（Map 的插入序特性正好是现成的「使用顺序」队列——delete 再 set 就把键移到最新）：

import assert from 'node:assert/strict';

function twoSum(nums, target) {
  const indexOf = new Map(); // 值 -> 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i]; // 先查
    indexOf.set(nums[i], i); // 后存：保证不用同一个元素两次
  }
  return [-1, -1];
}

function groupAnagrams(strs) {
  const groups = new Map(); // 排序后的字符串 -> 原字符串数组
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return [...groups.values()];
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // Map 迭代按插入序：最旧的在最前
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value); // 重新插入 = 标记为最近使用
    return value;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const oldest = this.map.keys().next().value; // 最旧的键
      this.map.delete(oldest);
    }
  }
}

assert.deepStrictEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
assert.deepStrictEqual(twoSum([3, 2, 4], 6), [1, 2]);

const grouped = groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']);
assert.strictEqual(grouped.length, 3);
assert.deepStrictEqual([...grouped[0]].sort(), ['ate', 'eat', 'tea']);

const lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
assert.strictEqual(lru.get(1), 1); // 1 变为最近使用
lru.put(3, 3); // 容量超限，淘汰最久未用的 key 2
assert.strictEqual(lru.get(2), -1);
lru.put(4, 4); // 淘汰 key 1
assert.strictEqual(lru.get(1), -1);
assert.strictEqual(lru.get(3), 3);
assert.strictEqual(lru.get(4), 4);

console.log('哈希表示例全部通过');

LRU 这版实现借用了 JS Map 保持插入序的特性，比教科书里的「哈希表 + 手写双向链表」短得多，面试时能手写双向链表版更佳，但理解这版的机制（delete + set 等价于移动到队首）已经抓住了本质。

常见坑

• 两数之和中「先存后查」：会把元素和自己配对（如 target = 2x 时下标 [i, i]），必须先查再存。
• 用普通对象当哈希表：{} 的键会被转成字符串且有原型链干扰（'constructor' 这类键会撞名）；算法题里统一用 Map/Set。
• 键的设计不合理：分组异位词用排序字符串当键是 O(k log k)，也可以用 26 字母计数数组当键做到 O(k)——能说清取舍即可。
• 以为哈希表严格 O(1)：它是平均 O(1)；被追问最坏情况时答「退化 O(n)，工程中靠好的哈希函数和扩容避免」。
• LRU 忘记更新已有键的位置：put 一个已存在的键也必须刷新它的「最近使用」状态，否则淘汰顺序出错。

小结

哈希表用空间换时间，平均 O(1) 查找；解题三板斧是见过没有、计数、存下标；键设计和存取顺序是易错点；LRU = 哈希表 + 使用顺序队列。下一章看另一种靠指针串起来的结构：链表。