If you're willing to produce an alternative, I'd be interested to see it.
Of course, any meaningful performance comparison would require that both
approaches provide the same functionality.
OK, here's an alternative. After all the ballyhoo, you'll probably note
that it doesn't use "hasOwnProperty". So why not?
Well, it did to start with. I created a "hasOwnProperty" prototype to
cover off browsers that don't have that feature built-in. Then I
realized I would also have to use "apply" in the single case where
"hasOwnProperty" was a key within the hash. That was fine, too, since
apply is also relatively easy to prototype. And then I did some timing
tests, which showed it performed very well.
That was until Opera was tried, and performance turned out to be
absolutely dismal. "hasOwnProperty" performance in Opera appeared to be
at the root of the problem.
So, this.containsKey is now a very quick whack-attack at providing
performance in Opera, as well as the other browsers that were tested
(IE, Firefox, Mozilla, Netscape). While I think it's reliable within
the known pre-defined values, it shouldn't be difficult ensure the
reliability with something just slightly more innovative.
As you suggested/requested, I believe equivalent functionality should
be there. I haven't tried to do everything to the letter, e.g.,
iterator behaviour under concurrent hash changes will be different, and
undefined values are currently allowed.
My testing was concentrated on performance, and only very rudimentary
testing was done on the basic functionality. So I'm sure you'll
encounter some things that aren't quite right. On the positive side,
problems shouldn't be hard to fix, given the straightforward nature of
the implementation.
There's possibly room for further performance improvement -- e.g., I
didn't embed information in the keys (as I believe you/Richard did).
Regards,
.../rh
(ggroups will of course undo the formatting):
function Hashtable( ) {
var hash = { } ;
var hashEnum = [ ];
var size = 0, hashChangeId = 0;
this.get = function( key ) {
if ( this.containsKey( key ) ) return hash[ key ] [ 0 ];
}
this.put = function( key, value ) {
if ( ! key ) return false;
var pos = this.containsKey( key ) ? hash[key][1] :
hashEnum.length;
hash[ key ] = [ value, pos ];
size++, hashChangeId++;
hashEnum[ pos ] = key;
return true;
}
this.remove = function( key ) {
if ( ! this.containsKey( key ) ) return false;
size--, hashChangeId++;
delete hashEnum[ hash[ key ] [ 1 ] ];
delete hash[ key ];
return true;
}
this.clear = function( ) {
hash = { } ;
hashEnum.length = size = 0, hashChangeId++;
}
this.keys = function( ) {
return new Enumerator( );
}
this.values = function( ) {
return new Enumerator( true );
}
this.containsKey = function( key ) {
var val = hash[key];
if (val && ! isNaN(val[1])
&& hashEnum[val[1]] == key) return true;
return false;
}
this.size = function( ) {
return size;
}
/******************************************************************************/
function Enumerator( values ) {
var nextIndex = 0;
var id = hashChangeId;
var which = values;
this.next = function( ) {
if ( this.hasNext( ) ) return which ? hash[hashEnum[
nextIndex++ ]] [ 0 ] : hashEnum[ nextIndex++ ];
}
this.hasNext = function( ) {
if ( id != hashChangeId ) return false;
while ( ! hashEnum[ nextIndex ] && nextIndex <=
hashEnum.length ) nextIndex++;
return nextIndex < hashEnum.length;
}
}
}
/******************************************************************************/
Hashtable.prototype.toString = function( ) {
var keys = this.keys( ) , str = [ ];
while ( keys.hasNext( ) ) key = keys.next( ) , str[ str.length ] =
key + " : " + this.get( key );
return "{"+str.join( ", " ) + "}";
}
/******************************************************************************/
Hashtable.prototype.clone = function( ) {
var keys = this.keys( ) , clone = new Hashtable;
while ( keys.hasNext( ) ) key = keys.next( ) , clone.put( key,
this.get( key ) );
return clone;
}
/******************************************************************************/
Hashtable.prototype.containsValue = function( value ) {
var values = this.values( );
while ( values.hasNext( ) ) if (value === values.next( ))
return true;
return false;
}
/******************************************************************************/
Hashtable.prototype.isEmpty = function( ) {
return ! this.size( );
}
