JavaScript associative arrays not ordered?

[Rene Nyffenegger]

Hello everyone.

I am not fluent in JavaScript, so I might overlook the obvious.

But in all other programming languages that I know and that
have associative arrays, or hashes, the elements in the
hash are alphabetically sorted if the key happens to
be alpha numeric. Which I believe makes sense because
it allows for fast lookup of a key.

But in JavaScript, I found this not to be true.

Consider the following function:

function print_assoc_array() {
var assoc_array = new Object();

assoc_array[ "one"] = 1;
assoc_array[ "two"] = 2;
assoc_array["three"] = 3;
assoc_array[ "four"] = 4;
assoc_array[ "five"] = 5;

document.open();
for (i in assoc_array) {
document.writeln(i + " = " + assoc_array + "<br>");
}
document.close();
}

It prints the content of the associative array in insertion
order rather than in alphabetical order (IE6 and FF1.5.0.6).

Am I missing something, or is this expected?


Rene

 

[Lasse Reichstein Nielsen]

I am not fluent in JavaScript, so I might overlook the obvious.

But in all other programming languages that I know and that
have associative arrays, or hashes, the elements in the
hash are alphabetically sorted if the key happens to
be alpha numeric.

Well, you know different languages than me. I'm used to Java's
HashMap, which is not sorted at all.

Which I believe makes sense because it allows for fast lookup of a
key.

Only if you depend on the key being sortable, which is a serious
restriction on what you can use as keys.

Implementing an associative array using sorted keys and binary search
makes it expensive to add elements, and still requires logarithmic
time for lookups. Using a hash based implementation has (amortized)
constant time addition and lookup.

But in JavaScript, I found this not to be true.

Nothing requires it to be true. It could be true in some browsers, but
.....

Consider the following function:

function print_assoc_array() { ....
}

It prints the content of the associative array in insertion
order rather than in alphabetical order (IE6 and FF1.5.0.6).

.... that is the traditional behavior of both IE and Netscape, which
other browsers mimic (Opera once tried to ignore it, since remembering
insertion order adds more work to a hash based implementation, but
users demanded that they mimic IE on this)

Am I missing something, or is this expected?

It's expected from tradition. I would prefer that there was no
expectations on the order, since insertion order is pretty arbitrary,
but I guess I'm too late for changing that when there are pages out
there depending on the current behavior.

/L

 

[Alvaro G. Vicario]

*** Rene Nyffenegger escribió/wrote (Sat, 19 Aug 2006 08:59:49 +0000
(UTC)):

But in all other programming languages that I know and that
have associative arrays, or hashes, the elements in the
hash are alphabetically sorted if the key happens to
be alpha numeric. Which I believe makes sense because
it allows for fast lookup of a key.

The external representation has nothing to do with the internal
implementation. When you make a directory listing and get files sorted by
name, it doesn't mean that files are physically sorted on disk and OS moves
files around the disk every time you create or rename a file.

In all languages I know (not many, I admit), associative arrays
maintain the insertion order. Which makes sense: otherwise, they wouldn't
be so useful as information storage. Sorting is a resource consuming
operation which cannot be undone. Associative arrays were not created for
performance.

Also, in this exact case, you don't really have an array but an "Object".
JavaScript only defines one-dimension numeric arrays; other sort of arrays
must be simulated with objects. And there's no point in sorting object
attributes alphabetically.

 

[Bart Van der Donck]

I am not fluent in JavaScript, so I might overlook the obvious.

But in all other programming languages that I know and that
have associative arrays, or hashes, the elements in the
hash are alphabetically sorted if the key happens to
be alpha numeric. Which I believe makes sense because
it allows for fast lookup of a key.

But in JavaScript, I found this not to be true.

Consider the following function:

