2.4 - Set/Map、WeakSet/WeakMap

JavaScript面试

2026年2月4日

JavaScript 集合数据结构深度解析

深入理解 Set/Map、WeakSet/WeakMap 的原理、应用与面试要点

一、Set 深度解析

1.1 Set 的本质

Set 是 ES6 引入的集合数据结构,类似于数组,但成员值都是唯一的,没有重复值。

const set = new Set([1, 2, 3, 3, 4]);
console.log(set); // Set(4) { 1, 2, 3, 4 }
console.log(set.size); // 4

1.2 Set 的核心特性

1.2.1 值的唯一性

Set 使用 “Same-value-zero equality” 算法判断值是否相同:

const set = new Set();

// 基本类型去重
set.add(1);
set.add('1');
set.add(true);
set.add(1); // 重复,不会添加
console.log(set); // Set(3) { 1, '1', true }

// NaN 的特殊处理
set.add(NaN);
set.add(NaN); // NaN 被认为是相等的
console.log(set.has(NaN)); // true

// 对象引用
const obj1 = { a: 1 };
const obj2 = { a: 1 };
set.add(obj1);
set.add(obj2); // 不同引用,都会添加
console.log(set.size); // 包含两个对象

// undefined 和 null
set.add(undefined);
set.add(null);
set.add(undefined); // 重复
console.log(set.has(undefined)); // true

重要面试点:

NaN === NaN 返回 false,但 Set 认为 NaN 相等
+0 和 -0 在 Set 中被认为是相等的
对象比较的是引用地址,不是值

1.2.2 有序性

Set 保持插入顺序:

const set = new Set([3, 1, 4, 1, 5]);
console.log([...set]); // [3, 1, 4, 5] 保持插入顺序

1.3 Set 的 API

const set = new Set();

// 添加元素
set.add(1).add(2).add(3); // 支持链式调用

// 删除元素
set.delete(2); // 返回 boolean
console.log(set.has(2)); // false

// 检查元素
console.log(set.has(1)); // true

// 清空
set.clear();
console.log(set.size); // 0

// 遍历方法
const fruits = new Set(['apple', 'banana', 'orange']);

// forEach
fruits.forEach((value, key, set) => {
  console.log(value); // 注意: value === key
});

// for...of
for (let fruit of fruits) {
  console.log(fruit);
}

// 迭代器方法
console.log([...fruits.keys()]); // ['apple', 'banana', 'orange']
console.log([...fruits.values()]); // ['apple', 'banana', 'orange']
console.log([...fruits.entries()]); // [['apple', 'apple'], ...]

面试重点: Set 的 forEach 回调函数第一个和第二个参数都是值,这是为了与 Map 保持 API 一致性。

1.4 Set 的实际应用

1.4.1 数组去重

// 基本类型去重
const arr = [1, 2, 2, 3, 4, 4, 5];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr); // [1, 2, 3, 4, 5]

// 字符串去重
const str = 'aabbccdd';
const uniqueStr = [...new Set(str)].join('');
console.log(uniqueStr); // 'abcd'

// 复杂对象去重(需要自定义逻辑)
const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 1, name: 'Alice' }
];

// 方案1: 使用 Map
const uniqueUsers = [...new Map(users.map(u => [u.id, u])).values()];

// 方案2: 使用 filter + findIndex
const uniqueUsers2 = users.filter((user, index, arr) => 
  arr.findIndex(u => u.id === user.id) === index
);

1.4.2 集合运算

// 并集
function union(setA, setB) {
  return new Set([...setA, ...setB]);
}

// 交集
function intersection(setA, setB) {
  return new Set([...setA].filter(x => setB.has(x)));
}

// 差集
function difference(setA, setB) {
  return new Set([...setA].filter(x => !setB.has(x)));
}

// 对称差集(并集 - 交集)
function symmetricDifference(setA, setB) {
  const diff1 = difference(setA, setB);
  const diff2 = difference(setB, setA);
  return union(diff1, diff2);
}

// 示例
const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

console.log([...union(setA, setB)]); // [1, 2, 3, 4, 5, 6]
console.log([...intersection(setA, setB)]); // [3, 4]
console.log([...difference(setA, setB)]); // [1, 2]
console.log([...symmetricDifference(setA, setB)]); // [1, 2, 5, 6]

1.4.3 判断超集和子集

function isSuperset(set, subset) {
  for (let elem of subset) {
    if (!set.has(elem)) {
      return false;
    }
  }
  return true;
}

function isSubset(subset, set) {
  return isSuperset(set, subset);
}

const setA = new Set([1, 2, 3, 4, 5]);
const setB = new Set([2, 3]);

console.log(isSuperset(setA, setB)); // true
console.log(isSubset(setB, setA)); // true

二、Map 深度解析

2.1 Map 的本质

Map 是键值对的集合,类似于对象,但键可以是任意类型,不仅限于字符串。

const map = new Map();
map.set('name', 'Alice');
map.set(42, 'answer');
map.set(true, 'boolean key');
map.set({ id: 1 }, 'object key');

console.log(map.size); // 4

2.2 Map vs Object

特性	Map	Object
键的类型	任意类型	String/Symbol
键的顺序	插入顺序	无序(部分有序)
大小获取	`map.size`	`Object.keys(obj).length`
迭代	原生可迭代	需要 `Object.keys()`
性能	频繁增删更优	小数据量更优
原型链	无原型链污染	有原型链

// Object 的限制
const obj = {};
obj[{ id: 1 }] = 'value1';
obj[{ id: 2 }] = 'value2';
console.log(obj); // { '[object Object]': 'value2' } 键被转为字符串

