16

The explanation for a dense array that I read from a few pages seem to be in contradiction to one another. I'd like some help understanding what it is.

While some links (search result 1, search result 2) suggest that it simply is an array where:

  1. the elements of the array are known to be specific values; and
  2. are assigned to the array at the time of its initialization.

The allusion there is that JavaScript arrays are dense.

It all makes sense up until here.

But this statement taken from the JavaScript Guide on the Mozilla Developer Network (MDN) says:

Since an array's length can change at any time, and data can be stored at non-contiguous locations in the array, JavaScript arrays are not guaranteed to be dense; this depends on how the programmer chooses to use them. In general, these are convenient characteristics; but if these features are not desirable for your particular use, you might consider using typed arrays.

And this has confused me now. My question is:

What does the statement on the MDN page mean when it says JavaScript arrays are not guaranteed to be dense? If it means that the following is not a dense array because one or more of its elements are undefined at the time of initialization, then why do the links I listed above seem to indicate that JavaScript arrays are indeed dense?

var array = new Array(1, , 3, ); // [1, undefined, 3, undefined]
Water Cooler v2
  • 32,724
  • 54
  • 166
  • 336
  • 3
    How the array was initialised is irrelevant, it is the state of the array *right now* that matters. Whether or not a given array is dense is something that can change over the life of the array: `var arr = [1,2,3,4]` creates a dense array, but if you then go on to say `arr[20] = 20` now you have a sparse array. – nnnnnn Aug 19 '16 at 02:31
  • @nnnnnn Thanks, I get it. Dense being a metaphor for every element has a value and therefore takes memory. – Water Cooler v2 Aug 19 '16 at 02:43
  • This is invalid syntax, by the way: `new Array(1, , 3, )`. You may be confusing it with `[1, , 3,]`. –  Aug 19 '16 at 03:23
  • @torazaburo Yes, sorry about that. – Water Cooler v2 Aug 19 '16 at 04:55

2 Answers2

21

"Dense" is in opposition to "sparse", and generally is used when talking about storage. For example, this array is dense:

a = [undefined, undefined, 2]

It can be stored in memory exactly like that: a sequence of three locations, the first two being undefined, the third being 2.

This array is sparse:

a = []
a[100000000] = 100000000

It is not stored in memory as a sequence of 100000001 locations, as it would be horribly inefficient. It is definitely not 100000000 places of undefined followed by 100000000. Rather, it just says 100000000th one is 100000000, and there is no space allocated to the first 100000000 elements.

(Actually, try to do this with 2 instead of 100000000, and you'll notice a curious thing: Chrome will display the dense array as [undefined, undefined, 2], but the sparse one as [undefined × 2, 2].)

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • 3
    I don't know if horribly inefficient is correct, I think maintainers of Underscore.js have argued over this very point, resulting in the fork of Underscore which became known as Lodash. – vol7ron Aug 19 '16 at 02:35
  • Further to your point about how Chrome displays the arrays in the console, it will say `undefined x 1` rather than `undefined` if there is a 1 missing element as compared to an element with the value `undefined`, so you can always tell what's what... – nnnnnn Aug 19 '16 at 02:38
  • 2
    I'd say you can't really argue about it: allocating 100000000 memory locations to store one value is inefficient. It was not a general statement ("dense arrays are inefficient"), but one specific to this scenario. – Amadan Aug 19 '16 at 02:38
  • Just one moot point though at the core of the issue: is an `undefined` element allocated memory? If not, then the declaration `var array = new Array(1, , 3, )` isn't dense? – Water Cooler v2 Aug 19 '16 at 02:42
  • `new Array(1, , 3, )` is AFAIK invalid JavaScript; `[1,,3,]` is valid. `undefined` can be a gap (in case of sparse arrays) or a proper element. The way to tell is this: given `a = [undefined,,2]`, `0 in a` is `true`, signifying a proper `undefined` value; `1 in a` is `false`, telling you there's a gap. – Amadan Aug 19 '16 at 02:48
  • @Amadan: Thank you. It's weird though, of JavaScript, that `undefined` should evaluate to different values in different circumstances. Also, I see it evaluates to true if I manually assign it the value `undefined` like so: `a[9] = undefined; console.log(9 in a); // true` – Water Cooler v2 Aug 19 '16 at 03:03
  • It doesn't evaluate to different values. Every `undefined` you write in your code is exactly the same thing (the real `undefined` value). However, the console *output* is ambiguous between a gap and a real `undefined`. – Amadan Aug 19 '16 at 03:08
  • 1
    Nowadays chrome is displaying the sparse array as `[empty × 2, 2]` – Albizia Nov 20 '20 at 11:19
5

Those articles say you can create an array being dense. This means that, at the time of creation, such arrays are dense, since in arrays like:

var a = new Array("foo", "bar", "baz");
var b = [2, 3, 5];

every element is set: from 0 to length-1, there is no undefined value. Or better said: every position from 0 to length-1 was assigned a value (even if the value is, actually, undefined).

However, you can make those arrays not dense anymore, by doing something like this:

a[20] = "bat";

That array, which was dense, is not dense anymore since the elements 0 1 2 and 20 (unlike elements in 3 to 19) are set to a value (this array has 4 elements, not 21).

Luis Masuelli
  • 12,079
  • 10
  • 49
  • 87