How do arrays in JavaScript work ? (ie without a starting dimension size)

Question

I was reading this post the other night about the inner workings of the Array, and learned a lot from the answers posted, especially from Jonathan Holland's one.

So the reason you give a size to an array beforehand is so that space will need to be reserved beforehand, so that elements in the array will be placed next each other in memory, and thus providing O(1) access time, because of the pointer + offset traversal.

---

But in JavaScript, you can initialize an array like such:

var anArray = []; //Initialize an empty array, without a dimension

So my question is, since in JavaScript you can initialize an array Without specifying a dimension before hand, how is memory allocated for an array to still provide a O(1) access time since the 'amount' of memory locations is not specified beforehand ?

Answer 1

Arrays in Javascript are "fake". They are implemented as hash maps. So in the worst case their access time is not O(1). They also need more memory and you can use any string as an array index. You think that's weird? It is.

Answer 2

I was interested in the answer to this, so did a little googling and found this.

Answer 3

It is the same in PHP. I came from a PHP/Javascript background and dimensionalizing arrays really got me when i moved onto other languages.

Answer 4

javascript has no real arrays. Elements are allocated as you define them.

It is a flexible tool. You can use the for many purposes but as a general purpose tool is not as efficient as special purpose arrays.

Answer 5

Hmm. You should distinguish between arrays and associative arrays.

arrays:

A=[0,1,4,9,16];

associative arrays:

B={a:'ha',b:27,c:30};

The former has a length, the latter does not. When I run this in a javascript shell, I get:

js>A=[0,1,4,9,16];
0,1,4,9,16
js>A instanceof Array
true
js>A.length
5
js>B={a:'ha',b:27,c:30};
[object Object]
js>B instanceof Array
false
js>B.length
js>

How arrays "work" in Javascript is implementation-dependent. (Firefox and Microsoft and Opera and Google Chrome would all use different methods) My guess is they (arrays, not associative arrays) use something like STL's std::vector. Your question:

how is memory allocated for an array to still provide a O(1) access time since the 'amount' of memory locations is not specified beforehand ?

is more along the lines of how std::vector (or similar resizable arrays) works. It reallocates to a larger array as necessary. Insertions at the end take amortized O(1) time, namely if you insert N elements where N is large, the total time takes N*O(1). Those individual inserts where it does have to resize the array may take longer, but on the average it takes O(1).

Answer 6

As Jason said, unless it is explicitly specified by the ECMAScript standard (unlikely), it is implementation dependent. The article shown by Feet shows that IE's implementation was poor (until IE8?), which is confirmed by JavaScript loop performance.

Other JS engines probably takes a more pragmatic approach. For example, they can do like in Lua, having a true array part and an associative array part: if the array is dense, it lives in the true array (which can still be extended at the cost of re-allocation), and you can still have sparse high indices living in the associative part.

Thus you have the best of two worlds, speed of access to dense parts and low memory use for sparse parts.

Answer 7

As I understand, it's like this:

There are two different things in JavaScript: Arrays and Objects. They both act as hashtables, although the underlying implementation is specific to each runtime. The difference between the two is that an Array has an implicit length property, while an object does not. Otherwise you can use [] or . syntaxes for both of them. Yes, that means that objects can have numerical properties and arrays have string indices. No problem. Although the length property might not be what you expect when using such tricks or sparse arrays. You should rely on it only if the array is not sparse and indices start from 0.

As for the performance - sorry, it's not the O(1) you'd expect. As stated before - it's actually implementation specific. But in general case it's not possible to ensure that there will be O(1) performance for all operations in a hashtable. That said, I'd expect that decent implementations should have quite a few optimizations in place for standard cases, which would make the performance quite close to O(1) under most scenarios. But at any rate - storing huge volumes of data in JavaScript is not a wise idea.