How do arrays work "under the hood"?

Question

In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next dataTypeSize * arrayLength bytes as reserved. Retrieving items just means looking at the memory address startPoint + (index * dataTypeSize).

But in other languages (such as JavaScript and ActionScript), there is no requirement to make them fixed when creating the array. In fact, most often in actual use, an empty array is created, then new items are one by one appended to the array in a for loop.

How is the memory managed when you could at any time append add an item to the end, or prepend an item to the beginning? Do you need to redefine space in memory every time the size changes?

Answer 1

There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points:

1. Arrays can be implemented simply as associative arrays (also known as hash tables or, in python, dictionaries). This is appropriate if the array is sparse (contains only few non-zero values).

2. Arrays can be implemented as dynamically sized arrays, which are appropriate for the dense case. These are stored as classical C/Fortran arrays with a certain "extent". Once their length exceeds their extent, they are extended (say by doubling the extent) by allocating a new array the size of the new extent, copying the old values to the new array, freeing the old array, and changing the appropriate pointer to reflect the new location in memory. Arrays can potentially shrink as well according to a similar scheme.

Associative arrays are also dynamically sized, so in any case the second paradigm is being used.

Since the extent of the arrays increases exponentially, the average overhead is bearable, though once in a while, an operation may take a long time to perform (due to an array being resized). So such arrays are not a good choice for real-time systems.