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

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).