Object key vs array lookup performance

Question

Example 1:

["member1", "member2",...,..., "member100000"]

Example 2:

{
    "member1": true, // (doesn't really need values, only keys :/)
    "member2": true,
    "...",
    "member100000": true
}

I'm storing members in an array on each piece of content like in Example 1, but doing it like this I'd have to iterate through 49999 items in my the array, to find member 50000, so I was thinking simply checking if a specific key is defined within the javascript object would be a better approach here, although I do not need to store a value, but only check whether the key is undefined or not?

What I need is to be able to check if eg. "member50000" exists as a value within my array - or as a key inside my object.

I did some benchmarking tests, but I'm not sure I've come to the right conclusion, or if I'm doing something wrong in my comparison: http://jsperf.com/lolda123

According to the above test results, would it then be fair to conclude that saving a key/value pair within an object where the value is boolean (true), and doing if(obj["member50000"]) is the best performing option? Even if no property with the given key even exists? As I see it, according to my test results, checking for the existence of the key itself, would seem much more expensive in terms of performance, but checking if the key is there, really is all I need.

I don't care about the value, so am I missing something here, or why would the better solution seem like being the one where you look up the value, by the key, instead of just looking up the key, inside the object?

Your test case seems to be missing `arr.indexOf(key)`. It'll return -1 if it doesn't find it. I'd be interested in the result. — Katana314, May 22 '15 at 14:19
Another method I'd try to benchmark is the "new" (ES6) `Set` type. — Amit, May 22 '15 at 14:20
And, in addition to what the others suggested, if you are open to using jQuery, you could also test: `$.inArray(key, arr);` — talemyn, May 22 '15 at 14:23
I think this might be a duplicate of : http://stackoverflow.com/questions/6075458/performance-differences-between-jquery-inarray-vs-object-hasownproperty — Pierre Henry, May 22 '15 at 14:25
Katana314, I've now added a test of indexOf like you suggested. As you'd expect, it does not perform very well. Talemyn, I don't think using jquery can ever really come close to raw javascript in terms of performance. — Dac0d3r, May 22 '15 at 14:26
Pierre it's not a duplicate. I'm not asking about jquery here. Of course jquery will always be slower, since it's just a library to sit on top of javascript. Jquery is not what I'm asking here. — Dac0d3r, May 22 '15 at 14:29
Values aren't hashed, keys are. Key lookup will always be virtually instantaneous, while looping will always take orders of magnitudes longer. — deceze, May 22 '15 at 15:10
Sure you don't use jQuery, but the `arrayContains` method of jQuery is a form of array lookup and the underlying logic is the same whether you use jQuery or not : iterate the entire array. Anyway the answers there confirm your finding : direct value lookup is somewhat faster than `hasOwnProperty()`. But I am not sure why... — Pierre Henry, May 22 '15 at 15:15
Pierre I guess what's most interesting is that looking up "just the key" without even considering the value, seem to be slower than looking up the value (or missing value) by using the key. That is where I suspect something might be wrong. I would assume checking if the key is defined, should be faster, but my results says otherwise. So I'm interested in flaws in the test, or an explanation why this is the case (if it is). :-) — Dac0d3r, May 22 '15 at 15:38

score 3 · Answer 1 · answered Aug 24 '16 at 15:02

Well I thought the same thing, that using an Object will be faster, and I proved myself wrong!

I ran the performance tests using the same stack as jsPerf on NodeJS 6.3 ( V8 engine ):

https://github.com/amoldavsky/js-array-indexof-vs-hashmap

The results are:

lookup is much faster on larger data sets
creating the Object datastructure ( basically a HashMap ) is EXPENSIVE! and much slower than using an array
when combined insert and lookup, array.indexOf is faster by a very big margin

If you believe I made a mistake in any of my tests feel free to bring it up and we can retest. Though so far looks like array.indexOf is much faster.

You're doing `(index.indexOf( url ) > -1) && index.push( url );`, but it should be `||`, shouldn't it? — maaartinus, Jun 30 '18 at 23:32

