Javascript - What's faster: a linear list search or getting an object value?

An object lookup will on average be much faster when trying to find a random element, especially when you are searching through a large number of items. This is because the underlying algorithm to do so is a B-tree search which has a time complexity of O(log n) and allows it to quickly look up an items membership without having to check it against each element in the object.

This is opposed to when searching in an array you must check each element before deciding if is not in the array which has a linear time complexity of O(n).

Here is the benchmark showing object lookup is faster: http://jsperf.com/array-vs-objv2/6

Without knowing all the black magic workings of JavaScript, I can say that something like a['3'] does not use linear search.

Does JavaScript have a direct reference to that element so it doesn't even need to do a search? Maybe. And if it does, it uses that to find a['3'] faster than a linear search, even though it might cost a little more memory. (I think this is what it actually does.)

If it doesn't, it and it actually searches through your data structure, it almost certainly doesn't use a simple linear search. There's probably some inner workings, or some sort of binary tree search or some other confoundedness.

I modified code like below to make both code equivalent before comparing their performance in jsPerf http://jsperf.com/array-vs-objv2

Test 1:

Test Setup:

var a = [];
var b = {};

for (var i = 1; i <= 100000; i++) {
   a.push(i);
   b[''+i] = true;
}

Using Arrays:

for(var i = 0; i < a.length; i++) { 
  if (a[i] === 99999) {
     console.log(true);
     return;
  }
}

Using Object: (Faster)

console.log(b['99999']);

Test 2:

Using Arrays: (Faster)

a = ['1','2','3','4','5']
for(var i = 0; i < a.length; i++) { 
  if (a[i] === 3) {
     console.log(true);
     return;
  }
}

Using Object:

a = {'1': true, '2': true, '3': true, '4': true, '5': true};
console.log(a['3']);

Resut: (As Trevor pointed out) The array search will be faster for fewer items, but when looking up on larger list.. the array is slower because of the linear search.

The associative array will perform faster, it only requires one logical operation. Though to achieve this it requires more be stored in memory to link the key with the value. This is roughly equivalent to a hash table vs array argument.

The drawbacks, slower insertions and higher memory use. How fast lookups are depends on the engine.

https://developers.google.com/v8/design

Complete analysis of both setup and search: http://jsperf.com/array-vs-objv2/5

Check out this benchmark figure

The access time of object property and array item are close

In your first case, there are three times of access to the array item

And in your second case, there are only one time of access to the object property

So I think the second one should be faster

a = {'1': true, '2': true, '3': true, '4': true}
if (a['3'] === true) {
  console.log("found it");
}

will be faster in the most cases, then

a = ['1','2','3','4','5']
for(var i = 0; i < a.length; i++) { 
  if (a[i] == 3) {
    console.log('found it!')
  }
}

Because the second one might need to loop through all values of the array.