Array and Hash in JavaScript : materials for FAQ : v2

A while ago I proposed to update info in the group FAQ section, but I
dropped the discussion using the approach "No matter what color the cat
is as long as it still hounts the mice". Over the last month I had
enough of extra proof that the cat doesn't hount mice anymore in more
and more situations. And the surrent sicretisme among array and hash is
the base for it.

I summarized all points in this article:
<http://www.geocities.com/schools_ring/ArrayAndHash.html>

I invite all members of the previous discussion, as well as anyone
interested in Array vs Hash mechanics in JavaScript to read this
article and to express your opinion (if any).

As each point in the article is illustrated by a concrete code sample,
I expect do not see any abstract considerations/injurations. But of
course factual mistakes illustrated by contre-samples should be edited
immediately.

re: Array and Hash in JavaScript : materials for FAQ : v2

"VK" <schools_ring@yahoo.com> writes:
[color=blue]
> I summarized all points in this article:
> <http://www.geocities.com/schools_ring/ArrayAndHash.html>
>
> I invite all members of the previous discussion, as well as anyone
> interested in Array vs Hash mechanics in JavaScript to read this
> article and to express your opinion (if any).[/color]

Comment: "You can use a notation like arrayObject[-1] top address the
last element in the array". Nope, doesn't work. It merely tries to
access the property named "-1", which doesn't exist unless you created
it.


Re. "multidimensional arrays". Javascript doesn't have mutidimensional
arrays in the sense of C, b ut only arrays of arrays. In C you wouldn't
be able to change a sub-array like:
int arr[4][4];
arr[3] = new int[4];

"The actual amount of possible indexes (dimensions) is platform
dependent, but always very big, so you should not worry about it."
It's not really platform dependent either, just limited by available
memory. Or, for a seemingly infinite-dimension array:
var x = []
x[0] = x;


You need to define what you mean by "element" of an array. You use it
in the sense "what you get when indexing with an integer less than the
array's length". That makes "new Array(10)" have ten elements, all
undefined. Other people (myself included) uses "element" to mean
an actual property of the array object, so "new Array(10)" has no
elements. This is a more usual meaning for *sparse* arrays, where
not all indices correspond to an "element".

You sortof say it in the section following this:
" Nevertheless it is important to understand the difference of (1)
undefined value received from a non-instantiated element within your
array and (2) undefined value received when addressing an element with
index bigger than length-1."

I think that's a dangerous way to make the point. There is no
difference between the "undefined" values you get, nor between the
underlying functionality that gives you that "undefined". What you
are trying to say is that:
Arrays in Javascript are an abstraction on top of normal object
properties. For property names that are (bounded) integers, it
works as if the array was a contiguous sequence of values, some
of them "undefined", indxed from 0 to one less than the arrays
"length" property's value.
Arrays are *implemented* as sparse arrays. Only the indices that have
been assigned to, take up space, and the "length" property only
guarantees to be larger than the largest index in use.
The methods operating on arrays respect the abstraction and all treat
the array as a contiguous sequence of, potentially "udefined" values.
[[ your example with "slice" ]].


Make no mistake, at the specification level, there is a difference
between being unassigned and having been assigned the value
"undefined". Example:

var arr = [1,,undefined,true];
arr[2]=undefined; // for IE's bug (2 in arr == false)
delete arr[1]; // for Firefox's bug (1 in arr == true)
alert([arr.length, 1 in arr, 2 in arr]); // 4,false,true
arr = arr.sort();
alert([arr.length, 2 in arr, 3 in arr]); // 4,true,false

I.e., unassigned indices are sorted as larger than those assigned
"undefined". (Not all implementationts are correct, e.g., Firefox
gives 4,true,true for the last one).


"On Macintosh platform an attempt to use a number for hash key leads
to an error. As a workaround, if you really need to have a number as
hash key (?), always put it into quotes."

Are you talking about Javascript objects here? It's not obvious.
Also, "Macintosh platform" is far from an exact specification of
the Javascript implementation that fails. It could be the one in
IE5.2, in Safari, in Galleon, in OmniWeb, ...

"JavaScript doesn't have a built-in constructor for hash objects. But
each object supports hash table mechanics inherited from the Object
prototype."
It's not Object.prototype that have string based properties, it's
just objects themselves. If you find a way to create an object without
inheriting Object.prototype, you can still add properties to it.

"Unfortunately interpreter doesn't resolve variables in such
declarations. Everything (quoted or not quoted) will be treated as
string literals."
Not so. It's variables in the keys that doesn't work, the values
work fine:
var x = 42;
var h = {foo: x, x:x, "y":x, "Lorem ipsum, lala": x, "":x};


There is no guarantee that implementations have efficient property
look-up. It seems like IE have linear time look-up of properties.


What is an "out of papers" language?


"Later it was called "JavaScript collection" and blessed to the
standard". You are referring to the DOM standard, before mentioning it
in the next paragraph. It is called an "HTMLCollection". It has the
interface:
interface HTMLCollection {
readonly attribute unsigned long length;
Node item(in unsigned long index);
Node namedItem(in DOMString name);
};
In the ECMAScript binding, both can be called indirectly by using the
square bracket notation (which is equivalent with the dot-notation
when the property name is a valid identifier).
<URL:http://www.w3.org/TR/DOM-Level-2-HTML/ecma-script-binding.html>