// Map 可以使用对象作为键
const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 2 };
map.set(key1, 'value1');
map.set(key2, 'value2');
console.log(map.get(key1)); // 'value1'
console.log(map.get(key2)); // 'value2'

2.3 Map 的 API

const map = new Map();

// 设置键值对
map.set('a', 1);
map.set('b', 2);
map.set('c', 3);

// 获取值
console.log(map.get('a')); // 1
console.log(map.get('d')); // undefined

// 检查键是否存在
console.log(map.has('a')); // true

// 删除键值对
map.delete('b');
console.log(map.has('b')); // false

// 清空
map.clear();
console.log(map.size); // 0

// 通过数组初始化
const map2 = new Map([
  ['name', 'Alice'],
  ['age', 25],
  ['city', 'Beijing']
]);

// 遍历方法
map2.forEach((value, key, map) => {
  console.log(`${key}: ${value}`);
});

// 迭代器
console.log([...map2.keys()]); // ['name', 'age', 'city']
console.log([...map2.values()]); // ['Alice', 25, 'Beijing']
console.log([...map2.entries()]); // [['name', 'Alice'], ...]

// for...of
for (let [key, value] of map2) {
  console.log(`${key}: ${value}`);
}

2.4 Map 的实际应用

2.4.1 缓存/记忆化

// 斐波那契数列缓存
function fibonacci() {
  const cache = new Map();
  
  return function fib(n) {
    if (n <= 1) return n;
    
    if (cache.has(n)) {
      return cache.get(n);
    }
    
    const result = fib(n - 1) + fib(n - 2);
    cache.set(n, result);
    return result;
  };
}

const fib = fibonacci();
console.log(fib(10)); // 55
console.log(fib(50)); // 12586269025 快速计算

2.4.2 对象属性统计

function countProperties(obj) {
  const counts = new Map();
  
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      const type = typeof obj[key];
      counts.set(type, (counts.get(type) || 0) + 1);
    }
  }
  
  return counts;
}

const obj = { a: 1, b: '2', c: true, d: null, e: undefined };
const counts = countProperties(obj);
console.log([...counts]); // [['number', 1], ['string', 1], ...]

2.4.3 DOM 节点元数据存储

// 使用 Map 存储 DOM 节点的额外数据
class DOMDataStore {
  constructor() {
    this.store = new Map();
  }
  
  set(element, key, value) {
    if (!this.store.has(element)) {
      this.store.set(element, new Map());
    }
    this.store.get(element).set(key, value);
  }
  
  get(element, key) {
    const elementData = this.store.get(element);
    return elementData ? elementData.get(key) : undefined;
  }
  
  delete(element) {
    return this.store.delete(element);
  }
}

// 使用示例
const dataStore = new DOMDataStore();
const button = document.querySelector('button');
dataStore.set(button, 'clickCount', 0);
dataStore.set(button, 'lastClicked', Date.now());

2.4.4 LRU 缓存实现

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(3);
lru.put(1, 'a');
lru.put(2, 'b');
lru.put(3, 'c');
console.log(lru.get(1)); // 'a'
lru.put(4, 'd'); // 移除 2
console.log(lru.get(2)); // -1

三、WeakSet 深度解析

3.1 WeakSet 的本质

WeakSet 是 Set 的变体,但有重要区别:

只能存储对象,不能存储基本类型值
对象引用是弱引用,不会阻止垃圾回收
不可迭代,没有 size 属性

const ws = new WeakSet();

const obj1 = { id: 1 };
const obj2 = { id: 2 };

ws.add(obj1);
ws.add(obj2);

console.log(ws.has(obj1)); // true

// 不能添加基本类型
// ws.add(1); // TypeError: Invalid value used in weak set

3.2 弱引用的原理

// 强引用示例(Set)
let obj = { data: 'important' };
const set = new Set();
set.add(obj);

obj = null; // obj 引用解除
// 但对象仍然在 set 中,不会被垃圾回收
console.log(set.size); // 1

// 弱引用示例(WeakSet)
let obj2 = { data: 'important' };
const ws = new WeakSet();
ws.add(obj2);

obj2 = null; // obj2 引用解除
// 对象可能被垃圾回收(取决于 GC 时机)
// 无法验证 ws.size,因为 WeakSet 没有 size 属性

关键理解:

强引用: Set、Map、数组、对象属性都会创建强引用
弱引用: WeakSet、WeakMap 不会阻止垃圾回收
GC 时机不确定,开发者无法精确控制

3.3 WeakSet 的 API

WeakSet 只有三个方法:

const ws = new WeakSet();
const obj = { id: 1 };

ws.add(obj);        // 添加对象
ws.has(obj);        // 检查对象是否存在
ws.delete(obj);     // 删除对象

// 没有以下方法:
// ws.size          // ❌
// ws.clear()       // ❌
// ws.keys()        // ❌
// ws.values()      // ❌
// ws.forEach()     // ❌

3.4 WeakSet 的实际应用

3.4.1 标记对象(不影响生命周期)

// 标记 DOM 节点是否已禁用
const disabledElements = new WeakSet();

function disableElement(element) {
  element.disabled = true;
  disabledElements.add(element);
}

function isDisabled(element) {
  return disabledElements.has(element);
}

// 当 DOM 节点被移除时,WeakSet 中的引用会自动清理
const button = document.querySelector('button');
disableElement(button);
console.log(isDisabled(button)); // true

// button 从 DOM 移除后,会被垃圾回收
button.remove();

3.4.2 防止对象被多次处理

// 防止循环引用导致的无限递归
function traverseObject(obj, visited = new WeakSet()) {
  // 避免重复访问
  if (visited.has(obj)) {
    console.log('已访问过,跳过');
    return;
  }
  
  visited.add(obj);
  
  for (let key in obj) {
    if (typeof obj[key] === 'object' && obj[key] !== null) {
      traverseObject(obj[key], visited);
    }
  }
}