function print_assoc_array() {
var assoc_array = new Object();
assoc_array[ "one"] = 1;
assoc_array[ "two"] = 2;
assoc_array["three"] = 3;
assoc_array[ "four"] = 4;
assoc_array[ "five"] = 5;
document.open();
for (i in assoc_array) {
document.writeln(i + " = " + assoc_array + "<br>");
}
document.close();
}

It prints the content of the associative array in insertion
order rather than in alphabetical order (IE6 and FF1.5.0.6).

I don't know if you can alter the input format; but doing

new numero("one", "1")
new numero("two", "2")
new numero("three", "3")

should leave you all possibilities to sort. See example on:
http://groups.google.com/group/comp.lang.javascript/msg/50918860bbb62a84

 

[Richard Cornford]

I am not fluent in JavaScript, so I might overlook
the obvious.

But in all other programming languages that I know
and that have associative arrays,

Javascript does not have "associative arrays".

or hashes,

Or "hashes".

the elements in the hash are alphabetically sorted
if the key happens to be alpha numeric. Which I
believe makes sense because it allows for fast
lookup of a key.

But in JavaScript, I found this not to be true.

Consider the following function:

function print_assoc_array() {
var assoc_array = new Object();

assoc_array[ "one"] = 1;
assoc_array[ "two"] = 2;
assoc_array["three"] = 3;
assoc_array[ "four"] = 4;
assoc_array[ "five"] = 5;

document.open();
for (i in assoc_array) {

The - for-in - statement lists the enumerable properties of an Object
(and its prototype(s)) in an implementation dependent order by
specification (ECMA 262, 3rd Ed. Section 12.6.4). That is, there should
be no expectation of the order.

document.writeln(i + " = " + assoc_array + "<br>");
}
document.close();
}

It prints the content of the associative array

It is not an "associative array" it is a native ECMAScript Object.

in insertion order rather than in alphabetical order
(IE6 and FF1.5.0.6).

Two examples of the same behaviour, where that behaviour is
implementation dependent, are not unexpected but do not guarantee the
same behaviour in other implementations.

Am I missing something,

More likely you are adding something; a miss-association of javascript
Objects with "associative arrays" and "hashes" and so the application to
javascript Objects of assumptions about "associative arrays" and
"hashes", that will be disappointed as javascript objects are no more
than just that.

or is this expected?

Expected in the sense that actual behaviour satisfies the specified
behaviour.

Richard.

 

[Bart Van der Donck]

[...]
Javascript does not have "associative arrays" [...]
Or "hashes".
[...]

"In JavaScript an object is a mapping from property names to values --
that is, an associative array."

http://en.wikipedia.org/wiki/Associative_arrays#JavaScript

 

[Michael Winter]

[...]
Javascript does not have "associative arrays" [...]
Or "hashes".
[...]

"In JavaScript an object is a mapping from property names to values --
that is, an associative array."

http://en.wikipedia.org/wiki/Associative_arrays#JavaScript

Since when has Wikipedia been an authority on the language?

This subject has been covered many times. Search the archives.

Mike

 

[Randy Webb]

Bart Van der Donck said the following on 8/19/2006 8:54 AM:

[...]
Javascript does not have "associative arrays" [...]
Or "hashes".
[...]

"In JavaScript an object is a mapping from property names to values --
that is, an associative array."

http://en.wikipedia.org/wiki/Associative_arrays#JavaScript

Another reason that I do not care for Wikipedia, especially when it is
as wrong as that entry is.

 

[Richard Cornford]

[...]
Javascript does not have "associative arrays" [...]
Or "hashes".
[...]

"In JavaScript an object is a mapping from property names
to values -- that is, an associative array."

http://en.wikipedia.org/wiki/Associative_arrays#JavaScript

If wikipedia wish to define an "associative array" as "a mapping from
property names to values" (or more generally as 'a mapping of keys to
values') then that is their choice. So much of what associative arrays
actually are in practice is disregarded in that definition as to render
it trivial. Under that definition many things become "associative
arrays", some of which would be better never to be thought of as
"associative arrays".

