哈希表 / Set / Map 深度解析

一、哈希表原理

什么是哈希表

哈希表（Hash Table）是一种基于键值对的数据结构，通过哈希函数将键映射到数组中的某个位置（桶/Bucket），从而实现近似 O(1) 时间复杂度的增删查操作。

核心思想：用空间换时间。

键(Key) ──▶ 哈希函数 h(key) ──▶ 数组下标 index ──▶ 存储/读取值(Value)

哈希函数的作用

哈希函数将任意长度的输入映射为固定范围内的整数。一个优秀的哈希函数需要满足：

确定性：相同输入永远产生相同输出
均匀性：输出尽可能均匀分布在整个值域
高效性：计算速度快

h("alice") = 3         h("bob")   = 7         h("carol") = 1

  index:  0     1       2     3       4     5     6     7
        ┌─────┬───────┬─────┬───────┬─────┬─────┬─────┬─────┐
        │     │ carol │     │ alice │     │     │     │ bob │
        └─────┴───────┴─────┴───────┴─────┴─────┴─────┴─────┘

哈希冲突

当两个不同的键经过哈希函数计算得到相同下标时，就产生了哈希冲突。这是不可避免的（鸽巢原理）。

两种主流解决方案：

1. 链地址法（Separate Chaining）

每个桶存储一个链表，冲突的元素追加到链表尾部。

h("alice") = 3    h("dave") = 3    h("bob") = 7

  index:  0     1     2        3           4     5     6     7
        ┌─────┬─────┬─────┬──────────┬─────┬─────┬─────┬──────┐
        │     │     │     │  ┌─────┐ │     │     │     │┌────┐│
        │     │     │     │  │alice│ │     │     │     ││bob ││
        │     │     │     │  └──┬──┘ │     │     │     │└────┘│
        │     │     │     │     │    │     │     │     │      │
        │     │     │     │  ┌──▼──┐ │     │     │     │      │
        │     │     │     │  │dave │ │     │     │     │      │
        │     │     │     │  └─────┘ │     │     │     │      │
        └─────┴─────┴─────┴──────────┴─────┴─────┴─────┴──────┘

查找 "dave"：
  1. h("dave") = 3 → 定位到 index 3
  2. 遍历链表：alice ≠ dave → dave = dave ✓ 找到

优点：实现简单，删除方便，对负载因子容忍度高缺点：链表过长时退化为 O(n)，缓存局部性差

2. 开放寻址法（Open Addressing）

所有元素都存在数组本身中。冲突时按一定探测序列寻找下一个空位。

线性探测：依次检查 index+1, index+2, ...

h("alice") = 3    h("dave") = 3    h("eve") = 3

  插入 alice → index 3
  index:  0     1     2     3       4     5     6     7
        ┌─────┬─────┬─────┬───────┬─────┬─────┬─────┬─────┐
        │     │     │     │ alice │     │     │     │     │
        └─────┴─────┴─────┴───────┴─────┴─────┴─────┴─────┘

  插入 dave → index 3 冲突 → 探测 4 → 空位，放入
  index:  0     1     2     3       4      5     6     7
        ┌─────┬─────┬─────┬───────┬──────┬─────┬─────┬─────┐
        │     │     │     │ alice │ dave │     │     │     │
        └─────┴─────┴─────┴───────┴──────┴─────┴─────┴─────┘

  插入 eve → index 3 冲突 → 4 冲突 → 探测 5 → 空位，放入
  index:  0     1     2     3       4      5     6     7
        ┌─────┬─────┬─────┬───────┬──────┬─────┬─────┬─────┐
        │     │     │     │ alice │ dave │ eve │     │     │
        └─────┴─────┴─────┴───────┴──────┴─────┴─────┴─────┘

优点：缓存友好，内存紧凑缺点：容易产生聚集（Clustering），删除操作复杂（需要标记墓碑/tombstone）

负载因子与扩容

负载因子（Load Factor） = 已存储元素数 / 桶总数

负载因子 α = n / m

n = 已存储元素数
m = 桶（Bucket）总数

