performance - 一个高效的 Javascript 集合结构

Question

看了很多类似的问题后:

• JavaScript implementation of a set data structure
• Mimicking sets in JavaScript?
• Node JS, traditional data structures? (such as Set, etc), anything like Java.util for node?
• Efficient Javascript Array Lookup
• Best way to find if an item is in a JavaScript array?
• How do I check if an array includes an object in JavaScript?

我还有一个问题:假设我有一个很大的字符串数组(数千个)，我必须进行多次查找(即多次检查给定的字符串是否包含在该数组中)。在 Node.js 中执行此操作的最有效方法是什么？

一个。对字符串数组进行排序，然后使用二进制搜索？或者:

B.将字符串转换为对象的键，然后使用“in”运算符

?

我知道 A 的复杂度是 O(log N)，其中 N 是字符串的数量。

但是我不知道B的复杂度。

如果一个Javascript对象实现为哈希表，那么B的复杂度平均为O(1)，比A好。但是，我不知道一个Javascript对象是否真的实现为哈希表!

Answer 1

2016 年更新

由于您询问的是 node.js，现在是 2016 年，您现在可以使用 ES6 中的 Set 或 Map 对象，因为它们内置于 ES6 中。两者都允许您使用任何字符串作为键。当您只想查看 key 是否存在时，Set 对象是合适的，如下所示:

if (mySet.has(someString)) {
    //code here
}

并且，Map 适用于存储该键的值，如下所示:

if (myMap.has(someString)) {
    let val = myMap[someString];
    // do something with val here
}

从 node V4 开始，这两个 ES6 功能现在都内置到 node.js 中(截至本次编辑，node.js 的当前版本是 v6)。

参见 this performance comparison查看 Set 操作比许多其他选择快多少。

旧答案

所有重要的性能问题都应在 jsperf.com 等工具中通过实际性能测试进行测试。在您的情况下，javascript 对象使用类似哈希表的实现，因为如果没有执行得很好的东西，整个实现会很慢，因为很多 javascript 使用对象。

对象上的字符串键将是我要测试的第一件事，也是我对最佳表现者的猜测。由于对象的内部是用 native 代码实现的，我希望这比您自己用 javascript 实现的哈希表或二进制搜索更快。

但是，正如我开始回答的那样，您应该在像 jsperf 这样的工具中使用您最关心的字符串的数量和长度来真正测试您的具体情况。