Dictionary definitions of "array" tend to stress ordering in the
arrangement (and we have heard of the expectation of ordering (in some
sense) in "associative arrays" from the OP) yet javascript objects have
no ordering of their properties (except as a coincidental manifestation
of particular object implementations).

When an "associative array" is just created/instantiated in a language
that supports such it would be expected to be empty (or just have the
key/value pairs specified at creation), while the javascript Object is
never 'empty', and so cannot be assumed to not posses a value mapped to
an arbitrary key just because no such key/value pair has been assigned.

Many "associative array" in a language that supports such have some
(recoverable) notion of the number of key/value pairs assigned, while
javascript objects have no interest in the number or properties they
contain.

The practice of talking of either javascript Objects or Arrays as
"associative arrays" tends to introduce in the minds of the readers who
are familiar with actual associative arrays from other languages an set
of expectations that are not true (or not generally true) of javascript
Objects/Arrays. Inevitably false expectations about javascript will not
be satisfied by javascript, will tend to get in the way of an accurate
understanding of javascript, and will directly result in
issues/problems/bugs in code written to those expectations. The most
reasonable response to this situation is to state clearly that
javascript objects are not "associative arrays" and so allow the reader
to move on to the much more productive consideration of what a
javascript Object actually is.

Richard.

 

[Bart Van der Donck]

Since when has Wikipedia been an authority on the language?

Maybe the Netscape javascript manual then ? Quote out of
http://wp.netscape.com/eng/mozilla/3.0/handbook/javascript/model.htm :

-
myCar["make"] = "Ford"
myCar["model"] = "Mustang"
myCar["year"] = 67
This type of array is known as an associative array, because each
index element is also associated with a string value.
-

 

[Bart Van der Donck]

[...]
If wikipedia wish to define an "associative array" as "a mapping from
property names to values" (or more generally as 'a mapping of keys to
values') then that is their choice. So much of what associative arrays
actually are in practice is disregarded in that definition as to render
it trivial. Under that definition many things become "associative
arrays", some of which would be better never to be thought of as
"associative arrays".

Dictionary definitions of "array" tend to stress ordering in the
arrangement (and we have heard of the expectation of ordering (in some
sense) in "associative arrays" from the OP) yet javascript objects have
no ordering of their properties (except as a coincidental manifestation
of particular object implementations).

When an "associative array" is just created/instantiated in a language
that supports such it would be expected to be empty (or just have the
key/value pairs specified at creation), while the javascript Object is
never 'empty', and so cannot be assumed to not posses a value mapped to
an arbitrary key just because no such key/value pair has been assigned.

Many "associative array" in a language that supports such have some
(recoverable) notion of the number of key/value pairs assigned, while
javascript objects have no interest in the number or properties they
contain.

The practice of talking of either javascript Objects or Arrays as
"associative arrays" tends to introduce in the minds of the readers who
are familiar with actual associative arrays from other languages an set
of expectations that are not true (or not generally true) of javascript
Objects/Arrays. Inevitably false expectations about javascript will not
be satisfied by javascript, will tend to get in the way of an accurate
understanding of javascript, and will directly result in
issues/problems/bugs in code written to those expectations. The most
reasonable response to this situation is to state clearly that
javascript objects are not "associative arrays" and so allow the reader
to move on to the much more productive consideration of what a
javascript Object actually is.

You're extremely precise and strictly analytic in describing the
behaviour of "associative arrays" in javascript; but one can also look
at them from a more conceptual point of view.

"associative arrays" have different finetunings in various computer
languages, but that doesn't mean that the overall idea isn't the same.
There are German cars and French cars, but both are cars; though they
might not always work the same. I think this kind of view is the most
honest one; I'm even leaving in the middle whether or not a term
"associative array" is justified in javascript.