"I strongly encourage you while working with forms and frames always
use index notation:
document.forms[0].elements[0];
window.frames[0]
That will make your code more stable and predictable."
I disagree. Using numeric indices is not stable against changes
to the page. If you insert a form before the one you refer to here,
you also need to change the index. Instead use:
document.forms['formId'].elements['elementName']
widow.frames['frameName']
It is safer. You do get collections when more than one element
have the same name, but that should not come as a surprise to you,
if you created the form. You can just traverse that collection then.
(and yes,
document.forms.formId.elements.elementName
is just as good when elementName is a valid identifier)


"then later we should address them respectively:
arrayObject[0];
hashObject{'key'};"
I fail to see why the format of a literal should define the format
of a lookup, but well, you are entitled to your opinion :)


Generally: The part about arrays is ok, with small nitpicks. The part
about hashes doesn't seem as coherent. It's a jubmle of independent
points, without a common goal. In other words: Find out what your
main point is, and build up to it.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

re: Array and Hash in JavaScript : materials for FAQ : v2

Lasse Reichstein Nielsen wrote:[color=blue]
> Comment: "You can use a notation like arrayObject[-1] top address the
> last element in the array". Nope, doesn't work. It merely tries to
> access the property named "-1", which doesn't exist unless you created
> it.[/color]

My bad! Did not check it for addressing option. Changed to:

Although in array methods you may refer the last array element using
-1, it's not a negative index, it's just a shortcut: for instance
arrayObject.slice(10,-1) simply means
arrayObject.slice(10,arrayObject.length-1)

[color=blue]
> Re. "multidimensional arrays". Javascript doesn't have mutidimensional
> arrays in the sense of C, b ut only arrays of arrays. In C you wouldn't
> be able to change a sub-array like:
> int arr[4][4];
> arr[3] = new int[4];
>
> "The actual amount of possible indexes (dimensions) is platform
> dependent, but always very big, so you should not worry about it."
> It's not really platform dependent either, just limited by available
> memory. Or, for a seemingly infinite-dimension array:
> var x = []
> x[0] = x;[/color]

Changed through to a neutral form.

[color=blue]
> You need to define what you mean by "element" of an array. You use it
> in the sense "what you get when indexing with an integer less than the
> array's length". That makes "new Array(10)" have ten elements, all
> undefined. Other people (myself included) uses "element" to mean
> an actual property of the array object, so "new Array(10)" has no
> elements. This is a more usual meaning for *sparse* arrays, where
> not all indices correspond to an "element".
>
> You sortof say it in the section following this:
> " Nevertheless it is important to understand the difference of (1)
> undefined value received from a non-instantiated element within your
> array and (2) undefined value received when addressing an element with
> index bigger than length-1."
>
> I think that's a dangerous way to make the point. There is no
> difference between the "undefined" values you get, nor between the
> underlying functionality that gives you that "undefined". What you
> are trying to say is that:
> Arrays in Javascript are an abstraction on top of normal object
> properties. For property names that are (bounded) integers, it
> works as if the array was a contiguous sequence of values, some
> of them "undefined", indxed from 0 to one less than the arrays
> "length" property's value.
> Arrays are *implemented* as sparse arrays. Only the indices that have
> been assigned to, take up space, and the "length" property only
> guarantees to be larger than the largest index in use.
> The methods operating on arrays respect the abstraction and all treat
> the array as a contiguous sequence of, potentially "udefined" values.
> [[ your example with "slice" ]].[/color]

Well, I'm affraid my vision is the only one that stops us from
declaring native array methods "broken".
My point always was that we need to see the difference between the
hardware reality and the human abstractions to describe it. Unless
you're working on ASSEMBLER, you're always dealing with something that
doesn't really exist. But at least you should call it the same words as
people around do. If slice() and splice() and so treat the array this
and not other way (and not in JavaScript only), so be it.

I just see another simplification of JavaScript, that forces us
sometimes to name and notate very different things in the same way. And
after that to have discussions "What kind of Joe is it really?"
JavaScript has only undefined and null. So by describing the situation
"within array" / "outside of array" we can only talk of "undefined kind
1" and "undefined kind 2", and it's really confusing (but still needs
to be understood).
If we move on on say VBasic.Net, we have the standard triad Nothing /
Empty / Null.
So:
1) something set *by myself* to be nothing is Null.
2) something appeared "against its will" in an enclosing structure (but
never directly set yet) is Empty.
3) something totally out of the scope of my program is Nothing.

So if
arrayObject=new Array(); arrayObject[100]=null;
then arrayObject[100] is Null, arrayObject[99] is Empty, and
arrayObject[1000] is Nothing. It gets much easier, is it? :-)

But I don't think we shall reach a compromise here...

[color=blue]
> "On Macintosh platform an attempt to use a number for hash key leads
> to an error. As a workaround, if you really need to have a number as
> hash key (?), always put it into quotes."
>
> Are you talking about Javascript objects here? It's not obvious.
> Also, "Macintosh platform" is far from an exact specification of
> the Javascript implementation that fails. It could be the one in
> IE5.2, in Safari, in Galleon, in OmniWeb, ...[/color]