链地址法通常在 α > 0.75 时触发扩容
开放寻址法通常在 α > 0.5 ~ 0.7 时触发扩容

扩容过程：

扩容前 (capacity = 4, size = 3, α = 0.75):

  index:  0       1      2     3
        ┌───────┬──────┬─────┬──────┐
        │ alice │ bob  │     │ dave │
        └───────┴──────┴─────┴──────┘

触发扩容 → 新容量 = 4 × 2 = 8
所有元素 rehash，重新分配位置：

  index:  0     1       2     3     4      5     6     7
        ┌─────┬───────┬─────┬─────┬──────┬─────┬─────┬──────┐
        │     │ alice │     │     │ dave │     │     │ bob  │
        └─────┴───────┴─────┴─────┴──────┴─────┴─────┴──────┘

手写简易 HashMap

class HashMap {
  constructor(initialCapacity = 16, loadFactor = 0.75) {
    this._capacity = initialCapacity
    this._loadFactor = loadFactor
    this._size = 0
    this._buckets = new Array(this._capacity).fill(null)
  }

  _hash(key) {
    let hash = 0
    const str = String(key)
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) | 0
    }
    return (hash >>> 0) % this._capacity
  }

  put(key, value) {
    if ((this._size + 1) / this._capacity > this._loadFactor) {
      this._resize()
    }
    const index = this._hash(key)
    let node = this._buckets[index]
    while (node) {
      if (node.key === key) {
        node.value = value
        return
      }
      node = node.next
    }
    this._buckets[index] = { key, value, next: this._buckets[index] }
    this._size++
  }

  get(key) {
    const index = this._hash(key)
    let node = this._buckets[index]
    while (node) {
      if (node.key === key) return node.value
      node = node.next
    }
    return undefined
  }

  delete(key) {
    const index = this._hash(key)
    let node = this._buckets[index]
    let prev = null
    while (node) {
      if (node.key === key) {
        if (prev) {
          prev.next = node.next
        } else {
          this._buckets[index] = node.next
        }
        this._size--
        return true
      }
      prev = node
      node = node.next
    }
    return false
  }

  _resize() {
    const oldBuckets = this._buckets
    this._capacity *= 2
    this._buckets = new Array(this._capacity).fill(null)
    this._size = 0
    for (const head of oldBuckets) {
      let node = head
      while (node) {
        this.put(node.key, node.value)
        node = node.next
      }
    }
  }

  get size() {
    return this._size
  }
}

const map = new HashMap()
map.put("name", "Alice")
map.put("age", 25)
map.put("city", "Beijing")

console.log(map.get("name"))    // "Alice"
console.log(map.get("age"))     // 25
console.log(map.size)           // 3

map.delete("age")
console.log(map.get("age"))     // undefined
console.log(map.size)           // 2

复杂度分析：

操作	平均	最坏
put	O(1)	O(n)
get	O(1)	O(n)
delete	O(1)	O(n)
resize	O(n)	O(n)

最坏情况发生在所有键哈希到同一个桶（链退化为链表）。

二、JS 中的 Map

Map vs Object 对比

维度	Map	Object
键类型	任意类型（对象、函数、原始值）	仅 String 和 Symbol
顺序	按插入顺序迭代	ES2015+ 整数键升序 → 字符串键插入序 → Symbol 键插入序
大小	`map.size` O(1) 获取	`Object.keys(obj).length` O(n)
性能	频繁增删场景更优	静态结构读取略快（V8 Hidden Class 优化）
序列化	无原生 JSON 支持	`JSON.stringify` 原生支持
原型链	无原型键污染风险	继承 `Object.prototype`（`toString` 等）
迭代协议	原生可迭代（实现 `Symbol.iterator`）	需要 `Object.keys/values/entries`

Map API 详解

const map = new Map()

map.set("a", 1)
map.set("b", 2)
map.set("c", 3)

map.get("a")           // 1
map.has("b")           // true
map.size               // 3

map.delete("b")        // true
map.has("b")           // false

map.set("a", 100)
map.get("a")           // 100