// 循环引用的对象
const a = { name: 'a' };
const b = { name: 'b' };
a.ref = b;
b.ref = a;

traverseObject(a); // 不会无限递归

3.4.3 私有数据存储

// 使用 WeakSet 实现简单的私有标记
const privateData = new WeakSet();

class User {
  constructor(name) {
    this.name = name;
    privateData.add(this); // 标记为已初始化
  }
  
  isInitialized() {
    return privateData.has(this);
  }
}

const user = new User('Alice');
console.log(user.isInitialized()); // true

四、WeakMap 深度解析

4.1 WeakMap 的本质

WeakMap 是 Map 的变体:

键必须是对象,值可以是任意类型
键是弱引用,不会阻止垃圾回收
不可迭代,没有 size 属性

const wm = new WeakMap();

const key1 = { id: 1 };
const key2 = { id: 2 };

wm.set(key1, 'value1');
wm.set(key2, 'value2');

console.log(wm.get(key1)); // 'value1'

// 键必须是对象
// wm.set('string', 'value'); // TypeError

4.2 WeakMap 的 API

const wm = new WeakMap();
const obj = { id: 1 };

wm.set(obj, { data: 'value' });  // 设置
wm.get(obj);                     // 获取
wm.has(obj);                     // 检查
wm.delete(obj);                  // 删除

// 没有以下方法:
// wm.size          // ❌
// wm.clear()       // ❌
// wm.keys()        // ❌
// wm.values()      // ❌
// wm.forEach()     // ❌

4.3 WeakMap 的实际应用

4.3.1 DOM 节点元数据存储(防止内存泄漏)

// 使用 WeakMap 存储 DOM 节点数据
const elementData = new WeakMap();

function setElementData(element, data) {
  elementData.set(element, data);
}

function getElementData(element) {
  return elementData.get(element);
}

// 使用示例
const button = document.querySelector('button');
setElementData(button, {
  clickCount: 0,
  lastClicked: null
});

button.addEventListener('click', () => {
  const data = getElementData(button);
  data.clickCount++;
  data.lastClicked = Date.now();
});

// 当 button 从 DOM 移除时,WeakMap 中的数据会自动清理
// 不会造成内存泄漏

4.3.2 对象私有数据实现

// 使用 WeakMap 实现真正的私有属性
const privateData = new WeakMap();

class Person {
  constructor(name, age) {
    privateData.set(this, { name, age });
  }
  
  getName() {
    return privateData.get(this).name;
  }
  
  getAge() {
    return privateData.get(this).age;
  }
  
  setAge(age) {
    const data = privateData.get(this);
    data.age = age;
  }
}

const person = new Person('Alice', 25);
console.log(person.getName()); // 'Alice'
console.log(person.name); // undefined - 真正的私有
console.log(privateData.get(person)); // undefined - 外部无法访问

4.3.3 缓存计算结果

// 使用 WeakMap 缓存对象的计算结果
const cache = new WeakMap();

function expensiveOperation(obj) {
  if (cache.has(obj)) {
    console.log('从缓存返回');
    return cache.get(obj);
  }
  
  console.log('执行计算');
  const result = obj.value * 2; // 假设这是昂贵的计算
  cache.set(obj, result);
  return result;
}

const obj1 = { value: 10 };
console.log(expensiveOperation(obj1)); // 执行计算 -> 20
console.log(expensiveOperation(obj1)); // 从缓存返回 -> 20

// 当 obj1 不再被引用时,缓存会自动清理

4.3.4 实现观察者模式

// 使用 WeakMap 实现观察者模式
const observers = new WeakMap();

function observe(target, callback) {
  if (!observers.has(target)) {
    observers.set(target, []);
  }
  observers.get(target).push(callback);
}

function notify(target, data) {
  const callbacks = observers.get(target);
  if (callbacks) {
    callbacks.forEach(callback => callback(data));
  }
}

// 使用示例
const user = { name: 'Alice' };

observe(user, data => console.log('Observer 1:', data));
observe(user, data => console.log('Observer 2:', data));

notify(user, { action: 'update', name: 'Bob' });
// Observer 1: { action: 'update', name: 'Bob' }
// Observer 2: { action: 'update', name: 'Bob' }

4.3.5 记录对象方法调用次数

const callCounts = new WeakMap();

function trackMethodCalls(obj, methodName) {
  const originalMethod = obj[methodName];
  
  if (!callCounts.has(obj)) {
    callCounts.set(obj, {});
  }
  
  const counts = callCounts.get(obj);
  counts[methodName] = 0;
  
  obj[methodName] = function(...args) {
    counts[methodName]++;
    return originalMethod.apply(this, args);
  };
}

function getCallCount(obj, methodName) {
  const counts = callCounts.get(obj);
  return counts ? counts[methodName] : 0;
}

// 使用示例
const calculator = {
  add(a, b) { return a + b; }
};

trackMethodCalls(calculator, 'add');

calculator.add(1, 2);
calculator.add(3, 4);
calculator.add(5, 6);

console.log(getCallCount(calculator, 'add')); // 3

五、底层实现原理

5.1 哈希表(Hash Table)原理

Set 和 Map 底层都基于哈希表实现:

原理流程:
1. 计算键的哈希值(hash code)
2. 将哈希值映射到数组索引(通常是 hash % array.length)
3. 在该索引位置存储值(处理哈希冲突)

// 简化的哈希表实现
class SimpleHashMap {
  constructor(size = 16) {
    this.buckets = new Array(size);
    this.size = 0;
  }
  