I hever was a Macintosh user, sorry. I guess the current platform is
OX? I saw references of this error in the Internet, but it would be
really great to check it through.
If there are any Macintosh users around here, they could run this quick
test:
<script type="text/javascript">
var a = new Object();
var b = [];
a[1] = 'foo';
b[1] = 'bar';
</script>
to see if any errors.
[color=blue]
> "JavaScript doesn't have a built-in constructor for hash objects. But
> each object supports hash table mechanics inherited from the Object
> prototype."
> It's not Object.prototype that have string based properties, it's
> just objects themselves. If you find a way to create an object without
> inheriting Object.prototype, you can still add properties to it.[/color]

Changed to:

But each object has native hash table mechanics to keep its
property:value pairs

[color=blue]
> "Unfortunately interpreter doesn't resolve variables in such
> declarations. Everything (quoted or not quoted) will be treated as
> string literals."
> Not so. It's variables in the keys that doesn't work, the values
> work fine:
> var x = 42;
> var h = {foo: x, x:x, "y":x, "Lorem ipsum, lala": x, "":x};[/color]

My bad! Changed to:

Unfortunately interpreter doesn't resolve variables used in keys.
Quoted or not quoted they will be treated as string literals.
Nevertheless you can instantiate hash with values taken from variables:

var hashObject = {'key1':myVar1,'key2':myVar2};

[color=blue]
> There is no guarantee that implementations have efficient property
> look-up. It seems like IE have linear time look-up of properties.[/color]

I don't think so, because object properties (if you list them unsorted)
corresponde to the model "memory baskets" strusture. Their interpreter
can have some bug in it though. Any reliable time mesurements around
here? (and please on real hash, not on a build-in object's properties).

[color=blue]
> What is an "out of papers" language?[/color]

"out of papers" - first think through, then do (like C)
"out of life" - first do, then look what happens (like LiveScript or
Perl).

Any better terms?

[color=blue]
> "Later it was called "JavaScript collection" and blessed to the
> standard". You are referring to the DOM standard, before mentioning it
> in the next paragraph. It is called an "HTMLCollection".[/color]

Changed
[color=blue]
> It has the
> interface:
> interface HTMLCollection {
> readonly attribute unsigned long length;
> Node item(in unsigned long index);
> Node namedItem(in DOMString name);
> };
> In the ECMAScript binding, both can be called indirectly by using the
> square bracket notation (which is equivalent with the dot-notation
> when the property name is a valid identifier).
> <URL:http://www.w3.org/TR/DOM-Level-2-HTML/ecma-script-binding.html>[/color]

A quot from my article: "...(later)... ECMA did a good cleanup job in
their specifications (especially the 3rd and the last one issued in
Dec.1999)";

[color=blue]
> "I strongly encourage you while working with forms and frames always
> use index notation:
> document.forms[0].elements[0];
> window.frames[0]
> That will make your code more stable and predictable."
> I disagree. Using numeric indices is not stable against changes
> to the page. If you insert a form before the one you refer to here,
> you also need to change the index. Instead use:
> document.forms['formId'].elements['elementName']
> widow.frames['frameName']
> It is safer. You do get collections when more than one element
> have the same name, but that should not come as a surprise to you,
> if you created the form. You can just traverse that collection then.
> (and yes,
> document.forms.formId.elements.elementName
> is just as good when elementName is a valid identifier)[/color]

See the cases I linked to the article. The isssue is to be sure that
you always get something what you asked for, not a substitution, even
if it is also usable sometimes.
[color=blue]
> "then later we should address them respectively:
> arrayObject[0];
> hashObject{'key'};"
> I fail to see why the format of a literal should define the format
> of a lookup, but well, you are entitled to your opinion :)[/color]

For the same reason we're talking about "undefined kind 1" and
"undefined kind 2". Different notation eliminates the question of what
are we doing or trying to reach.

[color=blue]
> Generally: The part about arrays is ok, with small nitpicks. The part
> about hashes doesn't seem as coherent. It's a jubmle of independent
> points, without a common goal.[/color]

The super goal is to pull out array and hash as separate and very
different *programming entity* from your "Great Mother"-like
HTMLCollection that supposes to include all and explains everything.
Because it doesn't, at least not anymore.

The mini goal to address numerous issues that should be included into
FAQ's such as:

1) arrayObject = new Array(); arrayObject['foo'] = 'bar';
arrayObject.length == 0;

2)
<http://groups-beta.google.com/group/comp.lang.javascript/browse_frm/thread/a618747cf483e3f5/5649fc9f65f33c20#5649fc9f65f33c20>

3)
<http://groups-beta.google.com/group/comp.lang.javascript/browse_frm/thread/8005d8ef77288c39/186b0f8e07897987?q=group:comp.lang.javascript+auth or:VK&rnum=39&hl=en#186b0f8e07897987>

re: Array and Hash in JavaScript : materials for FAQ : v2

"VK" <schools_ring@yahoo.com> writes:
[color=blue]
> Well, I'm affraid my vision is the only one that stops us from
> declaring native array methods "broken".
> My point always was that we need to see the difference between the
> hardware reality and the human abstractions to describe it.[/color]

I can agree on that. It is more the words used to describe the
abstraction that is my problem.
[color=blue]
> I just see another simplification of JavaScript, that forces us
> sometimes to name and notate very different things in the same way. And
> after that to have discussions "What kind of Joe is it really?"
> JavaScript has only undefined and null. So by describing the situation
> "within array" / "outside of array" we can only talk of "undefined kind
> 1" and "undefined kind 2", and it's really confusing (but still needs
> to be understood).[/color]

