5

If I have a whitelist of strings that I want to check everything the user inputs into my javascript program, what's the most efficient way to do that? I could just have an array and loop through it until a match has been found but that's O(N). Is there an yway to do it that's better and doesn't involve any sort of key value lookup, just checking to see if that value exists?

EDIT: I guess what I'm looking for is the equivalent of a set in C++ where I can just check to see if a value I'm given already exists in the set.

barndog
  • 6,975
  • 8
  • 53
  • 105
  • Duplicate: http://stackoverflow.com/questions/143847/best-way-to-find-an-item-in-a-javascript-array and again: http://stackoverflow.com/questions/237104/array-containsobj-in-javascript – Hanlet Escaño Mar 21 '13 at 18:47
  • 3
    It's not a direct duplicate of those questions since the answer to this is to not use an array, the answer is to use an object. – forivall Mar 21 '13 at 18:54
  • Possible duplicate of [How do I check if an array includes a value in JavaScript?](https://stackoverflow.com/questions/237104/how-do-i-check-if-an-array-includes-a-value-in-javascript) – Giorgi Gvimradze Oct 26 '19 at 14:28

3 Answers3

1

Sort the array, use binary search for the look-ups.

Or

Create an object where the key is the item and use the hash look-up whitelist[value] != undefined

Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
1

I think you'll find that key-value lookup is almost identical in performance to some kind of set implementation without values. (Many standard libraries actually just implement a set using a map)

Russell Zahniser
  • 16,188
  • 39
  • 30
1

Just make it a simple js object instead of an array.

var whitelist = {
  "string1":true,
  "string2":true
}

and then you can just check if(whitelist[str]) to check if its available.

Or use if(str in whitelist).

I expect that the first will have slightly better performance (I haven't verified that), but the second is more readable and makes the purpose clear. So its your choice of which is a better fit.

Ben McCormick
  • 25,260
  • 12
  • 52
  • 71