const objKey = { id: 1 }
const fnKey = () => {}
map.set(objKey, "object value")
map.set(fnKey, "function value")
map.get(objKey)        // "object value"

const map2 = new Map([
  ["x", 10],
  ["y", 20],
  ["z", 30],
])

for (const [key, value] of map2) {
  console.log(key, value)
}

map2.forEach((value, key) => {
  console.log(key, value)
})

const keys = [...map2.keys()]      // ["x", "y", "z"]
const values = [...map2.values()]  // [10, 20, 30]
const entries = [...map2.entries()]

map2.clear()
map2.size   // 0

WeakMap 原理

WeakMap 与 Map 的核心区别在于：键是弱引用。

普通 Map：

  Map ───强引用──▶ key 对象 ──▶ 对象不会被 GC 回收
                               （即使外部已无引用）

WeakMap：

  WeakMap ─弱引用─ ─ ▷ key 对象
                        │
                        └──▶ 当外部无强引用时 → GC 可回收
                             WeakMap 中对应条目自动消失

特性：

键必须是对象（不能是原始值）
键是弱引用，不阻止垃圾回收
不可枚举：没有 size、keys()、values()、entries()、forEach()
不可枚举的原因：GC 时机不确定，枚举结果不可预测

WeakMap API：仅有 get、set、has、delete 四个方法。

使用场景一：私有数据

const _privateData = new WeakMap()

class User {
  constructor(name, password) {
    _privateData.set(this, { name, password })
  }

  getName() {
    return _privateData.get(this).name
  }

  verify(input) {
    return _privateData.get(this).password === input
  }
}

const user = new User("Alice", "secret123")
console.log(user.getName())          // "Alice"
console.log(user.verify("secret123")) // true
console.log(user.password)           // undefined

使用场景二：DOM 元素缓存

const domMetadata = new WeakMap()

function bindMetadata(element, data) {
  domMetadata.set(element, data)
}

function getMetadata(element) {
  return domMetadata.get(element)
}

const btn = document.querySelector("#myBtn")
bindMetadata(btn, { clickCount: 0, bindTime: Date.now() })

getMetadata(btn)  // { clickCount: 0, bindTime: ... }

当 DOM 元素从页面移除且无其他引用时，WeakMap 中的条目会自动被 GC 清理，避免内存泄漏。

使用场景三：防止内存泄漏的缓存

const cache = new WeakMap()

function expensiveComputation(obj) {
  if (cache.has(obj)) {
    return cache.get(obj)
  }
  const result = { ...obj, computed: JSON.stringify(obj).length }
  cache.set(obj, result)
  return result
}

let data = { name: "Alice", scores: [95, 87, 92] }
expensiveComputation(data)  // 计算并缓存
expensiveComputation(data)  // 命中缓存

data = null  // 外部引用断开 → GC 回收 data → cache 中条目自动消失

三、JS 中的 Set

Set API 详解

const set = new Set()

set.add(1)
set.add(2)
set.add(3)
set.add(2)          // 重复值被忽略

set.size             // 3
set.has(2)           // true

set.delete(2)        // true
set.has(2)           // false

const set2 = new Set([1, 2, 3, 4, 5])

for (const value of set2) {
  console.log(value)
}

set2.forEach((value) => {
  console.log(value)
})

const keys = [...set2.keys()]      // [1, 2, 3, 4, 5]
const values = [...set2.values()]  // [1, 2, 3, 4, 5]
const entries = [...set2.entries()] // [[1,1], [2,2], ...]

set2.clear()
set2.size   // 0

Set 判断相等使用 SameValueZero 算法：与 === 类似，但 NaN === NaN 为 true。

const set = new Set()
set.add(NaN)
set.add(NaN)
set.size       // 1

set.add(0)
set.add(-0)
set.size       // 2  (NaN + 0，因为 +0 === -0)

WeakSet 原理与使用场景

WeakSet 与 Set 的关系类似于 WeakMap 与 Map：

值必须是对象
弱引用，不阻止 GC
不可枚举，仅有 add、has、delete 三个方法

典型场景：标记对象

const visited = new WeakSet()

