6

For instance, if I do a[1000000]=1; will it use memory for 1000000 elements or just for this one?

Lem0n
  • 77
  • 1
  • Related: http://stackoverflow.com/questions/1076658/javascript-array-associative-and-indexed – Pindatjuh Apr 04 '10 at 20:50
  • 4
    It seems you are asking two quite different questions here: Whether they are associative (in the title) and whether they are sparse (in the text). In fact, these two facets of JS arrays are orthogonal (i.e. the sparseness has nothing to do with associativity). – Tomalak Apr 04 '10 at 21:14
  • 1
    See also: http://stackoverflow.com/questions/2039908/does-javascript-populate-empty-array-items/ – Christian C. Salvadó Apr 04 '10 at 21:36

4 Answers4

8

In the ECMAScript standard (§15.4), the only special thing about array is that the length property is automatically updated (and a bunch of Array-specific prototype functions):

Array objects give special treatment to a certain class of property names. A property name P (in the form of a String value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1.
...
Every Array object has a length property whose value is always a nonnegative integer less than 232. The value of the length property is numerically greater than the name of every property whose name is an array index; ...

Other than that, an Array is just an Object, which means it can be treated as an associative array, although you shouldn't.

Nowadays the JS engines should detect whether the array is dense or very sparse and switch between using a linear or associative array internally. In your case, the JS engine won't allocate a million elements.

kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
7

Would 1,000,000 elements be created?

No, arrays are sparse, but their index will be persistent. EDIT: Actually, their sparseness would be implementation-specific, but keeping them sparse in case of a[1000000] = 1 would seem a logical thing to me.

var a = [1, 2, 3, 4];
var x = a[1]; // -> x := 2

delete a[1];
var y = a[1]; // -> y := undefined

a[9] = 10;
var y = a[8]; // -> z := undefined

Are JS arrays associative?

JavaScript arrays are a subset of associative arrays (in that indices have to be integers, as shown in KennyTM's answer. JavaScript objects are fully associative:

var o = { "key1": "value1", "key2": "value2" };
var i = "key2";
var v = o[i]; // -> v := "value2"
Community
  • 1
  • 1
Tomalak
  • 332,285
  • 67
  • 532
  • 628
  • 1
    Whether they're sparse or not would likely depend on the implementation. I would dare to guess that the undefined values the values inbetween get initialized to do take memory on current implementations. – Matti Virkkunen Apr 04 '10 at 20:54
  • I would have expected them to be sparse to save memory and time in the `var a[1000000] = x` situation. But this is very likely implementation-specific, I agree. Initializing a million `undefined` values seems like a waste of resources. – Tomalak Apr 04 '10 at 20:58
  • Implementing them as sparse arrays would make the common case (not having thousands of undefined values) needlessly inefficient. – Matti Virkkunen Apr 04 '10 at 21:00
  • @Matti: I would be interested in a definition/spec that clarifies this point. Thinking about it, one *could* interpret the fixed index->value connection as associativity. – Tomalak Apr 04 '10 at 21:18
  • @Matti: Oh, and while we are at it: IMHO, the "common case" is a) declaring an array by literal or b) incrementally appending to it in a loop. Either way - where would sparseness imply inefficiency here? – Tomalak Apr 04 '10 at 21:26
  • 4
    Arrays are Objects with string-numeric keys. Like all Object, they *are* associative. Browsers usually *also* provide an optimisation for numeric keys in an Array, but that's an internal implementation matter, not part of the language. – bobince Apr 04 '10 at 21:42
  • @bobince: Thanks for the clarification. This makes a lot of sense. – Tomalak Apr 04 '10 at 21:47
  • 1
    An Array's length property and member functions ignore any properties of the array aside from its integer-indexed elements. If you were to add [0], [1], and ["str"] indexes to an Array, the length would be 2 (indexes 0 and 1), and copying the array via `slice()` would give you an Array without the "str" property that you added to the original. If you need an associative array in Javascript, you should use an Object. There's no benefit to using Array instead, or of thinking of it as an associative array just because it appears to work as one superficially. – Josh Townzen Apr 04 '10 at 21:59
  • It would seem I have failed at remembering the spec. Please excuse my stupidity. – Matti Virkkunen Apr 04 '10 at 22:31
1

You may use object literal as a kind of 'associative aray' in some cases:

var object = {
  "first": "1",
  "second": "2",
  "third": "3",
  "fourth": "4"
};
object.fifth = "5";
object.["sixth"] = "6";

But it has its limitations... There is no magic 'length' parameter and you will not have access to methods that every array has.

smentek
  • 2,820
  • 1
  • 28
  • 32
0

JS arrays are auto-growing. Setting a[100] to 1 on an empty array will populate the first 99 elements with "undefined".

Tin
  • 9,082
  • 2
  • 34
  • 32
  • 4
    Actually nothing gets *populated*. That's why it won't be just the first elements that'll *be undefined* (as opposed to *populated with undefined*) but all elements (except `a[100]`) will be `undefined`. – Miguel Ventura Apr 04 '10 at 20:56
  • 4
    To demonstrate the difference: `a[1]=undefined`. Now `a.length===2` and `a['0']===undefined` and `a[1]===undefined`, *but* whilst `'1' in a` is `true`, `'0' in a` is `false`. – bobince Apr 04 '10 at 21:38