15

What's the big O for JavaScript's array access when used as a hash?

For example,

var x= [];
for(var i=0; i<100000; i++){
   x[i.toString()+'a'] = 123; // using string to illustrate x[alpha]
}
alert(x['9999a']); // linear search?

One can hope JS engines will not use a linear search internally O(n), but is this for sure?

Eric Leschinski
  • 146,994
  • 96
  • 417
  • 335
Alex Nolasco
  • 18,750
  • 9
  • 86
  • 81
  • 4
    Nothing is "for sure" (unless, as with C++, the standard defines the performance characteristics of containers?) but I can guarantee that no browser uses a linear search. There is massive competition for browsers to out-do each other in JS benchmarks these days; you can rest assured that indexing an array will be as fast as the browser manufacturer can make it. – user229044 Oct 04 '10 at 19:45

2 Answers2

13

Accessing object properties and array elements in JavaScript is syntacticly assumed to be done in constant time: O(1). Performance characteristics are not guaranteed in the ECMAScript specification, but all the modern JavaScript engines retrieve object properties in constant time.

Here's a simple example showing how access times grow when the container is x1000 times bigger:

var largeObject = {};
var smallObject = {};

var x, i;

for (i = 0; i < 1000000; i++) {
   largeObject['a' + i] = i;
}

for (i = 0; i < 1000; i++) {
   smallObject['b' + i] = i;
}

console.time('10k Accesses from largeObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)];
console.timeEnd('10k Accesses from largeObject');

console.time('10k Accesses from smallObject');
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)];
console.timeEnd('10k Accesses from smallObject');

Results in Firebug, Firefox 3.6.10 (Mac OS X 10.6.4 - 2.93Ghz Intel Core 2 Duo):

10k Accesses from largeObject: 22ms
10k Accesses from smallObject: 19ms

Results in Chrome Dev Tools 6.0.472:

10k Accesses from largeObject: 15ms
10k Accesses from smallObject: 15ms

Internet Explorer 8.0.7600 with Firebug Lite on Windows 7

10k Accesses from largeObject: 250ms
10k Accesses from smallObject: 219ms
Daniel Vassallo
  • 337,827
  • 72
  • 505
  • 443
  • 2
    Can you point to the paragraph in the ECMAScript or JavaScript specifications which says that accessing array elements or object properties is guaranteed to be O(1)? AFAIK, JScript has a perfectly standards-compliant O(n) implementation of objects as simple linked lists. – Jörg W Mittag Oct 05 '10 at 00:29
  • 1
    @Jörg: It's not mentioned in the spec, so in practice it is implementation dependent... That's why I chose to say that it is "syntactically assumed". Nevertheless, I rephrased my answer to be more accurate. – Daniel Vassallo Oct 05 '10 at 08:54
  • 1
    @Chaos: At least they aren't implementing object properties as a linked list. – Daniel Vassallo Oct 05 '10 at 13:59
  • 2
    The O(1) is average-case. Worst-case for a hash table is O(n). – Daniel Stutzbach Oct 08 '10 at 15:02
  • I run the code on Node. V8 does grate job. Thanks for the post. 10k Accesses from largeObject: 7ms 10k Accesses from smallObject: 6ms – Narek Tootikian Feb 05 '18 at 07:29
8

First and foremost Arrays are in fact hashes. Always. That's why x[5] === x["5"]:

var x = [];
x[5] = 10;
alert( x[5] === x["5"] ); // true

Objects are hashes and Arrays are just special objects. If you want to use general hashes go for Objects. "Associative arrays" in Javascript are Objects. Arrays are for numerically indexed data. Arrays have a length property and Array-like methods like push, pop, sort, etc. which makes no sense to be used on hashes.

As for the big O for searching in Objects: it's implementation dependent.

Probably the 2 best things you can do to:

  1. Check the source code of some browser implementations

  2. Do some benchmark for big n and make your conclusion

The related part of the language specification:

4.3.3 object

An object is a collection of properties and has a single prototype object.

8.6.2 Object Internal Properties and Methods

Array objects have a slightly different implementation of the [[DefineOwnProperty]] internal method. Array objects give special treatment to a certain class of property names.

gblazex
  • 49,155
  • 12
  • 98
  • 91
  • 1
    Arrays are not hashes. The value in `x["5"]` is cast into `number` before the lookup. That is why you get the same result for `x[5]` as well. However, `Array` does have `Object` in its prototype chain, thus it is not a type in JavaScript and `typeof === "object"`. It casts similar to `~~"5"` and if it equals 0, then the array is left untouched like in case of, say, `x["a5"]`. – Tower Jun 21 '11 at 13:01
  • I for one gave my references (the **language specification** for that matter), what can you show as the base for your completely subjective and **false theories**? This is where the problem used to start. – gblazex Jun 21 '11 at 22:28
  • 1
    (http://es5.github.com/#x15.4) `1.)` Arrays are hashes, *"15.4 **Array Objects**: Array objects give special treatment to a certain class of **property names**."* `2.)` Property names (even array indexes) are treated as strings: *"A property name P (in the form of a **String value**) is an **array index** if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1."* `3.)` It casts nothing like `~~` because it's a double bitwise operator which you've picked up from some kind of byte-shaving optimization article, and is nowhere near the specification. – gblazex Jun 21 '11 at 22:43
  • It casts exactly as quoted above: `if ToString(ToUint32(P)) equals P`, where P is the property name. – gblazex Jun 21 '11 at 22:51
  • `4.)` `x["a5"]` as part of a left hand side assignment won't leave the array untuched for sure. This is where you should've realized your whole misconception. If you had actually taken the time to test a single line of code. `x=[]; x["a5"] = 7; alert(x["a5"])` – gblazex Jun 21 '11 at 22:53
  • It seems I'm partly wrong. `x["a5"] = 7` definitely does not leave the Array object untouched, it only looked like so with quick tests on Webkit Inspector which does not report Array named properties. However, arrays are still not hashes. They are objects, but not hashes. Hash objects != hash arrays. Well, I guess it depends on your definition. – Tower Jun 23 '11 at 19:21
  • ToUint32(P) casts like ~~P. I never said that any implementation source code contains double NOTs, but that they work the same way machine wise. It was the shortest and simplest example. – Tower Jun 23 '11 at 19:35
  • 3
    No, they are hashes because they treat properties as strings (as you can read in the quoted spec). I'm not going to write it down again. It's all there. You just need to read it, and read it carefully. – gblazex Jun 23 '11 at 23:34