function processNode(node) {
  if (visited.has(node)) return
  visited.add(node)
  // ...处理节点
}

典型场景：防止构造函数被作为普通函数调用

const _instances = new WeakSet()

class Foo {
  constructor() {
    if (_instances.has(this)) {
      throw new Error("Foo is already instantiated")
    }
    _instances.add(this)
  }
}

Set 实现数组去重 / 交集 / 并集 / 差集

const a = [1, 2, 3, 4, 5]
const b = [3, 4, 5, 6, 7]

const unique = [...new Set(a)]

const union = [...new Set([...a, ...b])]
// [1, 2, 3, 4, 5, 6, 7]

const setB = new Set(b)
const intersection = a.filter((x) => setB.has(x))
// [3, 4, 5]

const difference = a.filter((x) => !setB.has(x))
// [1, 2]

const symmetricDifference = [
  ...a.filter((x) => !setB.has(x)),
  ...b.filter((x) => !new Set(a).has(x)),
]
// [1, 2, 6, 7]

复杂度对比：

操作	双重循环	Set 方案
去重	O(n²)	O(n)
交集	O(n×m)	O(n+m)
并集	O(n×m)	O(n+m)
差集	O(n×m)	O(n+m)

四、经典算法题

1. 两数之和（LeetCode 1）

给定一个整数数组 nums 和一个整数目标值 target，在数组中找出和为 target 的两个整数，返回它们的下标。

思路分析：暴力解法是双重循环 O(n²)。利用哈希表可以在遍历过程中记录每个数的下标，对于当前数 nums[i]，查找 target - nums[i] 是否已经在哈希表中。这将时间复杂度降为 O(n)。

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

console.log(twoSum([2, 7, 11, 15], 9))   // [0, 1]
console.log(twoSum([3, 2, 4], 6))        // [1, 2]
console.log(twoSum([3, 3], 6))           // [0, 1]

维度	复杂度
时间	O(n)
空间	O(n)

2. 字母异位词分组（LeetCode 49）

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

思路分析：异位词排序后的结果相同。将排序后的字符串作为哈希表的键，原始字符串作为值加入对应数组。

function groupAnagrams(strs) {
  const map = new Map()
  for (const str of strs) {
    const key = [...str].sort().join("")
    if (!map.has(key)) {
      map.set(key, [])
    }
    map.get(key).push(str)
  }
  return [...map.values()]
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

维度	复杂度
时间	O(n·k·log k)，k 为最长字符串长度
空间	O(n·k)

优化：用字符计数代替排序，将时间复杂度降为 O(n·k)。

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

维度	复杂度
时间	O(n·k)
空间	O(n·k)

3. 最长连续序列（LeetCode 128）

给定一个未排序的整数数组 nums，找出最长连续序列的长度。要求 O(n) 时间复杂度。

思路分析：将所有数放入 Set。对于每个数，只有当 num - 1 不在 Set 中时（说明它是某个连续序列的起点），才开始向后延伸计数。这保证每个元素最多被访问两次。

function longestConsecutive(nums) {
  const set = new Set(nums)
  let maxLen = 0

  for (const num of set) {
    if (set.has(num - 1)) continue

    let currentNum = num
    let currentLen = 1

    while (set.has(currentNum + 1)) {
      currentNum++
      currentLen++
    }

    maxLen = Math.max(maxLen, currentLen)
  }

  return maxLen
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2]))      // 4 → [1,2,3,4]
console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])) // 9

维度	复杂度
时间	O(n)
空间	O(n)

关键洞察：虽然有嵌套循环，但 while 内部的总执行次数不会超过 n，因为每个元素只会作为某个序列的一部分被访问一次。

4. 两个数组的交集 II（LeetCode 350）

给定两个整数数组 nums1 和 nums2，以数组形式返回两者的交集。结果中每个元素出现的次数应与其在两个数组中都出现的次数一致。

思路分析：用哈希表记录较短数组中每个元素的出现次数，然后遍历另一个数组，匹配时计数减一。

