哈希表

Map 的底层

V8 的 Map 是哈希表 + 插入顺序链表的组合：哈希表负责 O(1) 查找，额外一条双向链表记住插入顺序，所以迭代顺序稳定、delete 也不打乱顺序。

Set 就是把 Map 的值去掉、只留键，去重靠 SameValueZero：NaN 等于 NaN，+0 等于 -0，对象按引用。所以 new Set([NaN, NaN]).size === 1，而 new Set([{}, {}]).size === 2。

常见误区

很多人以为哈希表查找永远是 O(1)。 实际上那是平均与均摊情况；全部 key 落到同一个桶时退化成 O(n)，扩容那一次也是 O(n)。

很多人以为 Object 当字典和 Map 等价。 实际上 Object 的键会被转成字符串（obj[1] 和 obj['1'] 是同一个），还会继承原型属性，for...in 能遍历到原型上的键；做字典请用 Object.create(null) 或直接上 Map。

常考题型

1. 两数之和

思路：边遍历边把"值 → 下标"存进 Map，对每个数先查 target - nums[i] 是否出现过。

function twoSum(nums, target) {
    const seen = new Map();
    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];
        if (seen.has(need)) return [seen.get(need), i];
        seen.set(nums[i], i);
    }
    return [];
}

时间 O(n)，空间 O(n)。易错点：先查后存，才避免同一个元素用两次；返回的是下标不是值。

2. 字母异位词分组

思路：把字符计数拼成 key，异位词的计数数组完全相同，自然落进同一个桶。

function groupAnagrams(strs) {
    const map = new Map();
    for (const s of strs) {
        const count = new Array(26).fill(0);
        for (const ch of s) count[ch.charCodeAt(0) - 97]++;
        const key = count.join('#');
        if (!map.has(key)) map.set(key, []);
        map.get(key).push(s);
    }
    return [...map.values()];
}

时间 O(n·k)，空间 O(n·k)，k 是字符串长度。易错点：用排序做 key 会多一个 log k；计数数组必须转成字符串才能当 key。

3. 最长连续序列

思路：全部丢进 Set，只从"没有前驱"的数开始往后数，保证每个数只被访问一次。

function longestConsecutive(nums) {
    const set = new Set(nums);
    let best = 0;
    for (const n of set) {
        if (set.has(n - 1)) continue; // 不是起点，跳过
        let cur = n;
        let len = 1;
        while (set.has(cur + 1)) {
            cur++;
            len++;
        }
        best = Math.max(best, len);
    }
    return best;
}

时间 O(n)，空间 O(n)。易错点：不判断起点会退化成 O(n²)；空数组要返回 0。

4. 手写 LRU 缓存

思路：Map 的迭代顺序就是插入顺序，get 命中后先 delete 再 set 把键挪到末尾，超容量就删第一个键。

class LRUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.map = new 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);
        } else if (this.map.size >= this.cap) {
            this.map.delete(this.map.keys().next().value); // 最久未使用
        }
        this.map.set(key, value);
    }
}

get 和 put 均摊 O(1)，空间 O(capacity)。易错点：put 已存在的键也要先删再插，否则顺序不更新；容量为 0 时不能插入。

关联阅读

• 数组与链表：链地址法的桶就是数组 + 链表
• 栈与队列：LRU 的顺序维护本质是一个双端队列
• 树与堆：Java 8 的 HashMap 在长链表上会转成红黑树