fastest way to detect if a value is in a group of

Question

I have a group of strings in Javascript and I need to write a function that detects if another specific string belongs to this group or not.

What is the fastest way to achieve this? Is it alright to put the group of values into an array, and then write a function that searches through the array?

I think if I keep the values sorted and do a binary search, it should work fast enough. Or is there some other smart way of doing this, which can work faster?

Answer 1

Use a hash table, and do this:

// 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

Depends on how much values there are.

If there are a few values (less than 10 to 50), searching through the array may be ok. A hash table might be overkill.

If you have lots of values, a hash table is the best option. It requires less work than sorting the values and doing a binary search.

Answer 3

You can use ES6 includes.

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

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

Answer 4

A comment to the above mentioned hash solutions. Actually the {} creates an object (also mentioned above) which can lead to some side-effects. One of them is that your "hash" is already pre-populated with the default object methods.

So "toString" in setOfValues will be true (at least in Firefox). You can prepend another character e.g. "." to your strings to work around this problem or use the Hash object provided by the "prototype" library.

Answer 5

Stumbled across this and realized the answers are out of date. In this day and age, you should not be implementing sets using hashtables except in corner cases. You should use sets.

For example:

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

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

Refer to this SO post for more examples and discussion: Ways to create a Set in JavaScript?

Answer 6

Using a hash table might be a quicker option.

Whatever option you go for its definitely worth testing out its performance against the alternatives you consider.