function intersect(nums1, nums2) {
  if (nums1.length > nums2.length) {
    return intersect(nums2, nums1)
  }

  const map = new Map()
  for (const num of nums1) {
    map.set(num, (map.get(num) || 0) + 1)
  }

  const result = []
  for (const num of nums2) {
    const count = map.get(num)
    if (count > 0) {
      result.push(num)
      map.set(num, count - 1)
    }
  }

  return result
}

console.log(intersect([1, 2, 2, 1], [2, 2]))        // [2, 2]
console.log(intersect([4, 9, 5], [9, 4, 9, 8, 4]))  // [4, 9]

维度	复杂度
时间	O(n + m)
空间	O(min(n, m))

五、V8 引擎中 Map/Set 的底层实现

有序哈希表（Deterministic Hash Table）

V8 中的 Map 和 Set 基于 Deterministic Hash Table（确定性哈希表）实现，这是一种能够保持插入顺序的特殊哈希表结构。

传统哈希表中，元素的存储位置由哈希值决定，遍历顺序不可预测。V8 的实现将索引表与数据区分离：

传统哈希表：
┌──────────┬───────────────────────────────────────────┐
│  Bucket  │  存储区（位置由 hash 决定，无序）           │
├──────────┼───────────────────────────────────────────┤
│  0       │  { key: "b", value: 2 }                   │
│  1       │  (empty)                                   │
│  2       │  { key: "c", value: 3 }                   │
│  3       │  { key: "a", value: 1 }                   │
└──────────┴───────────────────────────────────────────┘
遍历顺序：b → c → a（取决于哈希值，非插入序）


V8 有序哈希表：

Hash Table（索引区）         Data Table（数据区，按插入顺序排列）
┌──────────┬──────────┐     ┌───────┬─────────┬─────────┬──────────┐
│  Bucket  │  Entry   │     │ Index │  Key    │  Value  │  Chain   │
├──────────┼──────────┤     ├───────┼─────────┼─────────┼──────────┤
│  0       │    2     │────▶│  0    │  "a"    │    1    │   -1     │
│  1       │    0     │     │  1    │  "b"    │    2    │   -1     │
│  2       │   -1     │     │  2    │  "c"    │    3    │   -1     │
│  3       │    1     │     └───────┴─────────┴─────────┴──────────┘
└──────────┴──────────┘          ▲
         │                       │
         └── Bucket 存的是        └── 按插入顺序存储
             数据区的 Index            遍历时顺序遍历此区

插入顺序：a → b → c
遍历顺序：a → b → c ✓（保持插入序）

核心设计

分离存储：

HashTable（桶数组）：每个桶存储数据区中的起始索引
DataTable（数据区）：按插入顺序线性存储所有条目
Chain 字段：处理冲突，指向同一桶中下一条目的索引，-1 表示链尾

查找过程：

查找 key = "c"：

1. 计算 hash("c") % bucketCount → Bucket 0
2. 读取 Bucket[0] = 2
3. 访问 DataTable[2] → key = "c" ✓ 匹配
4. 返回 value = 3

删除策略：

删除时不移动数据区中的元素（避免破坏索引关系），而是在被删元素位置标记 hole（空洞）。当空洞过多时触发 rehash，压缩数据区。

删除 "b" 后：

DataTable：
┌───────┬─────────┬─────────┬──────────┐
│ Index │  Key    │  Value  │  Chain   │
├───────┼─────────┼─────────┼──────────┤
│  0    │  "a"    │    1    │   -1     │
│  1    │ (hole)  │ (hole)  │  (hole)  │  ← 标记为空洞
│  2    │  "c"    │    3    │   -1     │
└───────┴─────────┴─────────┴──────────┘

遍历时跳过 hole：a → c（顺序不变）

与传统哈希表的区别

特性	传统哈希表	V8 有序哈希表
遍历顺序	不确定	保持插入顺序
内存布局	分散（链表/探测）	数据区连续线性存储
缓存友好性	链地址法较差	数据区遍历缓存友好
删除方式	直接移除/标记	标记 hole + 延迟压缩
额外开销	无	需要维护索引区 + chain
迭代复杂度	O(m)（m=桶数）	O(n)（n=元素数）