My problem is that you use the *values* to distinguish "inside" and
"outside" the array. The values are the same, and (at a lower level)
for the same reason.

What distinguishes being inside and outside the array, is the indices,
not the values.

So, in other words:

When using the notation arr[index] , where "arr" is an Array object,
one of the following two scenarios holds:

If your index is a non-negative integer less than the length of the
array (as given by the "length" property), then you are accessing
an array element. It will be undefined if no value have been stored
at that index.

If your index is either not a non-negative integer, or not less than
the arrays length, then you are not accessing an array element, but
merely a property of the object.

Not perfect, but moves the distinction from undefined 1 vs undefined 2
to the indices used to access them.
[color=blue]
> If we move on on say VBasic.Net, we have the standard triad Nothing /
> Empty / Null.[/color]

I'm not sure what makes it so standard, since I have never heard about
it before (but then again, I never did VB).
[color=blue]
> So:
> 1) something set *by myself* to be nothing is Null.
> 2) something appeared "against its will" in an enclosing structure (but
> never directly set yet) is Empty.
> 3) something totally out of the scope of my program is Nothing.[/color]

I prefer throwing exceptions when people go outside of the scope of
the program, and initializing everything, so I would probably only
see Null. (Does it show that I'm usually doing Java? :)
[color=blue]
> So if
> arrayObject=new Array(); arrayObject[100]=null;
> then arrayObject[100] is Null, arrayObject[99] is Empty, and
> arrayObject[1000] is Nothing. It gets much easier, is it? :-)[/color]

It makes some kind of sense, but I would presonally prefer to remove
"null" from Javascript rather than have one more value that means
really means "no value".
[color=blue]
> I hever was a Macintosh user, sorry. I guess the current platform is
> OX?[/color]

OS-X is not a Javascript platform, so it is probably Safari. It still
has a few quirks in its Javascript engine, but I bet they'll be sorted
out soon enough.
[color=blue][color=green]
>> There is no guarantee that implementations have efficient property
>> look-up. It seems like IE have linear time look-up of properties.[/color]
>
> I don't think so, because object properties (if you list them unsorted)
> corresponde to the model "memory baskets" strusture.[/color]

If I create an object and add the properties "x0" .. "x99", and then
read them out using for(var k in arr) {...} then they come out in the
same order as they were added, no matter if I add them forwards or
backwards. That shows no "memory basket" behavior.

Also, try this code:
---
var N = 10000; // try varying N.
var arr = {};

for (var i = N-1; i >= 0; i--) {
arr["x"+i] = true;
}
var res = [];

var t0 = new Date();
for (var i = 0; i < N; i++) {
var t = arr["x"+i];
}
var t1 = new Date();
alert((t1-t0)/N); // note - divides by N!
---
If IE was using a hash structure, then the result should be approx.
the same no matter what N is (limited by the granularity of the timer).
Instead it seems that doubling N gives an increase of little less than
a doubling ... i.e., accessing properties is not constant time, more
like linear.

[color=blue]
> Their interpreter can have some bug in it though. Any reliable time
> mesurements around here? (and please on real hash, not on a build-in
> object's properties).[/color]

I hope that above qualifies :)
[color=blue]
>[color=green]
>> What is an "out of papers" language?[/color]
>
> "out of papers" - first think through, then do (like C)
> "out of life" - first do, then look what happens (like LiveScript or
> Perl).
>
> Any better terms?[/color]

"designed"? :)
[color=blue][color=green]
>> I disagree. Using numeric indices is not stable against changes
>> to the page. If you insert a form before the one you refer to here,
>> you also need to change the index. Instead use:
>> document.forms['formId'].elements['elementName']
>> widow.frames['frameName'][/color][/color]
....[color=blue]
> See the cases I linked to the article. The isssue is to be sure that
> you always get something what you asked for, not a substitution, even
> if it is also usable sometimes.[/color]

You always get what you ask for. Computers are not that inventive.
The big question is whether you know what you ask for.

If you have more than one form control with the same control name,
then accessing by name is obviously not unambiguous. You then get
a collection of the matches. But you *should* know whether the name
is unique, and if you don't, it's better that the code fails as
soon as possible.

I still recommend accessing by name, not index. Indices are too
fragile when the page changes.
[color=blue]
> For the same reason we're talking about "undefined kind 1" and
> "undefined kind 2". Different notation eliminates the question of what
> are we doing or trying to reach.[/color]

It all comes back to arrays not *really* being part of the language.
There is just an *object* with array-like behavior (which pretty
much boils down to the magic "length" property ... ignore "length",
and there is no difference between Arrays and Objects)
[color=blue]
> The super goal is to pull out array and hash as separate and very
> different *programming entity* from your "Great Mother"-like
> HTMLCollection that supposes to include all and explains everything.
> Because it doesn't, at least not anymore.[/color]

I would rather define Array and Associative Array ("hash" smells too
much like a specific implementation) separatly, then show how each
can be approximated by a construct in Javascript (Array and Object).

In both cases, it is not a clean implementation, the underlying
object shows through the cracks. An object is never completely
free of properties (inheriting some from Object.prototype), and
an array is really just an object with a magic "legth".
[color=blue]
> The mini goal to address numerous issues that should be included into
> FAQ's such as:
>
> 1) arrayObject = new Array(); arrayObject['foo'] = 'bar';
> arrayObject.length == 0;[/color]

