Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Javascript > Array as hash tables

Reply
Thread Tools

Array as hash tables

 
 
Alexis Nikichine
Guest
Posts: n/a
 
      08-06-2004
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" ("constructor", "length", etc...)

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

function HashTable() { this.constructor = 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
 
Reply With Quote
 
 
 
 
Douglas Crockford
Guest
Posts: n/a
 
      08-06-2004
Alexis Nikichine wrote:

> 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" ("constructor", "length", etc...)
>
> I finally came to use the following as a naked object, to use as a
> hashtable:
>
> function HashTable() { this.constructor = 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,


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
 
Reply With Quote
 
 
 
 
Alexis Nikichine
Guest
Posts: n/a
 
      08-06-2004
Douglas Crockford wrote:

> 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

[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).

> 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";
> }


When I first met the, I used type discipline, and made sure that the
returned value was an integer.

> 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.


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 "constructor".

Which is why I am asking: is my HashTable a really really empty
Object/Function, once the "constructor" 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!
 
Reply With Quote
 
Douglas Crockford
Guest
Posts: n/a
 
      08-06-2004
>>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

>
> [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).
>
>
>>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";
>>}

>
>
> When I first met the, I used type discipline, and made sure that the
> returned value was an integer.
>
>
>>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.

>
>
> 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 "constructor".
>
> Which is why I am asking: is my HashTable a really really empty
> Object/Function, once the "constructor" member has been blanked ?


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
 
Reply With Quote
 
Alexis Nikichine
Guest
Posts: n/a
 
      08-06-2004
> > With a plain Object, I will get an unexpected result on
> > "constructor".
> >
> > Which is why I am asking: is my HashTable a really really empty
> > Object/Function, once the "constructor" member has been blanked ?

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


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 ?

> 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.


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.constructor = undefined;
Collection.prototype = 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!
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      08-06-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (Alexis Nikichine) writes:

> It is common knowledge that arrays can be used as hashtables:
>
> var color = [];
>
> color["red"] = 0xFF0000;
> color["blue"] = 0x0000FF;


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;