But it's pretty safe to assume that the principle of "associative
arrays" is present in javascript, albeit with some (minor)
particularities, which you rightly pointed out.

But almost any language has such specific points:
http://en.wikipedia.org/wiki/Associative_arrays#Language_support
And that doesn't mean that the principle of "associative arrays" isn't
the same across those languages. If declaration, assignment, key/value,
representation, syntactical appearance, look-up methodology and general
working of such variables all correspond to the computer-scientific
idea of "associative arrays", then I would vote to name them as such in
javascript too.

 

[Douglas Crockford]

I am not fluent in JavaScript, so I might overlook the obvious.

That right there is the source of a lot of misunderstanding about JavaScript. It
is different from other languages in some profound ways. If you insist on
thinking about it as though it were a different language, you will not use it
correctly.

There is no substitute for knowing what you are doing.

But in all other programming languages that I know and that
have associative arrays, or hashes, the elements in the
hash are alphabetically sorted if the key happens to
be alpha numeric. Which I believe makes sense because
it allows for fast lookup of a key.

It depends on the underlying data structure. Something like a B-tree sorts.
Something like a hashtable, which has faster retrieval characteristics, does
not. The ECMAScript standard does not dictate the underlying data structure.

But in JavaScript, I found this not to be true.

Consider the following function:

function print_object() {
var i, o = {};

o[ "one"] = 1;
o[ "two"] = 2;
o["three"] = 3;
o[ "four"] = 4;
o[ "five"] = 5;
document.writeln('<pre>');
for (i in o) {
document.writeln(i + " = " + o);
}
document.writeln('<\/pre>');
}

It prints the content of the associative array in insertion
order rather than in alphabetical order (IE6 and FF1.5.0.6).

Am I missing something, or is this expected?

Most implementations of ECMAScript tend to return items in insertion order. The
standard does not guarantee /any/ particular order. You should not assume any.

http://javascript.crockford.com/

 

[Michael Winter]

Michael Winter wrote:
[snip]

Since when has Wikipedia been an authority on the language?

Maybe the Netscape javascript manual then ?

That still wouldn't automatically eliminate the misuse of terminology.

myCar["make"] = "Ford"
myCar["model"] = "Mustang"
myCar["year"] = 67
This type of array is known as an associative array, because each
index element is also associated with a string value.

That's a worse description: myCar need not be an array (none of this has
/anything/ to do with arrays), and, in reference to "index element",
those strings are not indices; they are property names.

Again, I ask you to read the archives. Unless you have something new to
add, there's no point repeating this debate. I can't say that I'd look
forward to a ninth discussion of this subject.

Mike

 

[Richard Cornford]

[...]
If wikipedia wish to define an "associative array" as "a mapping from
property names to values" (or more generally as 'a mapping of keys to
values') then that is their choice. So much of what associative
arrays actually are in practice is disregarded in that definition as
to render it trivial. Under that definition many things become
"associative arrays", some of which would be better never to be
thought of as "associative arrays".

Dictionary definitions of "array" tend to stress ordering in the
arrangement (and we have heard of the expectation of ordering (in
some sense) in "associative arrays" from the OP) yet javascript
objects have no ordering of their properties (except as a
coincidental manifestation of particular object implementations).

When an "associative array" is just created/instantiated in a
language that supports such it would be expected to be empty (or
just have the key/value pairs specified at creation), while the
javascript Object is never 'empty', and so cannot be assumed to not
posses a value mapped to an arbitrary key just because no such
key/value pair has been assigned.

Many "associative array" in a language that supports such have some
(recoverable) notion of the number of key/value pairs assigned, while
javascript objects have no interest in the number or properties they
contain.

