JavaScript如何优化查找键名含指定子串的字典项

按实际业务场景选方案即可，不要过度设计，匹配场景和数据量级的方案性能最高。

场景1：字典仅做1-2次低频查询 #

这种情况完全不需要提前构建复杂索引，直接用原生遍历即可，注意规避多余性能损耗：

const searchString = 'Gen';
const myDict = {
  'Genesis': 'You are the beginning',
  'Joel': 'Joe is cool'
}

function matchValue(dict, searchStr) {
  // 用for...in直接遍历，比Object.keys().find()少了一层创建全量key数组的额外开销
  for (const key in dict) {
    if (Object.hasOwn(dict, key) && key.includes(searchStr)) {
      // 若需要返回所有匹配结果，把值push到结果数组即可，不要直接return
      return dict[key]
    }
  }
  return undefined
}

// 调用直接拿结果
console.log(matchValue(myDict, searchString)) // 输出You are the beginning

这种写法遍历开销是O(n)，n为字典键的总数量，仅做一两次查询的话，哪怕字典有几万条数据，JS引擎执行耗时也在几毫秒级别，完全够用。

场景2：同一个字典需要多次高频查询 #

如果字典是静态的（不会频繁增删键值对），每次搜索都走全量遍历的*O(n)*逻辑，键量级到十万级以上就会出现明显卡顿，这时候一定要提前构建索引，把时间成本摊到初始化阶段。

子情况2.1 业务为前缀匹配（绝大多数搜索场景都是这类，比如输入联想） #

也就是要找的子串基本出现在key的开头，和示例里Gen匹配Genesis的逻辑一致，直接构建前缀树（Trie）是最优解。构建完成后每次搜索的时间复杂度仅和输入的搜索串长度有关，为O(m)，和字典总键数完全无关，百万级键量也能做到毫秒级返回。
简单实现参考：

class PrefixSearch {
  constructor(dict) {
    this.root = new Map()
    // 初始化构建前缀树
    for (const key in dict) {
      if (!Object.hasOwn(dict, key)) continue
      let node = this.root
      for (const c of key) {
        if (!node.has(c)) node.set(c, new Map())
        node = node.get(c)
      }
      // 节点挂载对应的值
      node.set('__val', dict[key])
    }
  }
  find(prefix) {
    let node = this.root
    for (const c of prefix) {
      if (!node.has(c)) return undefined
      node = node.get(c)
    }
    // 如果需要返回所有前缀匹配的结果，在这里做深度遍历收集所有子节点的__val即可
    return node.get('__val')
  }
}

// 索引初始化仅需执行一次
const searcher = new PrefixSearch(myDict)
// 后续多次搜索直接调用即可
console.log(searcher.find('Gen'))

子情况2.2 需要匹配key任意位置的子串（子串可能出现在key的中间、末尾） #

不用硬啃实现复杂的后缀树，落地成本太高，性价比最高的方案是构建N-Gram倒排索引：根据业务里最短的搜索串长度（比如最短支持搜3个字符），把每个key拆成所有对应长度的连续片段，将片段映射到对应的原key列表。搜索时先拿搜索串去索引里拿到小范围的候选key集合，再在候选集里做精确includes校验即可，能把每次遍历的范围从几万、几十万压缩到几个、几十个，性能提升非常明显，内存占用也完全可控。

避坑提醒 #

• 不要每次搜索都调用Object.keys()转数组再遍历，额外的数组创建和遍历开销在大数据量下会拖慢速度
• 如果字典有动态增删需求，增删键的时候同步更新构建好的索引即可，维护开销远小于每次全量遍历
• 提前明确业务规则：如果多个key都包含搜索子串，要提前定好是返回第一个匹配项，还是返回所有匹配结果的数组，对应调整逻辑即可

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