score 1 · Answer 2 · answered Jun 16 '15 at 16:34

1

obj.hasOwnProperty is much faster than arr.indexOf http://jsperf.com/array-hasownproperty-vs-array-indexof

Using arr.indexOf should also be faster than any looping you do.

answered Jun 16 '15 at 16:34

erikvold

15,988
11
54
98

Why do you think `indexOf` would be faster than a loop? – Bergi Jun 16 '15 at 17:47
1

…which is not necessarily faster than optimised compiled javascript, as many cases have shown. – Bergi Jun 16 '15 at 18:06
1

There are a number of reasons why one's javascript would not be optimized. It's almost always better to rely to the js engine, and allow those working on optimizing the engine to optimize the code we write. At the moment there is a lot of focus on optimizing loops, that is true. – erikvold Jun 16 '15 at 18:11
Interestingly that test - right now (2018) - is faster for array.indexOf on the latest Chrome (Chrome 67.0.3396 / Windows 10 0.0.0), but the object.hasOwnProperty route is faster in every other browser I tested (Firefox, IE11). On Edge they're just about even. – Katinka Hesselink Jul 26 '18 at 07:41
I tested in Safari 13.1 and `hasOwnProperty` is 36% slower than `indexOf` – Mick Mar 30 '20 at 15:51

score 0 · Answer 3 · answered Sep 05 '20 at 03:14

Was curious about this since Object.prototype is an ancestor of any array instance, therefore it must be bulkier than an object and slower when it comes to property lookup.

In my test I store a list of strings as array elements and an object keys. Then I measure how much time it takes to check for existance of each key in both object and array implementations. Repeat 100000 times.

Generally, objects happen to be faster. Null objects are significantly faster on chromium.