六、面试题精选（5 道）

面试题 1：实现一个 LRU 缓存

设计一个满足 LRU（最近最少使用）缓存约束的数据结构，get 和 put 操作均为 O(1)。

解答：利用 Map 保持插入顺序的特性，最近使用的元素放到末尾，淘汰时删除第一个元素。

class LRUCache {
  constructor(capacity) {
    this._capacity = capacity
    this._cache = new Map()
  }

  get(key) {
    if (!this._cache.has(key)) return -1
    const value = this._cache.get(key)
    this._cache.delete(key)
    this._cache.set(key, value)
    return value
  }

  put(key, value) {
    if (this._cache.has(key)) {
      this._cache.delete(key)
    }
    this._cache.set(key, value)
    if (this._cache.size > this._capacity) {
      const firstKey = this._cache.keys().next().value
      this._cache.delete(firstKey)
    }
  }
}

const lru = new LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
console.log(lru.get(1))    // 1
lru.put(3, 3)
console.log(lru.get(2))    // -1（被淘汰）
lru.put(4, 4)
console.log(lru.get(1))    // -1（被淘汰）
console.log(lru.get(3))    // 3
console.log(lru.get(4))    // 4

时间复杂度：get O(1)，put O(1) 空间复杂度：O(capacity)

面试题 2：Map 的键比较使用什么算法？和 === 有什么区别？

解答：

Map 使用 SameValueZero 算法判断键的相等性。与 ===（Strict Equality）的区别在于对 NaN 的处理：

比较	`===`	SameValueZero
`NaN === NaN`	`false`	`true`
`+0 === -0`	`true`	`true`

const map = new Map()

map.set(NaN, "value1")
map.set(NaN, "value2")
console.log(map.size)         // 1（NaN 被视为同一个键）
console.log(map.get(NaN))    // "value2"

map.set(0, "zero")
map.set(-0, "negative zero")
console.log(map.size)         // 2（上面 NaN + 这里 0，-0 覆盖了 +0）
console.log(map.get(0))      // "negative zero"

另外还有一个 SameValue 算法（Object.is 使用），它与 SameValueZero 的区别是 Object.is(+0, -0) 返回 false。

面试题 3：WeakMap 为什么不能被枚举？

解答：

WeakMap 的键是弱引用，意味着如果键对象在外部没有其他引用，垃圾回收器（GC）可以随时回收它。而 GC 的运行时机是不确定的：

如果允许枚举，两次枚举之间可能因为 GC 运行导致结果不同
这种不确定性会引发难以调试的 Bug
暴露 GC 行为会破坏 JavaScript 的抽象层

因此规范设计上就不提供 size、keys()、values()、entries()、forEach() 等枚举方法。

const wm = new WeakMap()
let obj = { data: "important" }
wm.set(obj, "metadata")

wm.has(obj)    // true

obj = null     // 外部引用断开

// 某个时刻 GC 运行后：
// wm 中的条目已被自动移除
// 如果此时能枚举，结果将不可预测

面试题 4：如何用 Map 实现一个带过期时间的缓存？

解答：

class TTLCache {
  constructor() {
    this._cache = new Map()
  }

  set(key, value, ttl) {
    const expireAt = Date.now() + ttl
    this._cache.set(key, { value, expireAt })
  }

  get(key) {
    const entry = this._cache.get(key)
    if (!entry) return undefined
    if (Date.now() > entry.expireAt) {
      this._cache.delete(key)
      return undefined
    }
    return entry.value
  }

  has(key) {
    return this.get(key) !== undefined
  }

  delete(key) {
    return this._cache.delete(key)
  }

  cleanup() {
    const now = Date.now()
    for (const [key, entry] of this._cache) {
      if (now > entry.expireAt) {
        this._cache.delete(key)
      }
    }
  }

  get size() {
    this.cleanup()
    return this._cache.size
  }
}

const cache = new TTLCache()
cache.set("token", "abc123", 3000)

console.log(cache.get("token"))  // "abc123"

