JS中实现按值O(1)查找的缓存可用什么数据结构？

JS 没有内置原生支持按值匹配的 O(1) 查找缓存数据结构，但可以通过稳定深哈希 + 普通 Map的方案实现符合你要求的效果。

核心思路 #

要实现按值匹配的O(1)查询，本质是把任意类型的键（原始类型、对象、数组等）转换为一个和值强绑定的唯一字符串（稳定哈希）：两个值深相等时输出的哈希完全相同，深不等时哈希碰撞概率极低。之后直接用这个哈希字符串作为普通 Map 的键存储缓存结果，查询时直接计算哈希后查Map即可得到O(1)的查询效率。

实现方案 #

1. 稳定深哈希函数 #

需要实现一个能处理所有JS合法变量类型、支持循环引用、输出结果稳定的深哈希函数，示例实现如下：

// 简易稳定深哈希实现，生产环境可优化哈希逻辑降低碰撞概率
function getStableHash(value, seen = new WeakMap()) {
  // 处理非对象原始类型
  if (typeof value !== 'object' || value === null) {
    return `${typeof value}:${String(value)}`
  }
  // 处理循环引用避免爆栈
  if (seen.has(value)) {
    return `ref:${seen.get(value)}`
  }
  const refId = seen.size
  seen.set(value, refId)
  // 处理数组
  if (Array.isArray(value)) {
    const itemHash = value.map(i => getStableHash(i, new WeakMap(seen))).join(',')
    return `arr:[${itemHash}]`
  }
  // 处理普通对象，先排序键避免键顺序不同导致哈希不同
  const sortedKeys = Object.keys(value).sort()
  const objHash = sortedKeys.map(k => `${k}:${getStableHash(value[k], new WeakMap(seen))}`).join(',')
  return `obj:{${objHash}}`
}

2. 缓存封装 #

直接用普通Map作为缓存容器，键为深哈希计算结果，值为缓存内容：

const cache = new Map()

function cachedFunc(...keys) {
  // 把传入的键数组整体计算哈希
  const keyHash = getStableHash(keys)
  // 命中缓存直接返回，O(1)查询
  if (cache.has(keyHash)) {
    return cache.get(keyHash)
  }
  // 未命中则执行业务逻辑计算结果
  const result = 1234 // 此处替换为实际业务计算逻辑
  cache.set(keyHash, result)
  return result
}

注意事项 #

• 哈希计算的开销和键的复杂度正相关，如果键的大小是固定的，计算开销为常数级，实际使用中可认为是O(1)效率，相比遍历所有缓存条目做深相等对比的方案，缓存条目越多性能优势越明显。
• 简易哈希实现存在碰撞概率，生产环境可对输出的哈希字符串再做消息摘要处理，或使用成熟的深哈希实现，碰撞概率可低到可忽略不计。
• 你之前尝试的嵌套Map方案仅适合按引用匹配的场景，要支持按值匹配还是需要先把每一层的键转换为可按值对比的标识，和统一哈希的方案本质逻辑一致，后者实现更简洁。

内容的提问来源于stack exchange，提问作者Don P