{
  const iterations = 1000000;

  let arrTotal = 0;
  let objTotal = 0;
  let nullObjTotal = 0;

  let a = '';

  let keys = [
    "The standard Lorem Ipsum passage",
    "used since the 1500sLorem ipsum dolor sit amet",
    "consectetur adipiscing elit",
    "Ut enim ad minim veniam",
    "Excepteur sint occaecat cupidatat non proident",
    "sunt in culpa qui officia deserunt mollit anim id est laborum",
    "Section 1",
    "32 of de Finibus Bonorum et Malorum",
    "totam rem aperiam",
    "Neque porro quisquam est",
    "qui dolorem ipsum quia dolor sit amet",
    "consectetur",
    "adipisci velit",
    "Ut enim ad minima veniam",
    "the master-builder of human happiness",
    "No one rejects",
    "dislikes",
    "or avoids pleasure itself",
    "because it is pleasure",
    "because it is pain",
    "To take a trivial example",
    "which of us ever undertakes laborious physical exercise",
    "33 of de Finibus Bonorum et Malorum",
    "similique sunt in culpa qui officia deserunt mollitia animi",
    "id est laborum et dolorum fuga",
    "Et harum quidem rerum facilis est et expedita distinctio",
    "Nam libero tempore",
    "omnis voluptas assumenda est",
    "omnis dolor repellendus",
    "Itaque earum rerum hic tenetur a sapiente delectus",
    "1914 translation by H",
    "RackhamOn the other hand",
    "so blinded by desire",
    "These cases are perfectly simple and easy to distinguish",
    "In a free hour",
    "every pleasure is to be welcomed and every pain avoided",
    "or else he endures pains to avoid worse pains"
  ];

  let nullObj = Object.create(null);
  for (let key of keys) nullObj[key] = null;

  let obj = {
    "The standard Lorem Ipsum passage": null,
    "used since the 1500sLorem ipsum dolor sit amet": null,
    "consectetur adipiscing elit": null,
    "Ut enim ad minim veniam": null,
    "Excepteur sint occaecat cupidatat non proident": null,
    "sunt in culpa qui officia deserunt mollit anim id est laborum": null,
    "Section 1": null,
    "32 of de Finibus Bonorum et Malorum": null,
    "totam rem aperiam": null,
    "Neque porro quisquam est": null,
    "qui dolorem ipsum quia dolor sit amet": null,
    "consectetur": null,
    "adipisci velit": null,
    "Ut enim ad minima veniam": null,
    "the master-builder of human happiness": null,
    "No one rejects": null,
    "dislikes": null,
    "or avoids pleasure itself": null,
    "because it is pleasure": null,
    "because it is pain": null,
    "To take a trivial example": null,
    "which of us ever undertakes laborious physical exercise": null,
    "33 of de Finibus Bonorum et Malorum": null,
    "similique sunt in culpa qui officia deserunt mollitia animi": null,
    "id est laborum et dolorum fuga": null,
    "Et harum quidem rerum facilis est et expedita distinctio": null,
    "Nam libero tempore": null,
    "omnis voluptas assumenda est": null,
    "omnis dolor repellendus": null,
    "Itaque earum rerum hic tenetur a sapiente delectus": null,
    "1914 translation by H": null,
    "RackhamOn the other hand": null,
    "so blinded by desire": null,
    "These cases are perfectly simple and easy to distinguish": null,
    "In a free hour": null,
    "every pleasure is to be welcomed and every pain avoided": null,
    "or else he endures pains to avoid worse pains": null
  };

  let arr = [
    "The standard Lorem Ipsum passage",
    "used since the 1500sLorem ipsum dolor sit amet",
    "consectetur adipiscing elit",
    "Ut enim ad minim veniam",
    "Excepteur sint occaecat cupidatat non proident",
    "sunt in culpa qui officia deserunt mollit anim id est laborum",
    "Section 1",
    "32 of de Finibus Bonorum et Malorum",
    "totam rem aperiam",
    "Neque porro quisquam est",
    "qui dolorem ipsum quia dolor sit amet",
    "consectetur",
    "adipisci velit",
    "Ut enim ad minima veniam",
    "the master-builder of human happiness",
    "No one rejects",
    "dislikes",
    "or avoids pleasure itself",
    "because it is pleasure",
    "because it is pain",
    "To take a trivial example",
    "which of us ever undertakes laborious physical exercise",
    "33 of de Finibus Bonorum et Malorum",
    "similique sunt in culpa qui officia deserunt mollitia animi",
    "id est laborum et dolorum fuga",
    "Et harum quidem rerum facilis est et expedita distinctio",
    "Nam libero tempore",
    "omnis voluptas assumenda est",
    "omnis dolor repellendus",
    "Itaque earum rerum hic tenetur a sapiente delectus",
    "1914 translation by H",
    "RackhamOn the other hand",
    "so blinded by desire",
    "These cases are perfectly simple and easy to distinguish",
    "In a free hour",
    "every pleasure is to be welcomed and every pain avoided",
    "or else he endures pains to avoid worse pains"
  ];

  for (let i = 0, stamp = 0, length = keys.length; i < iterations; ++i) {
    stamp = performance.now();
    for (let j = 0; j < length; ++j) {
      if (keys[j] in obj) a = keys[j];
    }
    objTotal += (performance.now() - stamp)/1000;

    stamp = performance.now();
    for (let j = 0; j < length; ++j) {
      if (~arr.indexOf(keys[j])) a = keys[j];
    }
    arrTotal += (performance.now() - stamp)/1000;

    stamp = performance.now();
    for (let j = 0; j < length; ++j) {
      if (keys[j] in nullObj) a = keys[j];
    }
    nullObjTotal += (performance.now() - stamp)/1000;
  }

  console.log(`Array total: ${arrTotal}; Array avarage: ${arrTotal/iterations}(s).`);
  console.log(`Object total: ${objTotal}; Object avarage: ${objTotal/iterations}(s).`);
  console.log(`Null object total: ${nullObjTotal}; Null object avarage: ${nullObjTotal/iterations}(s).`);
}

Object key vs array lookup performance

3 Answers3