How are empty cells stored in a sparse array in JavaScript?

Question

I have a situation where I may be setting an array cell of a high index without setting any of the cells before it.

>>> var arr = [];
undefined
>>> arr[5] = 'value';
"filled"
>>> arr
[undefined, undefined, undefined, undefined, undefined, "filled"]

How is such an array stored in memory? Is there space allocated for each undefined value?

In my actual project, I may be using very large indices. For example, I may set cells 500-800 and 900-1000. I can't use a hash because I need to loop through these non-empty cells and be aware of their index. I want to know if fragmenting the array like this will use up a ton of memory for the empty cells.

I'm not sure I follow, why can't you use `{}`? You can still loop through all properties using a `for (i in obj)` loop. — zzzzBov, Apr 13 '12 at 18:09
Why can't you use a hash table? If you know the largest index, you can still use a `for` loop. Either the element is in the hash table, you retrieve and process it, or it is not and you move on to the next loop iteration. — Eric J., Apr 13 '12 at 18:10
If space was allocated for each value, then `var foo=[]; foo[999999999] = "uh oh";` would cause a large memory allocation. It doesn't, and so it isn't. — Phrogz, Apr 13 '12 at 18:13
possible duplicate of [Are Javascript arrays sparse?](http://stackoverflow.com/questions/1510778/are-javascript-arrays-sparse) — Phrogz, Apr 13 '12 at 18:24
possible duplicate of [If I set only a high index in an array, does it waste memory?](http://stackoverflow.com/questions/4524067/if-i-set-only-a-high-index-in-an-array-does-it-waste-memory) — epascarello, Apr 13 '12 at 19:08

aefxx · Answer 1 · 2012-04-13T18:24:49.217

1

I can't use a hash because I need to loop through these non-empty cells and be aware of their index.

What's wrong with the for (x in ...) language construct?

EDITED to accomodate vol7ron's comment:

var x = {2: "foo", 999: "bar"};

for ( var n in x ) {
    if ( x.hasOwnProperty(n) ) {
        console.log(n);
        console.log(x[n]);
    }
}

edited Apr 13 '12 at 18:24

answered Apr 13 '12 at 18:11

aefxx

24,835
6
45
55

1

a) I suggest that [`hasOwnProperty` is no longer appropriate to use by default](http://phrogz.net/death-to-hasownproperty). b) The problem with this solution is that iterating the keys of an object does not have a guaranteed order, and based on the OP's question it seems probably that JoJo wants/needs to visit them in order. – Phrogz Apr 13 '12 at 18:26
@aefxx: I wasn't aware of the `defineProperty` that Phrogz wrote about, though I'm still not 100% sold on it, since as he said there may be problems in some browsers (for me I take the lowest common denominator approach of the major browsers - since IE7/FF3) – vol7ron Apr 13 '12 at 18:44

vol7ron · Accepted Answer · 2012-04-13T18:45:13.137

1

Strapping onto aefxx's answer, you can still iterate:

var obj = {500: "foo",  10923: "bar"};
var max = 0;

for (var key in obj)
   max=key>max?key:(max||key);         // get max key

for (var i=0; i<=max; i++)
   console.log(obj[i]);                // output even the undefined

As Phrogz commented, it doesn't allocate for undeclared elements of the array. I'm not certain if that's the case if you explicitly set the element value to undefined (e.g. arr[somenum] = undefined;)

edited Apr 13 '12 at 18:45

answered Apr 13 '12 at 18:37

vol7ron

40,809
21
119
172

In order to actually see the log prints past (~500) you'll have to adjust the necessary firebug setting. I think go to `about:config` in the Firefox address bar and set `extensions.firebug.console.logLimit` to at least `10950` (considering the example) – vol7ron Apr 14 '12 at 17:07

score 0 · Answer 3 · answered Apr 13 '12 at 18:13

You should probably simply store the max index in a variable and the access your map like this :

for (var i=0; i<=maxIndex; i++) {
 console.log(myMap[i]);
}

Then you'll have the (relative) compacity of the map and the ability to loop through unsetted indexes.

How are empty cells stored in a sparse array in JavaScript?

3 Answers3