Array as hash tables

[Alexis Nikichine]

Hello,

It is common knowledge that arrays can be used as hashtables:

var color = [];

color["red"] = 0xFF0000;
color["blue"] = 0x0000FF;


With this, I can check whether a string identifies a color, or not:

function isColor(string)
{
return color[string] == undefined;
}

My only concern is that

isColor("pop") == true

and that will hold true for quite a few annoying, parasitic,
"keywords" ("constructo r", "length", etc...)

I finally came to use the following as a naked object, to use as a
hashtable:

function HashTable() { this.constructo r = undefined; }

// example of use:
var color = new HashTable;
color["red"] = 0xFF0000


Question for experts: won't then there be other unexpected, hardcoded,
keywords stalking my strings in the dark, and returning obscure,
native, js objects, where I expected plain numbers ?

Any help appreciated,


Alexis

[Douglas Crockford]

Re: Array as hash tables

Alexis Nikichine wrote:
[color=blue]
> It is common knowledge that arrays can be used as hashtables:
>
> var color = [];
>
> color["red"] = 0xFF0000;
> color["blue"] = 0x0000FF;
>
>
> With this, I can check whether a string identifies a color, or not:
>
> function isColor(string)
> {
> return color[string] == undefined;
> }
>
> My only concern is that
>
> isColor("pop") == true
>
> and that will hold true for quite a few annoying, parasitic,
> "keywords" ("constructo r", "length", etc...)
>
> I finally came to use the following as a naked object, to use as a
> hashtable:
>
> function HashTable() { this.constructo r = undefined; }
>
> // example of use:
> var color = new HashTable;
> color["red"] = 0xFF0000
>
>
> Question for experts: won't then there be other unexpected, hardcoded,
> keywords stalking my strings in the dark, and returning obscure,
> native, js objects, where I expected plain numbers ?
>
> Any help appreciated,[/color]

If the indexes are not integers, then use an Object, not an Array.

var color = {};

If the subscript is an identifier (and not a reserved word), you can use
the stylish dot notation.

color.red = 0xFF0000;
color.blue = 0x0000FF;

In HTML applications, it may be better to keep color values as strings.
That way you won't get a false negative on black.

color.red = "#FF0000";
color.blue = "#0000FF";
color.black = "#000000";

If you use a little type discipline, then it is eay to distinguish your
values from Object methods.

function isColor(string) {
return typeof color[string] == "string";
}

The hashtable constructor above is silly. If it doesn't have methods,
then it is better to use a plain Object. Even better, you can use the
object literal notation.

color = {red: "#FF0000", blue: "#0000FF", black: "#000000"};

http://www.JSON.org

[Alexis Nikichine]

Re: Array as hash tables

