Map 与 Set：哈希表的底层实现 ​

const dict = {};
dict['key1'] = 'value1';
dict['key2'] = 'value2';

console.log(dict['key1']);  // 'value1'

const obj = {};
const keyObj = { id: 1 };
const keyFunc = function() {};

obj[keyObj] = 'value1';      // 键变成 "[object Object]"
obj[keyFunc] = 'value2';     // 键变成 "function() {}"

console.log(Object.keys(obj));  // ["[object Object]", "function() {}"]

const dict = {};
dict['toString'] = 'my value';

console.log(dict.toString);         // [Function: toString] (不是我们设置的值！)
console.log(dict['toString']);      // 'my value'

const map = new Map();
const keyObj = { id: 1 };
const keyFunc = function() {};

map.set(keyObj, 'value1');
map.set(keyFunc, 'value2');

console.log(map.get(keyObj));    // 'value1'
console.log(map.get(keyFunc));   // 'value2'

// 伪代码展示 V8 内部逻辑
function mapSet(map, key, value) {
  const hash = getHash(key);              // 计算键的哈希值
  const bucketIndex = hash % map.numberOfBuckets;
  
  let entry = map.hashTable[bucketIndex]; // 获取桶中第一个元素
  
  // 检查键是否已存在
  while (entry !== kNotFound) {
    if (sameValueZero(map.dataTable[entry].key, key)) {
      // 键已存在，更新值
      map.dataTable[entry].value = value;
      return map;
    }
    entry = map.nextTable[entry];         // 检查冲突链中的下一个
  }
  
  // 键不存在，插入新元素
  const newIndex = map.numberOfElements;
  map.dataTable[newIndex] = { key, value, hash };
  map.nextTable[newIndex] = map.hashTable[bucketIndex]; // 新元素链到桶头
  map.hashTable[bucketIndex] = newIndex;                // 更新桶指向新元素
  map.numberOfElements++;
  
  // 检查是否需要扩容
  if (map.numberOfElements > map.numberOfBuckets * 0.75) {
    rehash(map, map.numberOfBuckets * 2);
  }
  
  return map;
}

function mapGet(map, key) {
  const hash = getHash(key);
  const bucketIndex = hash % map.numberOfBuckets;
  
  let entry = map.hashTable[bucketIndex];
  
  while (entry !== kNotFound) {
    if (sameValueZero(map.dataTable[entry].key, key)) {
      return map.dataTable[entry].value;  // 找到匹配键，返回值
    }
    entry = map.nextTable[entry];
  }
  
  return undefined;  // 未找到键，返回 undefined
}

function mapDelete(map, key) {
  const hash = getHash(key);
  const bucketIndex = hash % map.numberOfBuckets;
  
  let entry = map.hashTable[bucketIndex];
  let prev = kNotFound;
  
  while (entry !== kNotFound) {
    if (sameValueZero(map.dataTable[entry].key, key)) {
      // 找到匹配键，从冲突链中移除
      if (prev === kNotFound) {
        map.hashTable[bucketIndex] = map.nextTable[entry]; // 移除头节点
      } else {
        map.nextTable[prev] = map.nextTable[entry];        // 移除中间节点
      }
      
      // 标记为已删除（不立即回收）
      map.dataTable[entry].key = kTheHole;
      map.dataTable[entry].value = kTheHole;
      map.numberOfElements--;
      map.numberOfDeletedElements++;
      
      // 检查是否需要收缩哈希表
      if (map.numberOfDeletedElements > map.numberOfBuckets / 2) {
        rehash(map, map.numberOfBuckets);  // 重建哈希表清理已删除元素
      }
      
      return true;
    }
    prev = entry;
    entry = map.nextTable[entry];
  }
  
  return false;  // 键不存在
}

// V8 内部简化逻辑
Set.prototype.add = function(value) {
  // Set 内部使用 OrderedHashSet，结构与 OrderedHashMap 类似
  // 存储时键和值都是 value
  return this.table.set(value, value);
};

Set.prototype.has = function(value) {
  return this.table.has(value);
};

Set.prototype.delete = function(value) {
  return this.table.delete(value);
};

const map = new Map();
map.set('c', 3);
map.set('a', 1);
map.set('b', 2);