I'm not sure it qualifies as a *F*AQ, but it's worth repeating: Don't
use arrays unless you mean it.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

re: Array and Hash in JavaScript : materials for FAQ : v2

Lasse Reichstein Nielsen wrote:[color=blue]
> "VK" <schools_ring@yahoo.com> writes:
>[color=green]
> > Well, I'm affraid my vision is the only one that stops us from
> > declaring native array methods "broken".
> > My point always was that we need to see the difference between the
> > hardware reality and the human abstractions to describe it.[/color]
>
> I can agree on that. It is more the words used to describe the
> abstraction that is my problem.
>[color=green]
> > I just see another simplification of JavaScript, that forces us
> > sometimes to name and notate very different things in the same way. And
> > after that to have discussions "What kind of Joe is it really?"
> > JavaScript has only undefined and null. So by describing the situation
> > "within array" / "outside of array" we can only talk of "undefined kind
> > 1" and "undefined kind 2", and it's really confusing (but still needs
> > to be understood).[/color]
>
> My problem is that you use the *values* to distinguish "inside" and
> "outside" the array. The values are the same, and (at a lower level)
> for the same reason.
>
> What distinguishes being inside and outside the array, is the indices,
> not the values.
>
> So, in other words:
>
> When using the notation arr[index] , where "arr" is an Array object,
> one of the following two scenarios holds:
>
> If your index is a non-negative integer less than the length of the
> array (as given by the "length" property), then you are accessing
> an array element. It will be undefined if no value have been stored
> at that index.
>
> If your index is either not a non-negative integer, or not less than
> the arrays length, then you are not accessing an array element, but
> merely a property of the object.
>
> Not perfect, but moves the distinction from undefined 1 vs undefined 2
> to the indices used to access them.[/color]

I guess you're talking array elements too materialistically despite
your overall philosophical approach :-)

Array alement:
A single data item in an array, identified by the array name and one or
more subscripts.
<http://publib.boulder.ibm.com/infocenter/lnxpcomp/index.jsp?topic=/com.ibm.xlf91l.doc/xlflr/lr571.htm>

So saying "array element" doesn't imply at all "some value". Same way
saying "table cell" doesn't imply "some cell content" (it could be
shiny empty).
Array element simply is someting located withing the borders of array's
row (matrix, cube, n-linked hypercube). These borders are delimited by
each dimension length, and only within these borders array methods are
operating and having some sense.

Maybe indeed "undefined 1" and "undefined 2" are still too abstract.
I'll work on it :-) Concerning the addressing of array elements beyond
the array lenght, I don't see the reason to specify what exactly we've
addressing in this case. Not an array and not for array for sure. Outer
space, and that's it.

I can imagine a durty trick like:
arr = [1,2,3];
arr["10000"] = "Hi!";
alert(arr[10000]);
but it's a durty trick, and nothing more. It's being explaned enough in
the "Array as Hash" section.

[color=blue][color=green]
> > If we move on on say VBasic.Net, we have the standard triad Nothing /
> > Empty / Null.[/color]
>
> I'm not sure what makes it so standard, since I have never heard about
> it before (but then again, I never did VB).
>[color=green]
> > So:
> > 1) something set *by myself* to be nothing is Null.
> > 2) something appeared "against its will" in an enclosing structure (but
> > never directly set yet) is Empty.
> > 3) something totally out of the scope of my program is Nothing.[/color]
>
> I prefer throwing exceptions when people go outside of the scope of
> the program, and initializing everything, so I would probably only
> see Null. (Does it show that I'm usually doing Java? :)[/color]

OK, I should say "rather standard in Microsoft languages Nothing, Empty
and Null". I guess so far it's the closest encounter of the words
"standard" and "Microsoft" in this group (just 4 chars apart ) :-))

[color=blue]
> Also, try this code:
> ---
> var N = 10000; // try varying N.
> var arr = {};
>
> for (var i = N-1; i >= 0; i--) {
> arr["x"+i] = true;
> }
> var res = [];
>
> var t0 = new Date();
> for (var i = 0; i < N; i++) {
> var t = arr["x"+i];
> }
> var t1 = new Date();
> alert((t1-t0)/N); // note - divides by N!
> ---
> If IE was using a hash structure, then the result should be approx.
> the same no matter what N is (limited by the granularity of the timer).
> Instead it seems that doubling N gives an increase of little less than
> a doubling ... i.e., accessing properties is not constant time, more
> like linear.[/color]

Actually hash LOOKUP operation and stricture are optimized for
*semi-predictable intensive* value reading. So it should act a bit like
processor cache (by replacing pairs from one backet to other depending
on demands). The test I think to write tomorrow (if it's still reining)
has to accomodate this specifics. On randomized but repetititive
lookups a real hash has to show improving response time from one cicle
to another.

[color=blue][color=green][color=darkred]
> >> I disagree. Using numeric indices is not stable against changes
> >> to the page. If you insert a form before the one you refer to here,
> >> you also need to change the index. Instead use:
> >> document.forms['formId'].elements['elementName']
> >> widow.frames['frameName'][/color][/color][/color]

So do I with you by now. More tests needed. Needed too collect all
promising cases from this group and check it on current brousers.
Everything about form, window and frame. Will take some time.

[color=blue]
> and an array is really just an object with a magic "legth".[/color]
So it's a String then? And frames too? and...

And Canvas, Container, jLabel and jButton are really the same things,
just called differently in different context? Idealisme subjectif,
Monsieur! ;-)

