9

I have a situation where I can choose to implement a collection of string keys as an object:

$.each(objects, function (key, object) {
    collection[key] = "doesn't matter";
});

or an array:

$.each(objects, function (key, object) {
    collection.push(key);
});

I'd like to be able to quickly determine whether or not the collection contains a given key. If collection is an object, I can use:

if (collection.hasOwnProperty(key_to_find)) { // found it!... }
else { // didn't find it... }

If collection is an array, I can use:

if ($.inArray(key_to_find, collection)) { // found it!... }
else { // didn't find it... }

I'd imagine using JavaScript's built-in hasOwnProperty would be faster than jQuery's inArray(), but I'm not entirely sure. Does anyone know more about the performance differences between these two methods? Or, is there a more efficient alternative here that I am not aware of?

Gaurav
  • 974
  • 9
  • 13
  • The other consideration here is space: I'm assuming that an object can be slightly smaller than an array since the key string will be the same in both objects and instead of a 32-bit pointer associated with each key in the array, the object can have a 8-bit char (just one char) as the value for each keyed parameter. These assumptions could be way off :) - I'd appreciate any pointers to how these things are stored on various platforms (e.g browsers, machines, etc.). – Gaurav May 20 '11 at 17:23
  • How big is the set of keys? If it's small, it shouldn't be too much of a difference. If it's big, the constant access time (or otherwise "fast") for the object will be much faster. – Cristian Sanchez May 20 '11 at 17:23

5 Answers5

7

If we're talking just how long it takes to check, then there's really no contest:

http://jsperf.com/array-vs-obj

hasOwnProperty is way way faster for the reasons stated by others.

James Montagne
  • 77,516
  • 14
  • 110
  • 130
  • 1
    Using `obj['key']` is even faster than `hasOwnProperty()`. Also `true` can be used as the value added, instead of `"doesn't matter"` – Dan Manastireanu May 20 '11 at 18:24
  • Good point. That is generally how I do it, but didn't think to check it, just pulled the code from the question. – James Montagne May 20 '11 at 18:37
  • Thanks - didn't know that `obj['key']` wouldn't throw an undefined property error if the key didn't exist. Is it correct to say that JS will properly evaluate to true or false on an object param that does (true) or does not (false) exist as long as we are sure the object exists? – Gaurav May 24 '11 at 21:21
  • That test is showing the opposite in my browser. Maybe the JS engines have been improved since 2011? – Mister Smith Jun 05 '13 at 14:13
  • Oops, its not. Someone misplaced the labels in the results table and the one labeled "array" is the actual object test :) – Mister Smith Jun 05 '13 at 14:18
1

Mmmh, if the collection is an array you can also use the native indexOf on it, no? https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf

Claudio
  • 5,740
  • 5
  • 33
  • 40
  • 3
    As noted on [this stackoverflow article](http://stackoverflow.com/questions/2790001/fixing-javascript-array-functions-in-internet-explorer-indexof-foreach-etc), Array.indexOf() is not supported in all browsers, hence the use of jQuery.inArray(). Based on the performance test provided by @kingjiv below, seems like Object.hasOwnProperty() is much faster than jQuery.inArray(). – Gaurav May 24 '11 at 21:17
1

The array method is slower, because it requires linear time to find an element in the array (the code must step through potentially every element). hasOwnProperty will be much faster as it can use a hash table lookup, which occurs in constant time.

Lyn Headley
  • 11,368
  • 3
  • 33
  • 35
1

An object will have very fast access times for properties. However, you still have to account for overhead from calculating the hash etc (if the implementation uses hash tables to back objects). If the set of keys is relatively small, there shouldn't be too much of a difference. If it's larger, then I would go with the object/hash to store properties.

That said, it's a little easier to manage duplicate keys with the object, so I would personally would go with the dictionary.

Unless this is a bottleneck in your application, you shouldn't over think it.

Cristian Sanchez
  • 31,171
  • 11
  • 57
  • 63
0

Short Answer: .indexOf() (as @Claudio mentions)

Long Answer: Have a look at a quick speed test I coded up - http://jsfiddle.net/cvallance/4YdxJ/3/ - the difference is really negligible.

Charlino
  • 15,802
  • 3
  • 58
  • 74
  • The results here are in seconds? – Musikero31 Jul 04 '16 at 07:23
  • @Musikero31 Should be millis. Charlino, you're performance test is very simple and not exactly accurate. With such a small collection, pretty much any algorithm for determining whether the item exists in the collection will return relatively the same results. Relative performance only really comes into play when you scale up the size of the collection. – Nick Aug 11 '16 at 16:46