如何高效实现支持无序复合键的CompoundMap？

一、更高效的CompoundMap实现思路 #

你当前用嵌套Map树的方案时间复杂度O(2^n)确实低效，核心问题是无序复合键的处理导致需要遍历所有排列组合。这里有两种更高效的实现方式：

1. 排序复合键后用单层Map #

因为复合键是无序的，先对键数组按稳定规则排序（比如先将每个元素转为可比较的字符串/唯一标识，再排序），然后把排序后的数组转为一个可作为Map键的结构（比如JSON.stringify，或自定义哈希串），直接用普通Map存储。

• 时间复杂度：排序的O(n log n) + Map操作的O(1)，远优于O(2^n)
• 优势：实现简单，无需复杂嵌套，依赖JS原生Map的高效性能

2. 基于哈希合并的方案 #

给每个键元素生成唯一哈希值，先排序这些哈希值（保证无序键生成相同的合并结果），再通过拼接或数学运算生成一个整体哈希作为Map键。这种方式避免了JSON.stringify对复杂对象的局限性，性能更稳定。

二、通过唯一BigInt映射实现CompoundMap的可行性 #

这个思路完全可行，但要注意两个核心点：

1. 必须保证无序复合键生成唯一且相同的标识：即使每个元素有唯一BigInt，也要先对这些BigInt排序，再合并成一个键（比如拼接成字符串，或用位运算合并），否则不同顺序的同一组元素会被识别为不同键。
2. 任意值到唯一BigInt的映射必须无冲突：这需要覆盖所有JS类型（原始类型+引用类型），且同一值的不同类型（比如0和0n）不能生成相同的BigInt。

三、getUniqueIntFor函数的实现 #

要实现一个能给任意JS值生成唯一BigInt的函数，需要针对不同类型做差异化处理，同时避免冲突和内存泄漏：

// 全局映射：存储引用类型和Symbol的唯一ID，WeakMap避免内存泄漏
const refMap = new WeakMap();
const symbolMap = new Map();
let nextRefId = BigInt(0);
let nextSymbolId = BigInt(0);

function getUniqueIntFor(value) {
  // 处理null
  if (value === null) return BigInt(0);
  // 处理undefined
  if (value === undefined) return BigInt(1);

  const type = typeof value;

  // 处理布尔值
  if (type === 'boolean') return value ? BigInt(2) : BigInt(3);

  // 处理数字：区分整数和浮点数，避免冲突
  if (type === 'number') {
    if (Number.isInteger(value)) {
      // 用前缀10左移64位，避免和其他类型重叠
      return (BigInt(10) << BigInt(64)) | BigInt(value);
    } else {
      // 浮点数转字节数组再转BigInt，前缀11
      const buffer = new ArrayBuffer(8);
      new Float64Array(buffer)[0] = value;
      const bytes = new Uint8Array(buffer);
      let bigInt = BigInt(0);
      for (const byte of bytes) bigInt = (bigInt << BigInt(8)) | BigInt(byte);
      return (BigInt(11) << BigInt(64)) | bigInt;
    }
  }

  // 处理字符串：转UTF-8字节数组后生成BigInt，前缀20
  if (type === 'string') {
    const encoder = new TextEncoder();
    const bytes = encoder.encode(value);
    let bigInt = BigInt(0);
    for (const byte of bytes) bigInt = (bigInt << BigInt(8)) | BigInt(byte);
    // 左移足够位数避免前缀和内容重叠
    const shiftBits = BigInt(64 * Math.ceil(bytes.length / 8));
    return (BigInt(20) << shiftBits) | bigInt;
  }

  // 处理Symbol：用全局Map存储唯一ID，前缀30
  if (type === 'symbol') {
    if (!symbolMap.has(value)) {
      symbolMap.set(value, (BigInt(30) << BigInt(64)) | nextSymbolId);
      nextSymbolId += BigInt(1);
    }
    return symbolMap.get(value);
  }

  // 处理BigInt：前缀40，避免和其他数字类型冲突
  if (type === 'bigint') return (BigInt(40) << BigInt(64)) | value;

  // 处理引用类型（对象、函数等）：用WeakMap存储，前缀50
  if (!refMap.has(value)) {
    refMap.set(value, (BigInt(50) << BigInt(64)) | nextRefId);
    nextRefId += BigInt(1);
  }
  return refMap.get(value);
}

实现说明： #

• 类型前缀：给不同类型分配唯一前缀并左移足够位数，避免不同类型的值产生冲突（比如null的0和number的0）。
• 引用类型处理：用WeakMap存储对象到BigInt的映射，当对象被垃圾回收时，对应的条目会自动移除，不会造成内存泄漏。
• 浮点数处理：通过Float64Array将浮点数转成字节数组，再转成BigInt，保证每个浮点数对应唯一的BigInt。

基于getUniqueIntFor的CompoundMap实现 #

class CompoundMap {
  constructor() {
    this.innerMap = new Map();
  }

  // 生成无序复合键的唯一标识
  #generateKey(compoundKey) {
    // 先排序每个元素的唯一BigInt，保证无序键生成相同标识
    const sortedIds = compoundKey
      .map(getUniqueIntFor)
      .sort((a, b) => a > b ? 1 : a < b ? -1 : 0);
    // 拼接成字符串作为Map键（BigInt直接作为键也可以，但字符串更直观）
    return sortedIds.join(',');
  }

  set(compoundKey, value) {
    const key = this.#generateKey(compoundKey);
    this.innerMap.set(key, value);
  }

  get(compoundKey) {
    const key = this.#generateKey(compoundKey);
    return this.innerMap.get(key);
  }

  delete(compoundKey) {
    const key = this.#generateKey(compoundKey);
    return this.innerMap.delete(key);
  }

  has(compoundKey) {
    const key = this.#generateKey(compoundKey);
    return this.innerMap.has(key);
  }
}

内容的提问来源于stack exchange，提问作者Gershom Maes