  // 简单的哈希函数
  hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash << 5) - hash + str.charCodeAt(i);
      hash = hash & hash; // 转为32位整数
    }
    return Math.abs(hash) % this.buckets.length;
  }
  
  set(key, value) {
    const index = this.hash(key);
    
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    
    // 检查键是否已存在
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    
    // 添加新键值对
    bucket.push([key, value]);
    this.size++;
  }
  
  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    if (!bucket) return undefined;
    
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    
    return undefined;
  }
}

5.2 哈希冲突处理

V8 引擎使用开放寻址法(Open Addressing)处理冲突:

// 开放寻址法示例
class OpenAddressingHashMap {
  constructor(size = 16) {
    this.keys = new Array(size);
    this.values = new Array(size);
    this.size = 0;
    this.capacity = size;
  }
  
  hash(key, attempt = 0) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash << 5) - hash + str.charCodeAt(i);
    }
    // 线性探测
    return (Math.abs(hash) + attempt) % this.capacity;
  }
  
  set(key, value) {
    let attempt = 0;
    
    while (attempt < this.capacity) {
      const index = this.hash(key, attempt);
      
      if (this.keys[index] === undefined || this.keys[index] === key) {
        this.keys[index] = key;
        this.values[index] = value;
        this.size++;
        return;
      }
      
      attempt++;
    }
    
    throw new Error('HashTable is full');
  }
  
  get(key) {
    let attempt = 0;
    
    while (attempt < this.capacity) {
      const index = this.hash(key, attempt);
      
      if (this.keys[index] === key) {
        return this.values[index];
      }
      
      if (this.keys[index] === undefined) {
        return undefined;
      }
      
      attempt++;
    }
    
    return undefined;
  }
}

5.3 动态扩容

当哈希表的负载因子(size / capacity)超过阈值时,会触发扩容:

class DynamicHashMap {
  constructor(initialCapacity = 16) {
    this.capacity = initialCapacity;
    this.size = 0;
    this.loadFactor = 0.75;
    this.buckets = new Array(this.capacity);
  }
  
  shouldResize() {
    return this.size / this.capacity >= this.loadFactor;
  }
  
  resize() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity);
    this.size = 0;
    
    // 重新哈希所有元素
    for (let bucket of oldBuckets) {
      if (bucket) {
        for (let [key, value] of bucket) {
          this.set(key, value);
        }
      }
    }
  }
  
  set(key, value) {
    if (this.shouldResize()) {
      this.resize();
    }
    
    // ... 正常的 set 逻辑
  }
}

V8 实现细节:

初始容量: 16
负载因子: 0.75
扩容策略: 容量翻倍
时间复杂度: 平均 O(1),最坏 O(n)(需要扩容时)

5.4 WeakMap/WeakSet 的实现

WeakMap 和 WeakSet 使用弱引用实现:

核心机制:
1. 键使用 ephemeron table(短暂表)存储
2. 如果键对象没有其他强引用,GC 可以回收
3. 键被回收后,对应的键值对自动从表中移除

// 概念示意(实际由 C++ 实现)
class WeakMapConcept {
  constructor() {
    // 内部使用 C++ 的 ephemeron table
    this._table = createEphemeronTable();
  }
  
  set(key, value) {
    if (typeof key !== 'object') {
      throw new TypeError('Invalid key type');
    }
    // 存储弱引用
    this._table.setWeak(key, value);
  }
  
  get(key) {
    // 如果键已被 GC,返回 undefined
    return this._table.getWeak(key);
  }
}

关键理解:

WeakMap/WeakSet 不会增加键对象的引用计数
垃圾回收器可以忽略这些弱引用
无法枚举,因为键的存在状态不确定

六、实战应用场景

6.1 Set 应用场景

场景1: 权限管理

class PermissionManager {
  constructor() {
    this.permissions = new Map();
  }
  
  addPermissions(userId, ...perms) {
    if (!this.permissions.has(userId)) {
      this.permissions.set(userId, new Set());
    }
    perms.forEach(perm => this.permissions.get(userId).add(perm));
  }
  
  hasPermission(userId, perm) {
    const userPerms = this.permissions.get(userId);
    return userPerms ? userPerms.has(perm) : false;
  }
  
  removePermission(userId, perm) {
    const userPerms = this.permissions.get(userId);
    if (userPerms) {
      userPerms.delete(perm);
    }
  }
}

// 使用示例
const pm = new PermissionManager();
pm.addPermissions('user1', 'read', 'write', 'delete');
console.log(pm.hasPermission('user1', 'write')); // true
pm.removePermission('user1', 'delete');
console.log(pm.hasPermission('user1', 'delete')); // false

场景2: 事件去重

class UniqueEventEmitter {
  constructor() {
    this.events = new Map();
  }
  
  on(event, callback) {
    if (!this.events.has(event)) {
      this.events.set(event, new Set());
    }
    this.events.get(event).add(callback);
  }
  
  off(event, callback) {
    const callbacks = this.events.get(event);
    if (callbacks) {
      callbacks.delete(callback);
    }
  }
  
  emit(event, ...args) {
    const callbacks = this.events.get(event);
    if (callbacks) {
      callbacks.forEach(callback => callback(...args));
    }
  }
}

// 使用示例
const emitter = new UniqueEventEmitter();
const handler = (data) => console.log(data);

emitter.on('message', handler);
emitter.on('message', handler); // 重复添加,但只会执行一次
emitter.emit('message', 'Hello'); // 只输出一次

6.2 Map 应用场景

场景1: 路由管理

class Router {
  constructor() {
    this.routes = new Map();
  }
  
  register(path, handler) {
    this.routes.set(path, handler);
  }
  
