检测值是否在Javascript中的一组值中的最快方法

Question

我在Javascript中有一组字符串,我需要编写一个函数来检测另一个特定字符串是否属于该组.

实现这一目标的最快方法是什么？是否可以将值组放入数组中,然后编写一个搜索数组的函数？

我想如果我保持值的排序并进行二分查找,它应该足够快.或者还有其他一些聪明的方法可以做到这一点,它可以更快地工作？

Answer 1

使用哈希表,并执行以下操作:

// Initialise the set

mySet = {};

// Add to the set

mySet["some string value"] = true;

...

// Test if a value is in the set:

if (testValue in mySet) {
     alert(testValue + " is in the set");
} else {
     alert(testValue + " is not in the set");
}

Answer 2

您可以使用如下对象:

// prepare a mock-up object
setOfValues = {};
for (var i = 0; i < 100; i++)
  setOfValues["example value " + i] = true;

// check for existence
if (setOfValues["example value 99"]);   // true
if (setOfValues["example value 101"]);  // undefined, essentially: false

这利用了对象被实现为关联数组的事实.这有多快取决于您的数据和JavaScript引擎实现,但您可以轻松地进行一些性能测试,以与其他变体进行比较.

如果一个值可以在你的集合中出现多次并且"多久"对你很重要,你也可以用一个递增的数字代替我用来举例说明的布尔值.

Answer 3

偶然发现了这一点，并意识到答案已经过时了。在这个时代，除非在极端情况下，您不应该使用哈希表来实现集合。你应该使用set。

例如：

> let set = new Set();
> set.add('red')

> set.has('red')
true
> set.delete('red')
true
> set.has('red')
false

有关更多示例和讨论，请参阅此 SO 帖子：Ways to create a Set in JavaScript?

Answer 4

对上述哈希解决方案的评论.实际上{}会创建一个对象(也在上面提到),这可能会导致一些副作用.其中之一是您的"哈希"已经预先填充了默认对象方法.

因此,"toString" in setOfValues将true(至少在Firefox).你可以添加另一个字符,例如"." 到你的字符串来解决这个问题或使用"原型"库提供的哈希对象.