re: Array and Hash in JavaScript : materials for FAQ : v2

"VK" <schools_ring@yahoo.com> writes:
[color=blue]
> I guess you're talking array elements too materialistically despite
> your overall philosophical approach :-)[/color]

I am trying not to, but I might not have expressed it clearly enough :)
[color=blue]
> Array alement:
> A single data item in an array, identified by the array name and one or
> more subscripts.
> <http://publib.boulder.ibm.com/infocenter/lnxpcomp/index.jsp?topic=/com.ibm.xlf91l.doc/xlflr/lr571.htm>[/color]

That works for me.
[color=blue]
> So saying "array element" doesn't imply at all "some value".[/color]

Well "single data item" pretty much sounds like "some value" to me.
In a sparse array, some elements can be empty (and not hold a single
data item), which is exactly what Javascript arrays are.
[color=blue]
> Maybe indeed "undefined 1" and "undefined 2" are still too abstract.[/color]

I'd say too concrete. The value is "undefined" (different from the
value being undefined :), but that doesn't really matter. What matters
is that one corresponds to an array element (an empty one) and the
other doesn't. The actual value ("undefined") is incidental.
[color=blue]
> I'll work on it :-) Concerning the addressing of array elements beyond
> the array lenght, I don't see the reason to specify what exactly we've
> addressing in this case. Not an array and not for array for sure. Outer
> space, and that's it.[/color]

The problem with Javascript is that there is no encapsulation. You
can't hide implementation details ...
[color=blue]
> I can imagine a durty trick like:
> arr = [1,2,3];
> arr["10000"] = "Hi!";
> alert(arr[10000]);
> but it's a durty trick, and nothing more. It's being explaned enough in
> the "Array as Hash" section.[/color]

I don't see the dirt in that (except using a string representation of
the integer instead of a number), which should ofcourse be explained
to be equivalent.
[color=blue]
> Actually hash LOOKUP operation and stricture are optimized for
> *semi-predictable intensive* value reading. So it should act a bit like
> processor cache (by replacing pairs from one backet to other depending
> on demands).[/color]

That would be an optimizing hash table, where the hashing function
changes. Some implementations (like Java's HashMap) only changes the
hashing function on additions (based on the number of elements, to
avoid too many elements in one basket). Reading doesn't change
hashing.
[color=blue]
> The test I think to write tomorrow (if it's still reining)
> has to accomodate this specifics. On randomized but repetititive
> lookups a real hash has to show improving response time from one cicle
> to another.[/color]

That's one design. I wouldn't require that of a hash table.
[color=blue][color=green]
>> and an array is really just an object with a magic "legth".[/color]
> So it's a String then? And frames too? and...[/color]

Arrays are objects, and they make no attempt at hiding it. They
accept all the typical operations on objects, e.g.,
4 in arr
arr.hasOwnProperty(4)
for(key in arr) { ...
delete arr[4]
These are object operations, that double as array operations only
because arrays are objects. Also, all the operations in
Array.prototype will also work for non-Array objects, as long as
they have a property called "length" with a number in it. It's
deliberatly designed so that they can be reused for non-array
purposes.

[color=blue]
> And Canvas, Container, jLabel and jButton are really the same things,[/color]

Now you are comparing to a language with encapsulation. Sure, all
JLabel's are also Object's, but since a Java Object has only very
little functionality, there is no overlap between Object and JLabel
operations. In Javascript, there is overlap between Object and Array
functionality.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

re: Array and Hash in JavaScript : materials for FAQ : v2

I edited the text of the article
<http://www.geocities.com/schools_ring/ArrayAndHash.html> up to my
compromise abilities. I would like to add to the very bottom something
like:

"Many thanks to Lasse Reichstein Nielsen (one of comp.lang.javascript
gurus) for his sriticism and technical expertise. Despite the above
article doesn't totally correspond to his personal opinion."
Please let me know if it's OK (or your version).

And please don't look at this as an a** licking. I'll get s*** out of
anyone now and later to find out the truth (even if it appears to be
*not my truth*). I just used to be clear in copyrights in any
publication.

P.S. I did not touch the Frames/Forms/Elements section, because many
cases (including even today's harvest) show that:
either I'm right and you wrong or I'm partially right and you're
partially wrong, and the big picture is not layed out yet. But it is
indeed strange that very different browsers demonstrate an instability
in the same circumstances. Usually it's either IE-bug, or FF-bug etc.
"Browser-bug" would be too much to handle.

P.P.S. I'm still getting the exact picture of how a real hash (map,
associative array) should behave, so I could put the right test on it.
Unfortunately (for hash) it's a magic weather outside so the only
basket I'm concerned right now is our pick-nick basket my wife is
preparing on the kitchen :-)

re: Array and Hash in JavaScript : materials for FAQ : v2

We need to leave right now, but the last warming up class of wine just
shoot me:

array consists of "data holders", and length indicates the amount of
data holders in each dimensions. and array methods go through all
registered data holders ans count them in their operations. But data
holder may indeed hold some data or do not, it's not a requirement.

a real Rein Riesling is something you need to think properly about
arrays :-)

re: Array and Hash in JavaScript : materials for FAQ : v2

