检测某个值是否在 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

偶然发现这个问题并意识到答案已经过时了。在当今时代，除非在极端情况下，否则不应使用哈希表来实现集合。您应该使用sets。

例如：

> 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 中）。 您可以在前面添加另一个字符，例如“。”到您的字符串来解决此问题或使用“原型”库提供的哈希对象。

Answer 5

一种可能的方法，如果集合是不可变的，但仍然可以与变量集一起使用，则特别有效：

var haystack = "monday tuesday wednesday thursday friday saturday sunday";
var needle = "Friday";
if (haystack.indexOf(needle.toLowerCase()) >= 0) alert("Found!");

当然，您可能需要根据必须放在那里的字符串来更改分隔符...

更强大的变体可以包含界限，以确保“day wed”和“day”都不能正向匹配：

var haystack = "!monday!tuesday!wednesday!thursday!friday!saturday!sunday!";
var needle = "Friday";
if (haystack.indexOf('!' + needle.toLowerCase() + '!') >= 0) alert("Found!");

如果输入确定（例如，超出数据库等），则可能不需要。

我在 Greasemonkey 脚本中使用了它，其优点是直接使用 GM 存储中的干草堆。

Answer 6

使用哈希表可能是一个更快的选择。

无论您选择哪种选择，都绝对值得根据您考虑的替代方案来测试其性能。

Answer 7

取决于有多少值。

如果值较少（小于 10 到 50），则可以通过数组进行搜索。哈希表可能有点过分了。

如果你有很多值，哈希表是最好的选择。它比对值进行排序和进行二分搜索所需的工作量更少。

Answer 8

我知道这是一篇旧帖子。但要检测某个值是否在一组值中，我们可以通过数组

indexOf()

进行操作，该数组搜索并检测该值的存在

var myString="this is my large string set";
var myStr=myString.split(' ');
console.log('myStr contains "my" = '+ (myStr.indexOf('my')>=0));
console.log('myStr contains "your" = '+ (myStr.indexOf('your')>=0));

console.log('integer example : [1, 2, 5, 3] contains 5 = '+ ([1, 2, 5, 3].indexOf(5)>=0));

Answer 9

您可以使用 ES6 包括。

var string = "The quick brown fox jumps over the lazy dog.",
  substring = "lazy dog";

console.log(string.includes(substring));

Answer 10

这是在集合中搜索它的一种非常简短的方法（使用数组包含函数）：

var animal="pig";
if(["dog","cat","pig","horse"].includes(animal)){
document.write ("we found the "+animal);
}