Operator to test for collection membership in Javascript

Question

how could I efficiently do collection membership checks in Javascript? I have a potentially large array of strings and I need to verify if a given string is a member of the array.

Initially I thought that the in operator could help, but after reading the docs on Mozilla Developer Network I discovered that its purpose is different. In Javascript it checks if the specified property is in the specified object.

For performance related reasons I'd prefer to use a js builtin, but if a such function doesn't exist I'll probably end to do one of the following:

1. use the array to create an object having array elements as keys and then use in
2. iterate over array elements and do the comparison item by item
3. implement a binary search

Any opinion? Or better ideas?

Thanks

Anchylose

have a look Javascript - array.contains(obj) – Nitrogen

Answer 1

As you'll find out in this question, pretty much every framework has a function for that, some browsers even natively implement an indexOf function (not all of them though).

It seems that they all do it by iterating the array, some using the other direction (starting from the end) because it seems to be faster. For sublinear algorithms, you'll probably need to implement some kind of a hash set with binary search on keys.

Example of a HashSet implentation can be found here.

Pectoral

I can't use indexOf because I need to support IE too (all versions)! I'll look closely at the link you gave, thanks. – Anchylose

Answer 2

Does this have good enough perfomance?

var inArray = function(array, value) {
    var i = array.length;

    while (i--) {
        if (array[i] == value) {
            return true;
        }
    }

    return false;

}

jsFiddle.

Unless your application requires it (measure and see if this is the bottleneck), this should be fast enough and straight forward enough to read.

Penicillin

Answer 3

Do you have to use arrays? Can you just use an object from the beginning? If you need to iterate over the elements you could use a for in loop on the object.

Binary search only works if its sorted. That might be a good idea if you know you're going to search through the array many times. Otherwise option 2 would be faster.

Bolzano

If I had an object I'd have used in (I don't have to iterate). Thanks for having reminded me that binary search requires sorted data structures. – Anchylose

Answer 4

I'd recommand that you use both an object and array.

This way, you can very quickly do membership tests on the object, and use the array when you need your items to remain sorted.

This is the only way I found to emulate a "sorted dictionary" type of behavior.

Garage