Lasse Reichstein Nielsen wrote:
[color=blue]
> "VK" <schools_ring@yahoo.com> writes:[color=green]
>> If we move on on say VBasic.Net, we have the standard triad Nothing /
>> Empty / Null.[/color]
>
> I'm not sure what makes it so standard, since I have never heard
> about it before (but then again, I never did VB).[/color]

Be proud of it. VB is rather a disease than a programming language
which is why so many kiddies and so less professionals use it.


PointedEars

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1120916934.756841.241050@g47g2000cwa.googlegroups .com>, VK
<schools_ring@yahoo.com> writes

<snip>[color=blue]
>array consists of "data holders", and length indicates the amount of
>data holders in each dimensions.[/color]
<snip>

The length indicates whatever the Language Standard says it indicates,
no more, no less.

If you don't like what it indicates then use another language.

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1120719318.257842.72800@f14g2000cwb.googlegroups. com>, VK
<schools_ring@yahoo.com> writes

<snip>[color=blue]
>I invite all members of the previous discussion, as well as anyone
>interested in Array vs Hash mechanics in JavaScript to read this
>article and to express your opinion (if any).[/color]
<snip>

Please stop misusing the word 'Hash'. A Hash Table, aka Hash Map, is
just one way of implementing what's needed for objects.

There are other ways of implementing what's needed. Some of them are
more appropriate when most objects have a small number of properties.
E.g. A linked list, a tree.

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

Thomas 'PointedEars' Lahn wrote:
[color=blue]
> VB is rather a disease than a programming language
> which is why so many kiddies and so less professionals
> use it.[/color]

Then I don't think you have much corporate experience. Actually VB is
pretty popular in software companies (at least in W Europe that is)

--
Bart

re: Array and Hash in JavaScript : materials for FAQ : v2

> The length indicates whatever the Language Standard says it indicates,[color=blue]
> no more, no less.[/color]

Exactly. And arrayObject.length indicates the amount of registered
elements (data holders) in the array. And if you don't like it, you may
jump on GBasic, Focal or any other place away from here.

re: Array and Hash in JavaScript : materials for FAQ : v2

John G Harris wrote:[color=blue]
> Please stop misusing the word 'Hash'. A Hash Table, aka Hash Map, is
> just one way of implementing what's needed for objects.
>
> There are other ways of implementing what's needed. Some of them are
> more appropriate when most objects have a small number of properties.
> E.g. A linked list, a tree.
>
> John
> --
> John Harris[/color]

We're not talking about possible programming entitities we could
invent/introduce for programming. Its name is Legion.
We're talking about existing separate programming entities in
JavaScript. Besides all others these are: Array, Associative array
(Hash) and HTMLCollection. Despite these are very different entities
with very different method/property sets, on the basic level there is a
huge cocktail of all three of them in the minds.

re: Array and Hash in JavaScript : materials for FAQ : v2

Thomas 'PointedEars' Lahn wrote:[color=blue]
> Lasse Reichstein Nielsen wrote:
>[color=green]
> > "VK" <schools_ring@yahoo.com> writes:[color=darkred]
> >> If we move on on say VBasic.Net, we have the standard triad Nothing /
> >> Empty / Null.[/color]
> >
> > I'm not sure what makes it so standard, since I have never heard
> > about it before (but then again, I never did VB).[/color]
>
> Be proud of it. VB is rather a disease than a programming language
> which is why so many kiddies and so less professionals use it.[/color]

Your pointed ears again with another chunk of scum!

I don't like VB neither (looks too babish in all aspects). But VBA is
based on it, and you get good paid for good VBA modules.

But I guess you're one of these "conceptual" people who prefer to sit
with no money but keep the concept in its purity?

re: Array and Hash in JavaScript : materials for FAQ : v2

VK wrote:
[color=blue]
> I don't like VB neither (looks too babish in all aspects). But VBA is
> based on it, and you get good paid for good VBA modules.[/color]

VBA is just as bad, if not worse. Unfortunately it is the only means
(AFAIK) to script MS Office apps.
[color=blue]
> But I guess you're one of these "conceptual" people who prefer to sit
> with no money but keep the concept in its purity?[/color]

I prefer not to take jobs when it has to be a programming language that
is a pain in the ass, yes.


PointedEars

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1121611200.570046.104240@g43g2000cwa.googlegroups .com>, VK
<schools_ring@yahoo.com> writes[color=blue]
>
>
>John G Harris wrote:[color=green]
>> Please stop misusing the word 'Hash'. A Hash Table, aka Hash Map, is
>> just one way of implementing what's needed for objects.
>>
>> There are other ways of implementing what's needed. Some of them are
>> more appropriate when most objects have a small number of properties.
>> E.g. A linked list, a tree.
>>
>> John
>> --
>> John Harris[/color]
>
>We're not talking about possible programming entitities we could
>invent/introduce for programming. Its name is Legion.
>We're talking about existing separate programming entities in
>JavaScript. Besides all others these are: Array, Associative array
>(Hash) and HTMLCollection. Despite these are very different entities
>with very different method/property sets, on the basic level there is a
>huge cocktail of all three of them in the minds.[/color]

