在 JavaScript 的列表中检查对象是否存在的最快方法

Question

我有一个包含在内存中的 100,000 个项目的列表（所有这些大整数都存储为字符串）。

这些进来的数据结构并不重要。现在他们生活在这样的数组中：

const list = ['1','2','3'...'100000'];

注意：以上只是一个例子 - 实际上，每个条目都是一个 18 位的字符串。

我需要检查一个对象的存在。目前我正在做：

const needToCheck = '3';
const doesInclude = list.includes(needToCheck);

但是，有很多方法可以进行这种存在性检查。我需要它尽可能提高性能。

我可以遵循的其他一些途径是：

1. 创建一个Map值为 undefined

2. 创建一个对象 ( {}) 并创建对象的键作为 中的条目list，然后使用hasOwnProperty.

3. 用一个 Set()

4. 由于这些都是数字，因此请使用其他类型的数据结构（树？）。但是，由于这些长度都是 18 位数字，因此性能可能会降低。

我可以接受更高的前期成本来构建数据结构以在以后获得更大的速度提升，因为这是针对每天将被点击 > 1MM 次的 URL 路由。

Answer 1

Array.prototype.includes是一个O(n)操作，这是不可取的 - 每次您想要检查一个值是否存在时，您都必须迭代大部分集合（可能是整个集合）。Map、Set 或 object 更好，因为检查它们是否具有值是一种O(1)操作。树也是不可取的，因为查找必然会在树下进行许多操作，如果树很大并且您想要频繁查找，这可能是一个问题 - 所以O(1)解决方案更好。地图虽然有效，但可能不合适，因为您只想查看值是否存在 - 您不需要键值对，只需要值。Set 仅由值组成（并且Set.has确实是O(1)），因此这是这种情况的最佳选择。带有键的对象虽然也可以工作，但可能不是一个好主意，因为它可能会创建许多不必要的隐藏类- Set 更适合在运行时针对动态值。因此，Set 方法看起来是最高效和最合适的选择。您还可以考虑将计算移至服务器的可能性。100,000 个项目不一定太多，但在客户端看到的数量仍然惊人。

Answer 2

非常规地，您还可以使用一个对象并将 100,000 个项目中的每一个设置为一个属性，因为在幕后，JavaScript Object 是使用哈希表实现的。例如，var numbers = {"1": 1243213,"2": 4314121,"3": 3142123...}然后，您可以通过检查 if 来非常快速地检查项目是否存在numbers["1"] === undefined。不仅如此，您还可以同时获得房产的价值。然而，这种方法确实有一些缺点，比如遍历列表变得更加复杂（尽管仍然可能）。