8

在阅读了许多类似的问题后：

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

A. 对字符串数组进行排序，然后使用二分查找？或者：

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

?

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

但我不知道 B 的复杂性。

如果将Javascript对象实现为哈希表，那么B的复杂度平均为O(1)，优于A。但是，我不知道Javascript对象是否真的实现为哈希表！

4

2 回答 2

6

2016 年更新

由于您询问的是 node.js 并且它是 2016 年，因此您现在可以使用 ES6 中的SetorMap对象，因为它们内置于 ES6 中。两者都允许您使用任何字符串作为键。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）。

请参阅此性能比较，了解Set操作比许多其他选择快多少。

较早的答案

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

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

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

于 2013-06-12T20:35:50.320 回答
2

对于固定的大型字符串数组，我建议使用某种形式的基数搜索此外，请查看此包 中的不同数据结构和算法（AVL 树、队列/堆等）

我很确定使用 JS 对象作为字符串的存储将导致该对象的“哈希模式”。根据实现，这可能是 O(log n) 到 O(1) 时间。查看一些jsperf基准来比较排序数组上的属性查找与二进制搜索。

在实践中，特别是如果我不打算在浏览器中使用代码，我会将这个功能卸载到 redis 或 memcached 之类的东西上。

于 2013-06-13T01:21:38.473 回答