  navigate(path) {
    const handler = this.routes.get(path);
    if (handler) {
      handler();
    } else {
      console.log('404 Not Found');
    }
  }
}

// 使用示例
const router = new Router();
router.register('/home', () => console.log('Home Page'));
router.register('/about', () => console.log('About Page'));
router.navigate('/home'); // Home Page

场景2: 请求去重(防止重复提交)

class RequestDeduplicator {
  constructor() {
    this.pendingRequests = new Map();
  }
  
  async request(url, options = {}) {
    const key = this.generateKey(url, options);
    
    // 如果请求正在进行中,返回相同的 Promise
    if (this.pendingRequests.has(key)) {
      console.log('返回缓存的请求');
      return this.pendingRequests.get(key);
    }
    
    // 创建新请求
    const promise = fetch(url, options)
      .then(response => response.json())
      .finally(() => {
        // 请求完成后清除
        this.pendingRequests.delete(key);
      });
    
    this.pendingRequests.set(key, promise);
    return promise;
  }
  
  generateKey(url, options) {
    return `${options.method || 'GET'}-${url}-${JSON.stringify(options.body)}`;
  }
}

// 使用示例
const dedup = new RequestDeduplicator();

// 同时发起多个相同请求
Promise.all([
  dedup.request('/api/user/1'),
  dedup.request('/api/user/1'),
  dedup.request('/api/user/1')
]).then(results => {
  console.log('只发送了一次请求');
  console.log(results); // 三个结果相同
});

6.3 WeakMap 应用场景

场景1: Vue3 响应式系统(简化版)

const targetMap = new WeakMap();

function track(target, key) {
  let depsMap = targetMap.get(target);
  if (!depsMap) {
    targetMap.set(target, (depsMap = new Map()));
  }
  
  let dep = depsMap.get(key);
  if (!dep) {
    depsMap.set(key, (dep = new Set()));
  }
  
  // 收集依赖
  if (activeEffect) {
    dep.add(activeEffect);
  }
}

function trigger(target, key) {
  const depsMap = targetMap.get(target);
  if (!depsMap) return;
  
  const dep = depsMap.get(key);
  if (dep) {
    dep.forEach(effect => effect());
  }
}

function reactive(target) {
  return new Proxy(target, {
    get(target, key) {
      track(target, key);
      return target[key];
    },
    set(target, key, value) {
      target[key] = value;
      trigger(target, key);
      return true;
    }
  });
}

// 使用示例
let activeEffect = null;

function watchEffect(effect) {
  activeEffect = effect;
  effect();
  activeEffect = null;
}

const state = reactive({ count: 0 });

watchEffect(() => {
  console.log('Count:', state.count);
});

state.count++; // 自动触发: Count: 1

场景2: React Hooks 状态管理(简化版)

const componentStates = new WeakMap();

class Component {
  constructor() {
    componentStates.set(this, {
      hooks: [],
      currentHook: 0
    });
  }
  
  useState(initialValue) {
    const state = componentStates.get(this);
    const currentHook = state.currentHook;
    
    if (state.hooks[currentHook] === undefined) {
      state.hooks[currentHook] = initialValue;
    }
    
    const setValue = (newValue) => {
      state.hooks[currentHook] = newValue;
      this.render();
    };
    
    state.currentHook++;
    return [state.hooks[currentHook], setValue];
  }
  
  render() {
    const state = componentStates.get(this);
    state.currentHook = 0; // 重置 hook 索引
    // 触发重新渲染...
  }
}

6.4 WeakSet 应用场景

场景1: 防止 XSS 攻击(标记可信 HTML)

const trustedHTML = new WeakSet();

function createTrustedHTML(htmlString) {
  const div = document.createElement('div');
  div.innerHTML = htmlString;
  trustedHTML.add(div);
  return div;
}

function insertHTML(element, html) {
  if (trustedHTML.has(html)) {
    element.appendChild(html);
  } else {
    throw new Error('Untrusted HTML detected!');
  }
}

// 使用示例
const safe = createTrustedHTML('<p>Safe content</p>');
const unsafe = document.createElement('div');
unsafe.innerHTML = '<script>alert("XSS")</script>';

insertHTML(document.body, safe); // ✓ 允许
// insertHTML(document.body, unsafe); // ✗ 抛出错误

场景2: 标记已访问的对象(避免循环依赖)

function deepClone(obj, visited = new WeakSet()) {
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  if (visited.has(obj)) {
    throw new Error('Circular reference detected');
  }
  
  visited.add(obj);
  
  const clone = Array.isArray(obj) ? [] : {};
  
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key], visited);
    }
  }
  
  return clone;
}

// 测试循环引用
const a = { name: 'a' };
const b = { name: 'b' };
a.ref = b;
b.ref = a;

try {
  deepClone(a);
} catch (e) {
  console.log(e.message); // Circular reference detected
}

七、面试高频问题

7.1 基础问题

Q1: Set 和 Array 的区别?

答案要点:

唯一性: Set 成员唯一,Array 可重复
查找性能: Set 查找 O(1),Array 查找 O(n)
顺序: Set 保持插入顺序,Array 也保持顺序
方法: Set 有 add/delete/has,Array 有 push/pop/splice

// 性能对比
const arr = Array.from({ length: 10000 }, (_, i) => i);
const set = new Set(arr);

console.time('Array.includes');
arr.includes(9999);
console.timeEnd('Array.includes'); // ~0.1ms

console.time('Set.has');
set.has(9999);
console.timeEnd('Set.has'); // ~0.001ms

Q2: Map 和 Object 的区别?

答案要点:

特性	Map	Object
键类型	任意类型	String/Symbol
键顺序	插入顺序	部分有序
大小	`map.size`	需手动计算
迭代	原生可迭代	需 `Object.keys()`
性能	频繁增删更优	小数据量更优
继承	无原型链	有原型链
JSON	不支持	支持

