JavaScript – Object vs. Array Lookup Performance

javascript

What is the performance difference between retrieving the value by key in a JavaScript object vs iterating over an array of individual JavaScript objects?

In my case, I have a JavaScript object containing user information where the keys are the user's IDs and the values are each user's information.

The reason I ask this is because I would like to use the angular-ui-select module to select users, but I can't use that module with a Javascript object – it requires an array.

How much, if anything, am I sacrificing by switching from a lookup by key, to a lookup by iteration?

By key:

var user = users[id];

By iteration

var user;

for (var i = 0; i < users.length; i ++) {
  if (users[i].id == id) { 
    user = users[i]; break;
  }
}

Best Answer

The answer to this is browser dependent, however, there are a few performance tests on jsperf.com on this matter. It also comes down to the size of your data. Generally it is faster to use object key value pairs when you have large amounts of data. For small datasets, arrays can be faster.

Array search will have different performance dependent on where in the array your target item exist. Object search will have a more consistent search performance as keys doesn't have a specific order.

Also looping through arrays are faster than looping through keys, so if you plan on doing operations on all items, it can be wise to put them in an array. In some of my project I do both, since I need to do bulk operations and fast lookup from identifiers.

A test:

http://jsben.ch/#/Y9jDP

Related Solutions

JavaScript – Efficient Object Property Lookup

This can be tested empirically:

<script language="javascript">

alert("Initialising test object...");
var obj = new Object();
for (var i=0; i<1000000; i++) obj["prop"+i] = i;


alert("Initialised. Doing Test.");

var d1 = (new Date()).getTime();

needle = obj["prop"+(i-1)]; // last object
for (var prop in obj) {
    if (obj === needle) {
        // some decision
        break;
    }
}

var ms1 = ((new Date()).getTime()) - d1;

alert("Method 1 took "+ms1+"ms.")

var d2 = (new Date()).getTime();

if (typeof obj["prop"+(i-1)] != 'undefined') {
    // some decision
}

var ms2 = (new Date()).getTime() - d2;
alert("Method 2 took "+ms2+"ms.")

</script>

Method 1 takes MUCH longer than Method 2. This is hardly surprising since all of the computing necessary to execute Method 2 is included in Method 1 plus MUCH more.

JavaScript – Array vs Object Efficiency

The short version: Arrays are mostly faster than objects. But there is no 100% correct solution.

Update 2017 - Test and Results

var a1 = [{id: 29938, name: 'name1'}, {id: 32994, name: 'name1'}];

var a2 = [];
a2[29938] = {id: 29938, name: 'name1'};
a2[32994] = {id: 32994, name: 'name1'};

var o = {};
o['29938'] = {id: 29938, name: 'name1'};
o['32994'] = {id: 32994, name: 'name1'};

for (var f = 0; f < 2000; f++) {
    var newNo = Math.floor(Math.random()*60000+10000);
    if (!o[newNo.toString()]) o[newNo.toString()] = {id: newNo, name: 'test'};
    if (!a2[newNo]) a2[newNo] = {id: newNo, name: 'test' };
    a1.push({id: newNo, name: 'test'});
}

Original Post - Explanation

There are some misconceptions in your question.

There are no associative arrays in Javascript. Only Arrays and Objects.

These are arrays:

var a1 = [1, 2, 3];
var a2 = ["a", "b", "c"];
var a3 = [];
a3[0] = "a";
a3[1] = "b";
a3[2] = "c";

This is an array, too:

var a3 = [];
a3[29938] = "a";
a3[32994] = "b";

It's basically an array with holes in it, because every array does have continous indexing. It's slower than arrays without holes. But iterating manually through the array is even slower (mostly).

This is an object:

var a3 = {};
a3[29938] = "a";
a3[32994] = "b";

Here is a performance test of three possibilities:

Lookup Array vs Holey Array vs Object Performance Test

An excellent read about these topics at Smashing Magazine: Writing fast memory efficient JavaScript