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

Question

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

这些数据结构并不重要。现在他们住在这样的数组中:

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

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

我需要检查对象是否存在。目前我在做:

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

不过，我可以通过多种方式进行此存在性检查。我需要它尽可能高效。

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

1. 创建 Map值未定义
2. 创建一个对象 ( {} ) 并创建对象的键作为 list 中的条目, 然后使用 hasOwnProperty .
3. 使用 Set()
4. 使用其他类型的数据结构(一棵树？)，因为这些都是数字。但是，由于这些都是 18 位数字，因此性能可能会降低。

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

Answer 1

Array.prototype.includes 是一个 O(n) 操作，这是不可取的 - 每次你想检查一个值是否存在时，你都会有迭代大部分集合(可能是整个集合)。

Map、Set 或对象更好，因为检查它们是否具有值是 O(1) 操作。

树也是不可取的，因为查找必然会在树下进行许多操作，如果树很大并且您想经常查找，这可能是个问题 - 所以 O(1) 解决方案更好。

map 虽然有效，但可能并不合适，因为您只想查看是否存在值 - 您不需要键值对，只是值(value)观。 Set 仅由值组成(Set.has 确实是 O(1))，因此这是这种情况的最佳选择。带键的对象虽然也可以工作，但可能不是一个好主意，因为它可能会创建许多不必要的 hidden classes - Set 更倾向于运行时的动态值。

因此，Set 方法看起来是性能最高且最合适的选择。

您还可以考虑将计算移至服务器的可能性。 100,000 个项目不一定太多，但对于客户端来说仍然是一个大得惊人的数量。