Douglas Crockford wrote:
[color=blue]
> If the indexes are not integers, then use an Object, not an Array.
>
> var color = {};
>
> If the subscript is an identifier (and not a reserved word), you can[/color]
use[color=blue]
> the stylish dot notation.
>
> color.red = 0xFF0000;
> color.blue = 0x0000FF;
>
> In HTML applications, it may be better to keep color[/color]
[snip>

The color example was just a gratuitous one. I was worrying about
arbitrary strings typed in by users. One day, I had reports of "pop art"
request failing. "pop" yielded a function (instead of an expected
integer).
[color=blue]
> If you use a little type discipline, then it is eay to distinguish[/color]
your[color=blue]
> values from Object methods.
>
> function isColor(string) {
> return typeof color[string] == "string";
> }[/color]

When I first met the, I used type discipline, and made sure that the
returned value was an integer.
[color=blue]
> The hashtable constructor above is silly. If it doesn't have methods,
> then it is better to use a plain Object. Even better, you can use the
> object literal notation.[/color]

Unfortunately, I can't rely on type discipline, now, since (in another
urelated case) I need an hash (and don't call me a perl boob :-)
returning hash, integers.

With a plain Object, I will get an unexpected result on "constructo r".

Which is why I am asking: is my HashTable a really really empty
Object/Function, once the "constructo r" member has been blanked ?

Alexis

--
some domain is free (and btw, everything I know, I learned from your
site; thank you :-)

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

[Douglas Crockford]

Re: Array as hash tables

>>If the indexes are not integers, then use an Object, not an Array.[color=blue][color=green]
>>
>>var color = {};
>>
>>If the subscript is an identifier (and not a reserved word), you can[/color]
>
> use
>[color=green]
>>the stylish dot notation.
>>
>>color.red = 0xFF0000;
>>color.blue = 0x0000FF;
>>
>>In HTML applications, it may be better to keep color[/color]
>
> [snip>
>
> The color example was just a gratuitous one. I was worrying about
> arbitrary strings typed in by users. One day, I had reports of "pop art"
> request failing. "pop" yielded a function (instead of an expected
> integer).
>
>[color=green]
>>If you use a little type discipline, then it is eay to distinguish[/color]
>
> your
>[color=green]
>>values from Object methods.
>>
>>function isColor(string) {
>>return typeof color[string] == "string";
>>}[/color]
>
>
> When I first met the, I used type discipline, and made sure that the
> returned value was an integer.
>
>[color=green]
>>The hashtable constructor above is silly. If it doesn't have methods,
>>then it is better to use a plain Object. Even better, you can use the
>>object literal notation.[/color]
>
>
> Unfortunately, I can't rely on type discipline, now, since (in another
> urelated case) I need an hash (and don't call me a perl boob :-)
> returning hash, integers.
>
> With a plain Object, I will get an unexpected result on "constructo r".
>
> Which is why I am asking: is my HashTable a really really empty
> Object/Function, once the "constructo r" member has been blanked ?[/color]

Yes and no. A new object is empty, but it inherits values from its
prototype chain. Clobbering the constructor does not change that.

If the values in your object (or for the boobs, hash) are anything but
functions, you can use

(typeof color[string] != 'function')

to discriminate your values from the Object methods.

By the way, I think this was a design error in JavaScript. The
appearance of those methods complicates the use of objects as collections.

http://www.crockford.com/javascript/survey.html

[Alexis Nikichine]

Re: Array as hash tables

> > With a plain Object, I will get an unexpected result on[color=blue][color=green]
> > "constructo r".
> >
> > Which is why I am asking: is my HashTable a really really empty
> > Object/Function, once the "constructo r" member has been blanked ?[/color]
>
> Yes and no. A new object is empty, but it inherits values from its
> prototype chain. Clobbering the constructor does not change that.[/color]

Oups; you've left me far behind on this one. What should I expect to be
inherited by this simple as bread'n butter object :

function plainStuff(){}

... code ...

a = new plainStuff

?

Should I be concerned that in the ... code ... part, someone may have
augmented the plainStuff prototype ?
[color=blue]
> If the values in your object (or for the boobs, hash) are anything
> but functions, you can use
>
> (typeof color[string] != 'function')
>
> to discriminate your values from the Object methods.
>
> By the way, I think this was a design error in JavaScript. The
> appearance of those methods complicates the use of objects as
> collections.[/color]

I wonder too. Was not the dontEnum attribute a last minute and
incomplete workaround for this ?

May I suggest my definitive and foolprooh hash. Call it Collection, for
VB boobs:

function Collection()
{
this.constructo r = undefined;
Collection.prot otype = undefined;
}

Is it enough clobbering ?


Alexis

--
some domain is free

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

[Lasse Reichstein Nielsen]

Re: Array as hash tables

alexis.nikichin e@free.fr (Alexis Nikichine) writes:
[color=blue]
> It is common knowledge that arrays can be used as hashtables:
>
> var color = [];
>
> color["red"] = 0xFF0000;
> color["blue"] = 0x0000FF;[/color]

It is less common knowledge that arrays are overkill for this, and
that plain objects are better suited:

var color = {}; // or: new Object();
color["red"] = 0xff0000;
color["blue"] = 0x0000ff;
[color=blue]
> With this, I can check whether a string identifies a color, or not:
>
> function isColor(string)
> {
> return color[string] == undefined;[/color]

That would be better as:
return color[string] === undefined;
or, for browsers where "undefined" is not defined (the irony!) you
can define it as:
window.undefine d = window.undefine d;
or you could use
return (typeof color[string]) == "undefined" ;
[color=blue]
> My only concern is that
>
> isColor("pop") == true
>
> and that will hold true for quite a few annoying, parasitic,
> "keywords" ("constructo r", "length", etc...)[/color]

Fewer if using objects instead of arrays, but still some (e.g. toString).
[color=blue]
> I finally came to use the following as a naked object, to use as a
> hashtable:
>
> function HashTable() { this.constructo r = undefined; }
>
> // example of use:
> var color = new HashTable;
> color["red"] = 0xFF0000[/color]

Yes. That's just a plain object as well, with no properties except
those inherited from Object.prototyp e (and even with "constructo r"
removed).
[color=blue]
> Question for experts: won't then there be other unexpected, hardcoded,
> keywords stalking my strings in the dark, and returning obscure,
> native, js objects, where I expected plain numbers ?[/color]

According to ECMA 262 v3 section 5.2.4:
toString, toLocaleString, valueOf, hasOwnProperty, isPrototypeOf,
propertyIsEnume rable.
(you overwrote "constructo r", otherwise it would be there too).
[color=blue]
> Any help appreciated,[/color]

All these properties are functions. All your stored values are
numbers. Try:

function isColor(string) {
return (typeof color[string])=="number";
}

In recent versions of browsers, you can also use:

function isColor(string) {
return color.hasOwnPro perty(string);
}

That only counts the properties of the object itself, not its
prototypes. In any case, you can just use "new Object()" instead
of "new HashTable()".

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

[Lasse Reichstein Nielsen]

Re: Array as hash tables

Douglas Crockford <nospam@covad.n et> writes:
[color=blue]
> functions, you can use
>
> (typeof color[string] != 'function')
>
> to discriminate your values from the Object methods.
>
> By the way, I think this was a design error in JavaScript. The
> appearance of those methods complicates the use of objects as
> collections.[/color]

It has been somehow mitigated by later additions to, of all things,
Object.prototyp e :).

All the properties of Object.prototyp e are non-enumerable, so you
can test against non-original properties as:

propName in objectRef && !objectRef.prop ertyIsEnumerabl e(propName)

(or, if only adding to one object an not inheriting from it:
objectRef.hasOw nProperty(propN ame)
)
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Richard Cornford]

Re: Array as hash tables

Alexis Nikichine wrote:
<snip>[color=blue]
> The color example was just a gratuitous one. I was worrying
> about arbitrary strings typed in by users. One day, I had
> reports of "pop art" request failing. "pop" yielded a
> function (instead of an expected integer).[/color]
<snip>

If you want to store key/value pairs without any restrictions to the
names perhaps you need to implement an object for that storage. Maybe in
a Java style with - get - and - put - (and maybe - remove -) methods.
With an internal naming system that allows referencing by key but does
not directly use that key as a property name. You could genuinely hash
the keys to a number and then represent that number as a string property
name, but that would be quite an overhead to add to each reference. A
satisfactory indirect use of the key might be to append a space
character to the front of it, producing a property name that will never
conflict with any prototype inherited property of an object. A simple
implementation might go:-

function SafeHash(){
var safeName = [' '];
var values = {};
this.get = function(key){
safeName[1] = key;
return values[safeName.join(' ')]
};
this.put = function(key, value){
safeName[1] = key;
values[safeName.join(' ')] = value;
};
this.remove = function(key){
safeName[1] = key;
delete values[safeName.join(' ')];
};
}

A more complex version, implementing most of the pertinent methods form
the Java Hashtable, and returning Enumerator (and Iterator) Interfaces
for keys and values, might go:-

var Hashtable = (function(){
var keyAdj = [' '];
/* This private static Object constructor is used to implement
a Java style Enumerator (and Iterator) Interface:-
*/
function Enumeration(arr Nm, activeEnum, keysToIndex){
var lastIndex = null;
var enumIndex = 0;
while(typeof activeEnum[enumIndex] == 'number'){enumI ndex++;}
activeEnum[enumIndex] = 0;
this.hasNext = this.hasMoreEle ments = function(){
if(activeEnum[enumIndex] < keysToIndex.tab leLength){
return true;
}else{
if(typeof activeEnum[enumIndex] == 'number'){
activeEnum[enumIndex] = null;
}
return false;
}
};
this.next = this.nextElemen t = function(){
if(this.hasNext ()){
lastIndex = activeEnum[enumIndex];
return keysToIndex[arrNm][activeEnum[enumIndex]++];
}else{
return null;
}
};
this.remove = function(){
if(typeof lastIndex == 'number'){
removeItem(keys ToIndex._indexT oKeys[lastIndex],
keysToIndex, activeEnum);
lastIndex = null;
}
};
};
function removeItem(key, keysToIndex, activeEnum){
keyAdj[1] = key;
key = keyAdj.join('') ;
var remIndex = keysToIndex[key];
if(typeof remIndex == 'number'){
delete keysToIndex[key];
keysToIndex.tab leLength--;
for(var c = remIndex;c < keysToIndex.tab leLength;c++){
keysToIndex._in dexToValue[c] =
keysToIndex._in dexToValue[c+1];
keyAdj[1] = (keysToIndex._i ndexToKeys[c] =
keysToIndex._in dexToKeys[c+1]);
keysToIndex[keyAdj.join('')] = c;
}
keysToIndex._in dexToValue.leng th = keysToIndex.tab leLength;
for(var c = activeEnum.leng th;c--;){
if((activeEnum[c])&&(remIndex < activeEnum[c])){
activeEnum[c]--;
}
}
}
}
/* Hashtable object constructor fuction:-
*/
function HTable(){
var keysToIndex ={_indexToValue :[],_indexToKeys:[],tableLength:0} ;
var activeEnum = [];
this.get = function(key){
keyAdj[1] = key;
key = keyAdj.join('') ;
if(typeof keysToIndex[key] == 'number'){
return keysToIndex._in dexToValue[keysToIndex[key]];
}else{
return null;
}
};
this.put = function(key, value){
keyAdj[1] = key;
var sKey = keyAdj.join('') ;
if(typeof keysToIndex[sKey] == 'number'){
keysToIndex._in dexToValue[keysToIndex[sKey]] = value;
}else{
keysToIndex[sKey] = keysToIndex.tab leLength;
keysToIndex._in dexToValue[keysToIndex.tab leLength] = value;
keysToIndex._in dexToKeys[keysToIndex.tab leLength++] = key;
}
};
this.remove = function(key){
removeItem(key, keysToIndex, activeEnum);
};
this.containsKe y = function(key){
keyAdj[1] = key;
return (typeof keysToIndex[keyAdj.join('')] == 'number');
};
this.size = function(){retu rn keysToIndex.tab leLength;};
this.elements = function(){
return new Enumeration('_i ndexToValue',ac tiveEnum, keysToIndex);
};
this.keys = function(){
return new Enumeration('_i ndexToKeys', activeEnum, keysToIndex);
};
}
HTable.prototyp e.clear = function(){
var e = this.keys();
while(e.hasNext ()){
this.remove(e.n ext());
}
};
HTable.prototyp e.toString = function(){
var k,e = this.keys();
var st = '';
while(e.hasNext ()){
k = e.next();
st += k+' = '+this.get(k)+' \n';
}
return st;
};
HTable.prototyp e.containsValue =
(HTable.prototy pe.contains = function(testVa l){
var v,e = this.elements() ;
while(e.hasNext ()){
v = e.next();
if(v === testVal){
//if((v == testVal)&&(type of v == typeof testVal)){
return true;
}
}
return false;
});
HTable.prototyp e.isEmpty = function(){
return (this.size() == 0);
};
HTable.prototyp e.putAll = function(hTable ){
if((typeof hTable == 'object')&&
(hTable.constru ctor == HTable)){
var n,e = hTable.keys();
while(e.hasNext ()){
n = e.next();
this.put(n, hTable.get(n));
}
}
return this;
};
HTable.prototyp e.clone = function(){
return new HTable().putAll (this);
};
HTable.prototyp e.equals = function(o){
return (o == this);
};
return HTable; //return the Hashtable object constructor.
})();

The optimum functionality for your application will probably lye
somewhere in-between the two.

Richard.

[Douglas Crockford]

Re: Array as hash tables

>>If the values in your object (or for the boobs, hash) are anything[color=blue][color=green]
>>but functions, you can use
>>
>>(typeof color[string] != 'function')
>>
>>to discriminate your values from the Object methods.
>>
>>By the way, I think this was a design error in JavaScript. The
>>appearance of those methods complicates the use of objects as
>>collections .[/color]
>
>
> I wonder too. Was not the dontEnum attribute a last minute and
> incomplete workaround for this ?[/color]

The problem with dontEnum is that it didn't make it into the language;
it is only in the implementation. It only controls the results of
for..in, so it does not help you in this case, anyway.
[color=blue]
> May I suggest my definitive and foolproof hash. Call it Collection, for
> VB boobs:
>
> function Collection()
> {
> this.constructo r = undefined;
> Collection.prot otype = undefined;
> }
>
> Is it enough clobbering ?[/color]

No. The [[prototype]] property is the key one, and it is still there.
Clobbering is not effective. You will still see the Object methods (but
there are fewer of them than there are Array methods).

Something that might work is

function Collection() {}
Collection.prot otype = {constructor: null, toString: null,
prototype: null};

http://www.crockford.com/#javascript

[Lasse Reichstein Nielsen]

Re: Array as hash tables

Douglas Crockford <nospam@covad.n et> writes:
[color=blue]
> Something that might work is
>
> function Collection() {}
> Collection.prot otype = {constructor: null, toString: null,
> prototype: null};[/color]

A new object created from "new Collection()" will not have a "prototype"
property, so "prototype: null" is not needed.

The full monty would be:
---
function Collection(){}
Collection.prot otype = {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnume rable: undefined
};
---
However, there is no need for the Collection *constructor* then. When
you just need an empty collection, you can create a new one directly:

---
function createCollectio n() {
return {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnume rable: undefined
};
}
---

(Ofcourse, some implementations might have other, non-standard,
properties on Object.prototyp e :)

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

[John G Harris]

Re: Array as hash tables

In article <9519154a.04080 60544.14999064@ posting.google. com>, Alexis
Nikichine <alexis.nikichi ne@free.fr> writes

<snip>[color=blue]
>I finally came to use the following as a naked object, to use as a
>hashtable:[/color]
<snip>

Why do you call it a hashtable? It could just as easily be a balanced
tree or even a simple list. You wouldn't be able to tell the difference.

If you want to be posh, and accurate too, call it an associative array.
If you want to be less posh you could call it a map.

John
--
John Harris

[Richard Cornford]

Re: Array as hash tables

Lasse Reichstein Nielsen wrote:
<snip>[color=blue]
> (Ofcourse, some implementations might have other,
> non-standard, properties on Object.prototyp e :)[/color]

Such as Mozilla:-

__defineGetter_ _
__defineSetter_ _
__parent__
__proto__
eval
toSource
unwatch
watch

Richard.

[Douglas Crockford]

Re: Array as hash tables

>>I finally came to use the following as a naked object, to use as a[color=blue][color=green]
>>hashtable[/color][/color]
[color=blue]
> Why do you call it a hashtable? It could just as easily be a balanced
> tree or even a simple list. You wouldn't be able to tell the difference.
>
> If you want to be posh, and accurate too, call it an associative array.
> If you want to be less posh you could call it a map.[/color]

And if you want to be understood in a JavaScript forum, you would call
it an object.

http://www.crockford.com/javascript/javascript.html

[Yann-Erwan Perio]

Re: Array as hash tables

Richard Cornford wrote:
[color=blue][color=green]
>>(Ofcourse, some implementations might have other,
>>non-standard, properties on Object.prototyp e :)[/color]
>
>
> Such as Mozilla:-
>
> __defineGetter_ _
> __defineSetter_ _
> __parent__
> __proto__
> eval
> toSource
> unwatch
> watch[/color]

JFTR <URL:http://lxr.mozilla.org/seamonkey/source/js/src/jsobj.c#1535>
provides the last two methods : __lookupGetter_ _ and __lookupSetter_ _.


Regards,
Yep.

[rh]

Re: Array as hash tables

"Richard Cornford" wrote:
[color=blue]
> Alexis Nikichine wrote:
> <snip>[color=green]
> > The color example was just a gratuitous one. I was worrying
> > about arbitrary strings typed in by users. One day, I had
> > reports of "pop art" request failing. "pop" yielded a
> > function (instead of an expected integer).[/color]
> <snip>
>
> If you want to store key/value pairs without any restrictions to the
> names perhaps you need to implement an object for that storage.[/color]

That's unfortunate. Truthfully, this is a name-scope conflict with
genesis imbedded as a deficiency of the language (a statement made
notwithstanding the fact that JavaScript remains, by far, my favourite
progamming language). It should be possible to obtain a basic object
that is entirely clear of such name conflicts.

Given that, and ever seemingly the contrarian, I don't believe that
Alexis is that far off track in attempting to remedy the deficiency
through removal of pre-definded values in the object. The latter day
"propertyIsEnum erable" mentioned by Lasse, it seems, is a rather late,
lame fix to the language.

../rh