> With this, I can check whether a string identifies a color, or not:
>
> function isColor(string)
> {
> return color[string] == undefined;


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.undefined = window.undefined;
or you could use
return (typeof color[string]) == "undefined";

> My only concern is that
>
> isColor("pop") == true
>
> and that will hold true for quite a few annoying, parasitic,
> "keywords" ("constructor", "length", etc...)


Fewer if using objects instead of arrays, but still some (e.g. toString).

> I finally came to use the following as a naked object, to use as a
> hashtable:
>
> function HashTable() { this.constructor = undefined; }
>
> // example of use:
> var color = new HashTable;
> color["red"] = 0xFF0000


Yes. That's just a plain object as well, with no properties except
those inherited from Object.prototype (and even with "constructor"
removed).

> 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 ?


According to ECMA 262 v3 section 5.2.4:
toString, toLocaleString, valueOf, hasOwnProperty, isPrototypeOf,
propertyIsEnumerable.
(you overwrote "constructor", otherwise it would be there too).

> Any help appreciated,


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.hasOwnProperty(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 - (E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      08-06-2004
Douglas Crockford <(E-Mail Removed)> writes:

> 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.


It has been somehow mitigated by later additions to, of all things,
Object.prototype .

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

propName in objectRef && !objectRef.propertyIsEnumerable(propName)

(or, if only adding to one object an not inheriting from it:
objectRef.hasOwnProperty(propName)
)
/L
--
Lasse Reichstein Nielsen - (E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Richard Cornford
Guest
Posts: n/a
 
      08-06-2004
Alexis Nikichine wrote:
<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).

<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(arrNm, activeEnum, keysToIndex){
var lastIndex = null;
var enumIndex = 0;
while(typeof activeEnum[enumIndex] == 'number'){enumIndex++;}
activeEnum[enumIndex] = 0;
this.hasNext = this.hasMoreElements = function(){
if(activeEnum[enumIndex] < keysToIndex.tableLength){
return true;
}else{
if(typeof activeEnum[enumIndex] == 'number'){
activeEnum[enumIndex] = null;
}
return false;
}
};
this.next = this.nextElement = function(){
if(this.hasNext()){
lastIndex = activeEnum[enumIndex];
return keysToIndex[arrNm][activeEnum[enumIndex]++];
}else{
return null;
}
};
this.remove = function(){
if(typeof lastIndex == 'number'){
removeItem(keysToIndex._indexToKeys[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.tableLength--;
for(var c = remIndex;c < keysToIndex.tableLength;c++){
keysToIndex._indexToValue[c] =
keysToIndex._indexToValue[c+1];
keyAdj[1] = (keysToIndex._indexToKeys[c] =
keysToIndex._indexToKeys[c+1]);
keysToIndex[keyAdj.join('')] = c;
}
keysToIndex._indexToValue.length = keysToIndex.tableLength;
for(var c = activeEnum.length;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._indexToValue[keysToIndex[key]];
}else{
return null;
}
};
this.put = function(key, value){
keyAdj[1] = key;
var sKey = keyAdj.join('');
if(typeof keysToIndex[sKey] == 'number'){
keysToIndex._indexToValue[keysToIndex[sKey]] = value;
}else{
keysToIndex[sKey] = keysToIndex.tableLength;
keysToIndex._indexToValue[keysToIndex.tableLength] = value;
keysToIndex._indexToKeys[keysToIndex.tableLength++] = key;
}
};
this.remove = function(key){
removeItem(key, keysToIndex, activeEnum);
};
this.containsKey = function(key){
keyAdj[1] = key;
return (typeof keysToIndex[keyAdj.join('')] == 'number');
};
this.size = function(){return keysToIndex.tableLength;};
this.elements = function(){
return new Enumeration('_indexToValue',activeEnum, keysToIndex);
};
this.keys = function(){
return new Enumeration('_indexToKeys', activeEnum, keysToIndex);
};
}
HTable.prototype.clear = function(){
var e = this.keys();
while(e.hasNext()){
this.remove(e.next());
}
};
HTable.prototype.toString = function(){
var k,e = this.keys();
var st = '';
while(e.hasNext()){
k = e.next();
st += k+' = '+this.get(k)+'\n';
}
return st;
};
HTable.prototype.containsValue =
(HTable.prototype.contains = function(testVal){
var v,e = this.elements();
while(e.hasNext()){
v = e.next();
if(v === testVal){
//if((v == testVal)&&(typeof v == typeof testVal)){
return true;
}
}
return false;
});
HTable.prototype.isEmpty = function(){
return (this.size() == 0);
};
HTable.prototype.putAll = function(hTable){
if((typeof hTable == 'object')&&
(hTable.constructor == HTable)){
var n,e = hTable.keys();
while(e.hasNext()){
n = e.next();
this.put(n, hTable.get(n));
}
}
return this;
};
HTable.prototype.clone = function(){
return new HTable().putAll(this);
};
HTable.prototype.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.


 
Reply With Quote
 
Douglas Crockford
Guest
Posts: n/a
 
      08-06-2004
>>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.

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


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.

> May I suggest my definitive and foolproof hash. Call it Collection, for
> VB boobs:
>
> function Collection()
> {
> this.constructor = undefined;
> Collection.prototype = undefined;
> }
>
> Is it enough clobbering ?


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.prototype = {constructor: null, toString: null,
prototype: null};

http://www.crockford.com/#javascript
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      08-06-2004
Douglas Crockford <(E-Mail Removed)> writes:

> Something that might work is
>
> function Collection() {}
> Collection.prototype = {constructor: null, toString: null,
> prototype: null};


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.prototype = {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnumerable: 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 createCollection() {
return {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnumerable: undefined
};
}
---

(Ofcourse, some implementations might have other, non-standard,
properties on Object.prototype

/L
--
Lasse Reichstein Nielsen - (E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
building an array of hash tables. Ted Flethuseo Ruby 1 07-26-2010 01:16 AM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
Benchmark segfault [Was: Array#inject to create a hash versus Hash[*array.collect{}.flatten] ] Michal Suchanek Ruby 6 06-13-2007 04:40 AM
Array#inject to create a hash versus Hash[*array.collect{}.flatten] -- Speed, segfault Anthony Martinez Ruby 4 06-11-2007 08:16 AM



Advertisments