// 键类型对比
const obj = {};
const key1 = { id: 1 };
const key2 = { id: 2 };

obj[key1] = 'value1';
obj[key2] = 'value2';
console.log(obj); // { '[object Object]': 'value2' }

const map = new Map();
map.set(key1, 'value1');
map.set(key2, 'value2');
console.log(map.size); // 2

Q3: WeakMap 和 Map 的区别?

答案要点:

特性	WeakMap	Map
键类型	只能是对象	任意类型
引用方式	弱引用	强引用
可迭代性	不可迭代	可迭代
size 属性	无	有
垃圾回收	自动清理	需手动清理
使用场景	私有数据、缓存	通用键值对

// 内存管理对比
let obj = { data: 'important' };

// Map - 强引用
const map = new Map();
map.set(obj, 'value');
obj = null; // 对象仍在 map 中,不会被回收

// WeakMap - 弱引用
const wm = new WeakMap();
let obj2 = { data: 'important' };
wm.set(obj2, 'value');
obj2 = null; // 对象可能被回收

7.2 进阶问题

Q4: 如何实现一个支持过期时间的 Map?

class ExpirableMap {
  constructor() {
    this.map = new Map();
  }
  
  set(key, value, ttl = null) {
    const entry = { value, expireAt: ttl ? Date.now() + ttl : null };
    this.map.set(key, entry);
  }
  
  get(key) {
    const entry = this.map.get(key);
    if (!entry) return undefined;
    
    if (entry.expireAt && Date.now() > entry.expireAt) {
      this.map.delete(key);
      return undefined;
    }
    
    return entry.value;
  }
  
  has(key) {
    return this.get(key) !== undefined;
  }
  
  // 清理过期项
  cleanup() {
    const now = Date.now();
    for (let [key, entry] of this.map) {
      if (entry.expireAt && now > entry.expireAt) {
        this.map.delete(key);
      }
    }
  }
}

// 使用示例
const cache = new ExpirableMap();
cache.set('token', 'abc123', 5000); // 5秒后过期

console.log(cache.get('token')); // 'abc123'
setTimeout(() => {
  console.log(cache.get('token')); // undefined
}, 6000);

Q5: 如何用 WeakMap 实现对象的私有属性?

// 方案1: 单个 WeakMap
const privateProps = new WeakMap();

class BankAccount {
  constructor(balance) {
    privateProps.set(this, { balance });
  }
  
  getBalance() {
    return privateProps.get(this).balance;
  }
  
  deposit(amount) {
    const props = privateProps.get(this);
    props.balance += amount;
  }
  
  withdraw(amount) {
    const props = privateProps.get(this);
    if (props.balance >= amount) {
      props.balance -= amount;
      return true;
    }
    return false;
  }
}

const account = new BankAccount(1000);
console.log(account.getBalance()); // 1000
console.log(account.balance); // undefined - 无法访问

// 方案2: 多个 WeakMap(更细粒度)
const _balance = new WeakMap();
const _owner = new WeakMap();

class SecureBankAccount {
  constructor(owner, balance) {
    _owner.set(this, owner);
    _balance.set(this, balance);
  }
  
  getOwner() {
    return _owner.get(this);
  }
  
  getBalance() {
    return _balance.get(this);
  }
}

Q6: Set 如何实现交集、并集、差集?

class SetOperations {
  // 并集
  static union(setA, setB) {
    return new Set([...setA, ...setB]);
  }
  
  // 交集
  static intersection(setA, setB) {
    return new Set([...setA].filter(x => setB.has(x)));
  }
  
  // 差集 A - B
  static difference(setA, setB) {
    return new Set([...setA].filter(x => !setB.has(x)));
  }
  
  // 对称差集
  static symmetricDifference(setA, setB) {
    const diff1 = this.difference(setA, setB);
    const diff2 = this.difference(setB, setA);
    return this.union(diff1, diff2);
  }
  
  // 判断子集
  static isSubset(subset, superset) {
    return [...subset].every(x => superset.has(x));
  }
  
  // 判断超集
  static isSuperset(superset, subset) {
    return this.isSubset(subset, superset);
  }
}

// 测试
const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

console.log([...SetOperations.union(setA, setB)]); // [1,2,3,4,5,6]
console.log([...SetOperations.intersection(setA, setB)]); // [3,4]
console.log([...SetOperations.difference(setA, setB)]); // [1,2]
console.log(SetOperations.isSubset(new Set([1, 2]), setA)); // true

7.3 场景问题

Q7: 如何实现一个 LRU 缓存?

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);
    }
  }
  
  // 辅助方法
  toString() {
    return JSON.stringify([...this.cache]);
  }
}

// 测试
const lru = new LRUCache(3);
lru.put(1, 'a'); // [(1,'a')]
lru.put(2, 'b'); // [(1,'a'), (2,'b')]
lru.put(3, 'c'); // [(1,'a'), (2,'b'), (3,'c')]
lru.get(1);      // [(2,'b'), (3,'c'), (1,'a')]
lru.put(4, 'd'); // [(3,'c'), (1,'a'), (4,'d')] - 移除 2
console.log(lru.get(2)); // -1

Q8: 如何防止循环引用导致的内存泄漏?

// 场景: 深度克隆时避免循环引用
function deepCloneWithWeakMap(obj, hash = new WeakMap()) {
  // 处理原始类型和 null
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  // 处理 Date
  if (obj instanceof Date) {
    return new Date(obj);
  }
  
  // 处理正则
  if (obj instanceof RegExp) {
    return new RegExp(obj);
  }
  
  // 检查是否已克隆过(防止循环引用)
  if (hash.has(obj)) {
    return hash.get(obj);
  }
  
  // 创建克隆对象
  const clone = Array.isArray(obj) ? [] : {};
  hash.set(obj, clone);
  
  // 递归克隆属性
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepCloneWithWeakMap(obj[key], hash);
    }
  }
  
  return clone;
}