setTimeout(() => {
  console.log(cache.get("token"))  // undefined（已过期）
}, 4000)

时间复杂度：get/set/delete O(1)，cleanup O(n) 空间复杂度：O(n)

面试题 5：为什么说频繁增删键值对时 Map 比 Object 性能更好？

解答：

无 Hidden Class 开销：V8 为 Object 维护 Hidden Class（隐藏类）来加速属性访问。每次增删属性都可能导致 Hidden Class 转换（transition），甚至退化为字典模式（Dictionary Mode）。Map 的内部实现本身就是哈希表，增删操作不触发 Hidden Class 变更。
无原型链查找：Object 的属性访问需要考虑原型链，虽然 V8 做了 Inline Cache 优化，但动态增删属性会使缓存失效。Map 不存在原型链问题。
哈希表优化：Map 底层是专门为键值存储优化的有序哈希表。Object 在作为字典使用时，V8 也会切换到哈希表实现，但这个切换本身有开销，且 Object 需要兼顾属性描述符等元信息。
删除操作：Object 的 delete 操作在 V8 中代价较高，会导致 Hidden Class 退化。Map 的 delete 是哈希表的常规操作，代价低。

const N = 1_000_000

console.time("Map add/delete")
const map = new Map()
for (let i = 0; i < N; i++) map.set(`key${i}`, i)
for (let i = 0; i < N; i++) map.delete(`key${i}`)
console.timeEnd("Map add/delete")

console.time("Object add/delete")
const obj = {}
for (let i = 0; i < N; i++) obj[`key${i}`] = i
for (let i = 0; i < N; i++) delete obj[`key${i}`]
console.timeEnd("Object add/delete")

七、追问思考

如果要实现一个支持并发读写的线程安全哈希表（在 Web Worker 场景下），你会如何设计？SharedArrayBuffer 和 Atomics 能否帮助？
ES2024 引入的 Map.groupBy() 和 Object.groupBy() 在实现原理上有什么区别？它们的性能特征如何？
在 React/Vue 中使用 Map 或 Set 作为状态时，框架的响应式系统能否正确追踪其变化？如果不能，如何解决？
如果需要一个既支持 O(1) 查找，又支持按插入顺序遍历，还支持按优先级排序的数据结构，你会如何设计？
WeakRef 和 FinalizationRegistry 与 WeakMap/WeakSet 有何关系？它们分别适合什么场景？能否用 WeakRef + Map 模拟 WeakMap 的行为？

哈希表 / Set / Map 深度解析 ​

一、哈希表原理 ​

什么是哈希表 ​

哈希函数的作用 ​

哈希冲突 ​

1. 链地址法（Separate Chaining） ​

2. 开放寻址法（Open Addressing） ​

负载因子与扩容 ​

手写简易 HashMap ​

二、JS 中的 Map ​

Map vs Object 对比 ​

Map API 详解 ​

WeakMap 原理 ​

使用场景一：私有数据 ​

使用场景二：DOM 元素缓存 ​

使用场景三：防止内存泄漏的缓存 ​

三、JS 中的 Set ​

Set API 详解 ​

WeakSet 原理与使用场景 ​

Set 实现数组去重 / 交集 / 并集 / 差集 ​

四、经典算法题 ​

1. 两数之和（LeetCode 1） ​

2. 字母异位词分组（LeetCode 49） ​

3. 最长连续序列（LeetCode 128） ​

4. 两个数组的交集 II（LeetCode 350） ​

五、V8 引擎中 Map/Set 的底层实现 ​

有序哈希表（Deterministic Hash Table） ​

核心设计 ​

与传统哈希表的区别 ​

六、面试题精选（5 道） ​

面试题 1：实现一个 LRU 缓存 ​

面试题 2：Map 的键比较使用什么算法？和 === 有什么区别？ ​

面试题 3：WeakMap 为什么不能被枚举？ ​

面试题 4：如何用 Map 实现一个带过期时间的缓存？ ​

面试题 5：为什么说频繁增删键值对时 Map 比 Object 性能更好？ ​

七、追问思考 ​