The practice of talking of either javascript Objects or Arrays as
"associative arrays" tends to introduce in the minds of the readers
who are familiar with actual associative arrays from other languages
an set of expectations that are not true (or not generally true) of
javascript Objects/Arrays. Inevitably false expectations about
javascript will not be satisfied by javascript, will tend to get in
the way of an accurate understanding of javascript, and will
directly result in issues/problems/bugs in code written to those
expectations. The most reasonable response to this situation is to
state clearly that javascript objects are not "associative arrays"
and so allow the reader to move on to the much more productive
consideration of what a javascript Object actually is.

You're extremely precise and strictly analytic in describing
the behaviour of "associative arrays" in javascript;

If you cannot be precise about a programming language what could you be
precise about?

but one can also look
at them from a more conceptual point of view.

And you can also look at them from a more miss-conceptual point of view.

"associative arrays" have different finetunings in various
computer languages, but that doesn't mean that the overall
idea isn't the same.

Which overall idea?

There are German cars and French cars, but both are cars;
though they might not always work the same. I think this
kind of view is the most honest one; I'm even leaving in
the middle whether or not a term "associative array" is
justified in javascript.

The term is directly harmful when associated with javascript's native
Objects/Arrays.

But it's pretty safe to assume that the principle of
"associative arrays" is present in javascript,

This is a 'principle of associative arrays"' in which it is not possible
to use arbitrary string keys to store values within an associative
array, not possible to use arbitrary string keys to retrieve a stored
value (as a consequence of not being able to store values under all
possible keys) and from which arbitrary string keys cannot necessarily
be removed?

albeit with some (minor) particularities,
which you rightly pointed out.

I did not point out any minor particulars, I listed the things that make
applying any concept of "associate arrays" acquired in any other
language to javascript's Objects a disappointing and unsuccessful
exercise.

But almost any language has such specific points:
http://en.wikipedia.org/ ...

Wikipedia again? Weren't they the ones that defined an associative array
as "a mapping from property names to values"? (That is actually a
description of nearly every object in any OO language).

And that doesn't mean that the principle of "associative
arrays" isn't the same across those languages.

State a definition of "associative array" that includes the things that
are associative arrays and precludes the things that are not and, if it
is successful/acceptable, we can see if the javascript Object qualifies
or not.

If declaration, assignment, key/value, representation,
syntactical appearance, look-up methodology and general
working of such variables all correspond to the
computer-scientific idea of "associative arrays", then I
would vote to name them as such in javascript too.

So would I, but javascript Objects don't so it is better to tell it like
it is.

Javascript objects are not a safe storage medium for arbitrary key/value
pairs and should not be treated as if they are. If such an object is
wanted it should be (and certainly can be) implemented with javascript.

Richard.

 

[Matt Kruse]

Javascript objects are not a safe storage medium for arbitrary
key/value pairs and should not be treated as if they are.

That's a bit of an exaggeration, isn't it?

Using an Object() to store key/value pairs is just fine as long as you don't
extend the Object prototype, don't expect keys back in any certain order,
etc.

 

[Richard Cornford]

That's a bit of an exaggeration, isn't it?

No, it is a statement of fact.

Using an Object() to store key/value pairs is just fine
as long as you don't extend the Object prototype, don't
expect keys back in any certain order, etc.

The 'etc' includes; don't expect to be able to safely store and retrieve
values using _arbitrary_ property names.

Richard.

 

[Lasse Reichstein Nielsen]

(and nobody else extends Object.prototype either)

The 'etc' includes; don't expect to be able to safely store and retrieve
values using _arbitrary_ property names.

The problem isn't storing a property and retrieving it again, which
works for all property names, it's recognizing what has been stored
without knowing the property names already.

Correct ECMAScript implementations gives you a "hasOwnProperty" that
can distinguish properties set on the object from those inherited from
its prototypes (but you would obviously have to call it indirectly,
like "Object.prototype.hasOwnProperty.call(myObject, propName)" as
it too could have been overridden on myObject).

That is the kind of loops you have to jump through to be able to
ignore inherited properties.

/L

 

[Richard Cornford]

(and nobody else extends Object.prototype either)