for (const [key, value] of map) {
  console.log(key, value);
}
// 输出顺序：c 3, a 1, b 2（插入顺序）

// 测试：频繁插入删除
function testInsertDelete(iterations) {
  // 使用 Map
  console.time('Map insert/delete');
  const map = new Map();
  for (let i = 0; i < iterations; i++) {
    map.set(i, i);
  }
  for (let i = 0; i < iterations; i++) {
    map.delete(i);
  }
  console.timeEnd('Map insert/delete');
  
  // 使用对象
  console.time('Object insert/delete');
  const obj = {};
  for (let i = 0; i < iterations; i++) {
    obj[i] = i;
  }
  for (let i = 0; i < iterations; i++) {
    delete obj[i];
  }
  console.timeEnd('Object insert/delete');
}

testInsertDelete(100000);
// Map insert/delete: 8ms
// Object insert/delete: 25ms

// 测试：查找性能
function testLookup(iterations) {
  const map = new Map();
  const obj = {};
  
  // 预填充数据
  for (let i = 0; i < 10000; i++) {
    map.set(i, i);
    obj[i] = i;
  }
  
  // Map 查找
  console.time('Map lookup');
  for (let i = 0; i < iterations; i++) {
    map.get(i % 10000);
  }
  console.timeEnd('Map lookup');
  
  // 对象查找
  console.time('Object lookup');
  for (let i = 0; i < iterations; i++) {
    obj[i % 10000];
  }
  console.timeEnd('Object lookup');
}

testLookup(1000000);
// Map lookup: 10ms
// Object lookup: 5ms

// 不好：大量相似对象
const map = new Map();
for (let i = 0; i < 1000; i++) {
  map.set({ id: i }, i);  // 每个对象哈希值随机，但结构相同
}

// 更好：使用基本类型或唯一标识
const map = new Map();
for (let i = 0; i < 1000; i++) {
  map.set(i, { id: i });  // 数字键哈希分布更均匀
}

// 预分配空间（非标准，仅示意）
function createPreallocatedMap(expectedSize) {
  const map = new Map();
  // 插入占位元素触发扩容
  for (let i = 0; i < expectedSize; i++) {
    map.set(i, null);
  }
  // 清空占位元素
  map.clear();
  return map;  // 此时内部桶数量已扩容
}

// 数组去重
const arr = [1, 2, 2, 3, 3, 3, 4];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr);  // [1, 2, 3, 4]

// 方法1：使用 indexOf（O(n²)）
function uniqueWithIndexOf(arr) {
  const result = [];
  for (const item of arr) {
    if (result.indexOf(item) === -1) {
      result.push(item);
    }
  }
  return result;
}

// 方法2：使用 Set（O(n)）
function uniqueWithSet(arr) {
  return [...new Set(arr)];
}

// 性能测试
const largeArr = Array.from({ length: 10000 }, (_, i) => i % 100);

console.time('indexOf');
uniqueWithIndexOf(largeArr);
console.timeEnd('indexOf');  // ~150ms

console.time('Set');
uniqueWithSet(largeArr);
console.timeEnd('Set');      // ~2ms

// 集合运算
const setA = new Set([1, 2, 3, 4]);
const setB = new Set([3, 4, 5, 6]);

// 并集
const union = new Set([...setA, ...setB]);
console.log([...union]);  // [1, 2, 3, 4, 5, 6]

// 交集
const intersection = new Set([...setA].filter(x => setB.has(x)));
console.log([...intersection]);  // [3, 4]

// 差集
const difference = new Set([...setA].filter(x => !setB.has(x)));
console.log([...difference]);  // [1, 2]

const privateData = new WeakMap();

class Person {
  constructor(name, age) {
    this.name = name;
    privateData.set(this, { age });  // age 作为私有数据
  }
  
  getAge() {
    return privateData.get(this).age;
  }
}

let p = new Person('Alice', 30);
console.log(p.getAge());  // 30
p = null;  // Person 对象可被垃圾回收，WeakMap 中的记录自动清除

const cache = new WeakMap();

function expensiveComputation(obj) {
  if (cache.has(obj)) {
    return cache.get(obj);  // 命中缓存
  }
  
  const result = /* 复杂计算 */ obj.data * 2;
  cache.set(obj, result);
  return result;
}