// 测试循环引用
const obj1 = { name: 'obj1' };
const obj2 = { name: 'obj2' };
obj1.ref = obj2;
obj2.ref = obj1;

const cloned = deepCloneWithWeakMap(obj1);
console.log(cloned.name); // 'obj1'
console.log(cloned.ref.name); // 'obj2'
console.log(cloned.ref.ref === cloned); // true

Q9: WeakMap 在 DOM 事件监听中的应用?

// 场景: 避免 DOM 节点内存泄漏
class EventManager {
  constructor() {
    this.listeners = new WeakMap();
  }
  
  addEventListener(element, event, handler) {
    if (!this.listeners.has(element)) {
      this.listeners.set(element, new Map());
    }
    
    const elementListeners = this.listeners.get(element);
    if (!elementListeners.has(event)) {
      elementListeners.set(event, new Set());
    }
    
    elementListeners.get(event).add(handler);
    element.addEventListener(event, handler);
  }
  
  removeEventListener(element, event, handler) {
    const elementListeners = this.listeners.get(element);
    if (!elementListeners) return;
    
    const eventHandlers = elementListeners.get(event);
    if (!eventHandlers) return;
    
    eventHandlers.delete(handler);
    element.removeEventListener(event, handler);
  }
  
  removeAllListeners(element) {
    const elementListeners = this.listeners.get(element);
    if (!elementListeners) return;
    
    for (let [event, handlers] of elementListeners) {
      for (let handler of handlers) {
        element.removeEventListener(event, handler);
      }
    }
    
    this.listeners.delete(element);
  }
}

// 使用示例
const eventManager = new EventManager();
const button = document.createElement('button');

const clickHandler = () => console.log('Clicked!');
eventManager.addEventListener(button, 'click', clickHandler);

// 当 button 从 DOM 移除后,WeakMap 会自动清理
button.remove(); // 不会造成内存泄漏

八、性能对比与优化

8.1 时间复杂度对比

操作	Array	Set	Map	Object
查找	O(n)	O(1)	O(1)	O(1)
插入	O(1)*	O(1)	O(1)	O(1)
删除	O(n)	O(1)	O(1)	O(1)
遍历	O(n)	O(n)	O(n)	O(n)

*数组末尾插入为 O(1),其他位置为 O(n)

8.2 性能测试

// 性能对比测试
function benchmark(name, fn, iterations = 1000000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    fn(i);
  }
  const end = performance.now();
  console.log(`${name}: ${(end - start).toFixed(2)}ms`);
}

// 查找性能
const arr = Array.from({ length: 10000 }, (_, i) => i);
const set = new Set(arr);
const map = new Map(arr.map(v => [v, v]));
const obj = Object.fromEntries(arr.map(v => [v, v]));

console.log('=== 查找性能 ===');
benchmark('Array.includes', i => arr.includes(5000));
benchmark('Set.has', i => set.has(5000));
benchmark('Map.has', i => map.has(5000));
benchmark('Object.hasOwnProperty', i => obj.hasOwnProperty(5000));

// 插入性能
console.log('\n=== 插入性能 ===');
benchmark('Array.push', i => {
  const a = [];
  a.push(i);
});
benchmark('Set.add', i => {
  const s = new Set();
  s.add(i);
});
benchmark('Map.set', i => {
  const m = new Map();
  m.set(i, i);
});
benchmark('Object assign', i => {
  const o = {};
  o[i] = i;
});

// 删除性能
console.log('\n=== 删除性能 ===');
benchmark('Array.splice', i => {
  const a = [1, 2, 3, 4, 5];
  a.splice(2, 1);
});
benchmark('Set.delete', i => {
  const s = new Set([1, 2, 3, 4, 5]);
  s.delete(3);
});
benchmark('Map.delete', i => {
  const m = new Map([[1, 1], [2, 2], [3, 3]]);
  m.delete(2);
});
benchmark('delete operator', i => {
  const o = { a: 1, b: 2, c: 3 };
  delete o.b;
});

8.3 内存使用对比

// 内存占用测试(需要 Node.js 环境)
function measureMemory(name, fn) {
  if (global.gc) global.gc(); // 手动触发 GC
  const before = process.memoryUsage().heapUsed;
  
  fn();
  
  if (global.gc) global.gc();
  const after = process.memoryUsage().heapUsed;
  
  const used = ((after - before) / 1024 / 1024).toFixed(2);
  console.log(`${name}: ${used} MB`);
}

// 测试
const size = 100000;

measureMemory('Array', () => {
  const arr = Array.from({ length: size }, (_, i) => i);
});

measureMemory('Set', () => {
  const set = new Set(Array.from({ length: size }, (_, i) => i));
});

measureMemory('Map', () => {
  const map = new Map(Array.from({ length: size }, (_, i) => [i, i]));
});

measureMemory('Object', () => {
  const obj = {};
  for (let i = 0; i < size; i++) {
    obj[i] = i;
  }
});

8.4 最佳实践

1. 选择合适的数据结构

// ❌ 错误: 使用数组做查找
const userIds = [1, 2, 3, 4, 5, /*...1000 items*/];
if (userIds.includes(targetId)) { // O(n)
  // ...
}

// ✅ 正确: 使用 Set
const userIds = new Set([1, 2, 3, 4, 5, /*...1000 items*/]);
if (userIds.has(targetId)) { // O(1)
  // ...
}

