Take the following code example:

var myObject = {};
var i = 100;

while (i--) {
    myObject["foo"+i] = new Foo(i);
}

console.log(myObject["foo42"].bar());

I have a few questions.

What kind of data structure do the major engines (IE, Mozilla, Chrome, Safari) use for storing key-value pairs? I'd hope it's some kind Binary Search tree, but I think they may use linked lists (due to the fact iterating is done in insertion order).

If they do use a search tree, is it self balancing? Because the above code with a conventional search tree will create an unbalanced tree, causing worst case scenario of O(n) for searching, rather than O(log n) for a balanced tree.

I'm only asking this because I will be writing a library which will require efficient retrieval of keys from a data structure, and while I could implement my own or an existing red-black tree I would rather use native object properties if they're efficient enough.

Take the following code example:

var myObject = {};
var i = 100;

while (i--) {
    myObject["foo"+i] = new Foo(i);
}

console.log(myObject["foo42"].bar());

I have a few questions.

What kind of data structure do the major engines (IE, Mozilla, Chrome, Safari) use for storing key-value pairs? I'd hope it's some kind Binary Search tree, but I think they may use linked lists (due to the fact iterating is done in insertion order).

If they do use a search tree, is it self balancing? Because the above code with a conventional search tree will create an unbalanced tree, causing worst case scenario of O(n) for searching, rather than O(log n) for a balanced tree.

I'm only asking this because I will be writing a library which will require efficient retrieval of keys from a data structure, and while I could implement my own or an existing red-black tree I would rather use native object properties if they're efficient enough.

• javascript
• data-structures
• time-plexity
• javascript-objects
• javascript-engine

• what exactly are you trying to acplish? if you're storing so much data client side that you need to worry about how efficient a hash lookup is, then you might be doing it wrong. – Andy Ray Commented Aug 22, 2012 at 6:32
• 1 Have you dug into the code of any of the implementations, e.g. V8? – alex Commented Aug 22, 2012 at 6:38
• 1 Even assuming for the sake of argument that the native object properties are inefficient, surely implementing your own version would be no better given you'd have to add your own layer of code on top of some native structure? – nnnnnn Commented Aug 22, 2012 at 6:39
• Speed is the currency of puting, why should I settle for an inferior algorithm? – Randy the Dev Commented Aug 22, 2012 at 6:45
• 1 @nnnnnn The same algorithms should work faster when they're implemented in native code. But the requirements for the algorithms implemented by the browser engines are different than Andrew's requirements, as object in javascript can do much more than being used as associative array substitutes. So it is possible that the browser engine implementors had to stick to a slower algorithm to meet their requirements. In that case, a specialized algorithm that just fits the purpose of doing Binary Tree Searches could outrun the native implementation of objects, even it its implemented in javascript. – Simon Commented Aug 22, 2012 at 7:23

1 Answer 1

The question is hard to answer for a couple reasons. First, the modern browsers all heavily and dynamically optimize code while it is executing so the algorithms chosen to access the properties might be different for the same code. Second, each engine uses different algorithms and heuristics to determine which access algorithm to use. Third, the ECMA specification dictates what the result of must be, not how the result is achieved so the engines have a lot of freedom to innovate in this area.

That said, given your example all the engines I am familiar with will use some form of a hash table to retrieve the value associated with foo42 from myobject. If you use an object like an associative array JavaScript engines will tend to favor a hash table. None that I am aware of use a tree for string properties. Hash tables are worst case O(N), best case O(1) and tend to be closer to O(1) than O(N) if the key generator is any good. Each engine will have a pattern you could use to get it to perform O(N) but that will be different for each engine. A balanced tree would guarantee worst case O(log N) but modifying a balanced tree while keeping it balanced is not O(log N) and hash tables are more often better than O(log N) for string keys and are O(1) to update (once you determine you need to, which is the same big-O as read) if there is space in the table (periodically O(N) to rebuild the table but the tables usually double in space which means you will only pay O(N) 7 or 8 times for the life of the table).

Numeric properties are special, however. If you access an object using integer numeric properties that have few or no gaps in range, that is, use the object like it is an array, the values will tend to be stored in a linear block of memory with O(1) access. Even if your access has gaps the engines will probably shift to a sparse array access which will probably be, at worst, O(log N).

Accessing a property by identifier is also special. If you access the property like,

myObject.foo42

and execute this code often (that is, the speed of this matters) and with the same or similar object this is likely to be optimized into one or two machine instructions. What makes objects similar also differs for each engine but if they are constructed by the same literal or function they are more likely to be treated as similar.

No engine that does at all well on the JavaScript benchmarks will use the same algorithm for every object. They all must dynamically determine how the object is being used and try to adjust the access algorithm accordingly.