The problem isn't storing a property and retrieving it again,
which works for all property names, it's recognizing what has
been stored without knowing the property names already.

The inability to safely use arbitrary keys as property names may not be
the problem but it certainly is a problem. Consider the following in a
JavaScript(tm) implementation:-

<html>
<head>
<title></title>
</head>
<body>
<script type="text/javascript">
var o = {};

document.write(o.hasOwnProperty('_parent__')+'<br><br>');
// writes - false - in JavaScript(tm)

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

o._parent__ = 'test 1'

document.write(o.hasOwnProperty('_parent__')+'<br><br>');
// writes - true - in JavaScript(tm)

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

delete o.__parent__;

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

document.write(o.hasOwnProperty('_parent__')+'<br><br>');
// writes - true - in JavaScript(tm)

document.write('----------------------'+'<br><br>');

o = {
'_parent__':'test 2'
};
document.write(o.hasOwnProperty('_parent__')+'<br><br>');
// writes - true - in JavaScript(tm)

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

o._parent__ = 'test 3'

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

delete o.__parent__;

document.write(o.__parent__+'<br><br>');
// writes - [object Window] - in JavaScript(tm)

document.write(o.hasOwnProperty('_parent__'));
// writes - true - in JavaScript(tm)

</script>
</body>
</html>

- The extension(s) to the Object in JavaScript(tm) are legal, and the
extended properties are allowed to be - DontDelete - and - ReadOnly -
(even this strange form where assignment to the object moves the -
ReadOnly - value from the prototype to the object itself but makes the
new property of the object - DontDelete -).

So you cannot define, assign or retrieve values from Objects using
string keys safely unless you know enough about those string keys to be
pretty certain that they will never coincide with language extension
properties. That is; any keys used in this way must not be truly
arbitrary.

I think that the ability to use arbitrary keys is fairly fundamental to
what an "associative array" is, and so the javascript Object does not
qualify.

Correct ECMAScript implementations gives you a "hasOwnProperty"
that can distinguish properties set on the object from those
inherited from its prototypes (but you would obviously have to
call it indirectly, like
"Object.prototype.hasOwnProperty.call(myObject, propName)"
as it too could have been overridden on myObject).

That is the kind of loops you have to jump through to be able
to ignore inherited properties.

And in reality 90% of the time it is not an issue. For example, some of
the web service responses that the code I am working on at the moment
include sequences of name/value pairs. I have absolutely no qualms about
transferring those names to properties of javascript objects and the
values to their values, because those names are _required_ to satisfy a
format of uppercase alphabetical characters and (non-leading)
underscores only.

In other places values come in and I still want to use them as keys, but
not having certainty about what the character sequences represent I
store them in a (Java-style) 'HashTable' implementation.

It is knowing what the javascript object actually is that allows
informed decisions to be made about which hoops need to be jumped
through, and when.

Richard.

 

[Dr John Stockton]

JRS: In article <[email protected]>, dated Sat, 19
Aug 2006 11:07:06 remote, seen in Richard

The - for-in - statement lists the enumerable properties of an Object
(and its prototype(s)) in an implementation dependent order by
specification (ECMA 262, 3rd Ed. Section 12.6.4). That is, there should
be no expectation of the order.

ECMA there clearly implies that there is an order, by saying "next
property"; and it rather strongly suggests that the order does not
change if the Object is not changed.

Thus if an Object is enumerated twice without being changed in between,
the properties should be given in the same order; and in particular the
order is not randomly chosen during each enumeration. Which is only
reasonable.

Perhaps ECMA 4 will be more explicit - anyone here writing it?

 

[Laurent Bugnion]

Hi,

Well, you know different languages than me. I'm used to Java's
HashMap, which is not sorted at all.

C#'s Hashtables are also not sorted. If you do a "foreach" on a
Hashtable, it's impossible to predict in what order they will appear.

HTH,
Laurent