You are talking about Hash Tables with their buckets (aka "hash memory
baskets") and their hashing algorithms.

You are saying that every object grabs kilobytes in case there are going
to be a lot of properties. And you are saying that some choices of
property names will be worst case : wasting most buckets and with lousy
performance. ECMA 262 does NOT require this.

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1121610630.350942.236080@g47g2000cwa.googlegroups .com>, VK
<schools_ring@yahoo.com> writes

<John said>[color=blue][color=green]
>> The length indicates whatever the Language Standard says it indicates,
>> no more, no less.[/color]
>
>Exactly. And arrayObject.length indicates the amount of registered
>elements (data holders) in the array. And if you don't like it, you may
>jump on GBasic, Focal or any other place away from here.[/color]

The Language Standard says
"The length property of this Array object is always numerically greater
than the name of every property whose name is an array index."
which is not what you've just said.

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

John G Harris wrote:[color=blue]
> You are saying that every object grabs kilobytes in case there are going
> to be a lot of properties. And you are saying that some choices of
> property names will be worst case : wasting most buckets and with lousy
> performance. ECMA 262 does NOT require this.
>
> John
> --
> John Harris[/color]

I'm cannot say it until I conduct the tests. Maybe the hash mechanics
is implemented in JavaScript objects, maybe not.
On the first loot at the native objects at least (the order of
methods/properties as they listed through the for-in loop) presumably
hash mechanics is implemented or at least mimiced.

HTMLCollection for sure has nothing to do with baskets - it's build by
the order the elements appear on the page.

And in any case you as programmer do not have to worry about some
special property naming for a "better basket packaging". As you don't
need to allocate memory for your var's (talking JavaScript only).

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1121870602.935313.260570@f14g2000cwb.googlegroups .com>, VK
<schools_ring@yahoo.com> writes[color=blue]
>
>
>John G Harris wrote:[color=green]
>> You are saying that every object grabs kilobytes in case there are going
>> to be a lot of properties. And you are saying that some choices of
>> property names will be worst case : wasting most buckets and with lousy
>> performance. ECMA 262 does NOT require this.
>>
>> John
>> --
>> John Harris[/color]
>
>I'm cannot say it until I conduct the tests. Maybe the hash mechanics
>is implemented in JavaScript objects, maybe not.[/color]

If 'maybe not' then you mustn't say objects use hash tables.

[color=blue]
>On the first loot at the native objects at least (the order of
>methods/properties as they listed through the for-in loop) presumably
>hash mechanics is implemented or at least mimiced.[/color]

Properties might be listed in the order they were put into the object,
and you can't say what that order is for a native object.

Hash tables mimic the general requirements of associative arrays, not
the other way around.

[color=blue]
>HTMLCollection for sure has nothing to do with baskets - it's build by
>the order the elements appear on the page.[/color]

It is still built from objects, using object properties.

[color=blue]
>And in any case you as programmer do not have to worry about some
>special property naming for a "better basket packaging". As you don't
>need to allocate memory for your var's (talking JavaScript only).[/color]

With hash tables you always have to worry. They can turn round and bite
you if you don't know the hashing algorithm, and if you do know it you
can still be very unlucky.

The second sentence doesn't make sense. Do you really know what a hash
table is?

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

>> As you don't need to allocate memory[color=blue][color=green]
>> for your var's (talking JavaScript only).[/color][/color]
[color=blue]
> The second sentence doesn't make sense.[/color]

Simply means that you *usually* don't have to worry about memory
menagement issues in JavaScript (variables, baskets etc.). And if you
even had have some worries, the only way to handle them would be a pill
of Prozac because JavaScript itself has nearly nothing to offer.
[color=blue]
> Do you really know what a hash table is?[/color]
I guess I do. But if you have ideas how to check something for
"hashness" for 100% guarantee, I would love to hear it. That qualities
should be tested and what responses should be received?

re: Array and Hash in JavaScript : materials for FAQ : v2

In article <1121888306.595775.40330@z14g2000cwz.googlegroups. com>, VK
<schools_ring@yahoo.com> writes[color=blue][color=green][color=darkred]
>>> As you don't need to allocate memory
>>> for your var's (talking JavaScript only).[/color][/color]
>[color=green]
>> The second sentence doesn't make sense.[/color]
>
>Simply means that you *usually* don't have to worry about memory
>menagement issues in JavaScript (variables, baskets etc.). And if you
>even had have some worries, the only way to handle them would be a pill
>of Prozac because JavaScript itself has nearly nothing to offer.
>[color=green]
>> Do you really know what a hash table is?[/color]
>I guess I do. But if you have ideas how to check something for
>"hashness" for 100% guarantee, I would love to hear it. That qualities
>should be tested and what responses should be received?[/color]

It looks as though you don't know what can go wrong with the hashing
function, the function that turns key values into bucket numbers.

I can only conclude that you really don't know what a hash table is.

John
--
John Harris

re: Array and Hash in JavaScript : materials for FAQ : v2

"VK" <schools_ring@yahoo.com> writes:

Please include attributions for your quotes!
[color=blue][color=green]
>> Do you really know what a hash table is?[/color]
> I guess I do. But if you have ideas how to check something for
> "hashness" for 100% guarantee, I would love to hear it. That qualities
> should be tested and what responses should be received?[/color]

Then I would say that you don't.

A hast table is an implementation of an associative array that uses
hash values (numbers) calculated from key values to do approx.
constant time lookup.

There are no external qualities, except time compliexity of
operations, that distinguish a hash based implementation from other
choices of implementation.

The 100% guarantee only requires looking at the code implementing
the associative array.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'