Operator to test for collection membership in Javascript - Stack Overflow

admin管理员组

文章数量:1289422

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 parison item by item
3. implement a binary search

Any opinion? Or better ideas?

Thanks

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 parison item by item
3. implement a binary search

Any opinion? Or better ideas?

Thanks

• javascript
• collections
• parison
• membership
• in-operator

Share Improve this question Follow asked Mar 8, 2011 at 11:29 PaoloPaolo 21.1k2121 gold badges7676 silver badges121121 bronze badges 1

• 2 have a look Javascript - array.contains(obj) – Maxym Commented Mar 8, 2011 at 11:35

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 2

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.

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.

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.

I'd remand 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.

本文标签： Operator to test for collection membership in JavascriptStack Overflow