2. 避免过度使用 WeakMap/WeakSet

// ❌ 错误: 需要遍历时使用 WeakMap
const userPreferences = new WeakMap();
// 无法遍历所有用户偏好!

// ✅ 正确: 使用 Map
const userPreferences = new Map();
for (let [user, prefs] of userPreferences) {
  console.log(user, prefs);
}

3. 合理使用键类型

// ❌ 错误: 使用对象字面量作为 Map 的键
const cache = new Map();
cache.set({ id: 1 }, 'value'); // 每次都是新对象!
console.log(cache.get({ id: 1 })); // undefined

// ✅ 正确: 复用键对象
const cache = new Map();
const key = { id: 1 };
cache.set(key, 'value');
console.log(cache.get(key)); // 'value'

4. 大数据集去重优化

// ❌ 慢: 使用 filter
function removeDuplicates(arr) {
  return arr.filter((item, index) => arr.indexOf(item) === index);
  // O(n²)
}

// ✅ 快: 使用 Set
function removeDuplicates(arr) {
  return [...new Set(arr)]; // O(n)
}

// 🚀 更快: 对于大型数组,直接返回 Set
function removeDuplicates(arr) {
  return new Set(arr); // 不转为数组,保持 Set
}

5. WeakMap 用于缓存时的注意事项

// ✅ 正确: 对象不再使用时自动清理
const cache = new WeakMap();

function processData(obj) {
  if (cache.has(obj)) {
    return cache.get(obj);
  }
  
  const result = expensiveOperation(obj);
  cache.set(obj, result);
  return result;
}

// ⚠️ 注意: 基本类型不能作为键
// cache.set('key', 'value'); // TypeError

总结

核心要点回顾

Set: 唯一值集合,适合去重、集合运算
Map: 任意类型键值对,适合键不是字符串的场景
WeakSet: 弱引用对象集合,适合对象标记
WeakMap: 弱引用键值对,适合私有数据、DOM 元数据

选择指南

场景	推荐
数组去重	Set
键不是字符串	Map
频繁增删查	Set/Map
需要遍历	Set/Map
对象私有数据	WeakMap
DOM 元数据	WeakMap
对象标记	WeakSet
防止内存泄漏	WeakMap/WeakSet

面试准备清单

理解四种数据结构的核心差异
掌握哈希表的基本原理
能实现常见算法(去重、LRU、深克隆)
了解弱引用和垃圾回收机制
熟悉实际应用场景
能比较时间/空间复杂度

进阶学习方向

V8 引擎实现细节: 研究 V8 源码中的哈希表实现
其他语言对比: Java HashSet/HashMap, Python set/dict
数据结构设计: 实现更复杂的数据结构(跳表、布隆过滤器)
性能优化: 学习更多性能测试和优化技巧

参考资料:

JavaScript 集合数据结构深度解析

目录

一、Set 深度解析

1.1 Set 的本质

1.2 Set 的核心特性

1.2.1 值的唯一性

1.2.2 有序性

1.3 Set 的 API

1.4 Set 的实际应用

1.4.1 数组去重

1.4.2 集合运算

1.4.3 判断超集和子集

二、Map 深度解析

2.1 Map 的本质

2.2 Map vs Object

2.3 Map 的 API

2.4 Map 的实际应用

2.4.1 缓存/记忆化

2.4.2 对象属性统计

2.4.3 DOM 节点元数据存储

2.4.4 LRU 缓存实现

三、WeakSet 深度解析

3.1 WeakSet 的本质

3.2 弱引用的原理

3.3 WeakSet 的 API

3.4 WeakSet 的实际应用

3.4.1 标记对象(不影响生命周期)

3.4.2 防止对象被多次处理

3.4.3 私有数据存储

四、WeakMap 深度解析

4.1 WeakMap 的本质

4.2 WeakMap 的 API

4.3 WeakMap 的实际应用

4.3.1 DOM 节点元数据存储(防止内存泄漏)

4.3.2 对象私有数据实现

4.3.3 缓存计算结果

4.3.4 实现观察者模式

4.3.5 记录对象方法调用次数

五、底层实现原理

5.1 哈希表(Hash Table)原理

5.2 哈希冲突处理

5.3 动态扩容

5.4 WeakMap/WeakSet 的实现

六、实战应用场景

6.1 Set 应用场景

场景1: 权限管理

场景2: 事件去重

6.2 Map 应用场景

场景1: 路由管理

场景2: 请求去重(防止重复提交)

6.3 WeakMap 应用场景

场景1: Vue3 响应式系统(简化版)

场景2: React Hooks 状态管理(简化版)

6.4 WeakSet 应用场景

场景1: 防止 XSS 攻击(标记可信 HTML)

场景2: 标记已访问的对象(避免循环依赖)

七、面试高频问题

7.1 基础问题

Q1: Set 和 Array 的区别?

Q2: Map 和 Object 的区别?

Q3: WeakMap 和 Map 的区别?

7.2 进阶问题

Q4: 如何实现一个支持过期时间的 Map?

Q5: 如何用 WeakMap 实现对象的私有属性?

Q6: Set 如何实现交集、并集、差集?

7.3 场景问题

Q7: 如何实现一个 LRU 缓存?

Q8: 如何防止循环引用导致的内存泄漏?

Q9: WeakMap 在 DOM 事件监听中的应用?

八、性能对比与优化

8.1 时间复杂度对比

8.2 性能测试

8.3 内存使用对比

8.4 最佳实践

1. 选择合适的数据结构

2. 避免过度使用 WeakMap/WeakSet

3. 合理使用键类型

4. 大数据集去重优化

5. WeakMap 用于缓存时的注意事项

总结