Some languages implement hash tables which can use anything, not just strings, as a key. In JavaScript, you are restricted to strings and numbers. Is the lookup for this kind of implementation still O(1)? Is there an implementation in JavaScript?
Some languages implement hash tables which can use anything, not just strings, as a key. In JavaScript, you are restricted to strings and numbers. Is the lookup for this kind of implementation still O(1)? Is there an implementation in JavaScript?
Share Improve this question edited Sep 2, 2012 at 19:07 Andreas Köberle 111k58 gold badges280 silver badges307 bronze badges asked Sep 2, 2012 at 19:05 MaiaVictorMaiaVictor 53k47 gold badges157 silver badges301 bronze badges 1-
can you clarify what you meant by "Hash Objects"? Were you referring to the client side
new Object(); or var foo = {};type of object or the underlying data structure used by "the system" (e.g. C++)? – scunliffe Commented Sep 2, 2012 at 19:25
2 Answers
Reset to default 14There's obviously a lot of misunderstanding around this subject. In JavaScript, they keys of objects are actually only strings (see §8.10). Anything (including numbers) used as an object key is converted to string. Thus, obj[1] and obj["1"] are equivalent.
Internally, many JS implementations use some kind of hash table to enable quick lookup of object properties. V8 actually generates hidden C++ classes that allows lookups to execute in a single CPU instruction. Either way, it's safe to assume that object property access is fast and near O(1).
As a consequence of all object property keys being converted to string, you can only use things that convert to string as a key. Since numbers naturally convert to string, they work fine. Same for booleans. Dates work too, since Date instances convert to unique strings (although there are edge cases to be aware of).
However, objects do not convert into meaningful strings. For example:
var o = {};
o[{a:1}]='some value';
Actually results in:
o = { '[object Object]': 'some value' }
because of the string conversion rules. Since every object converts to [object Object], adding many objects as keys to another object will result in an object with only one property.
Of course, it's still possible to use an object as a key. You just have to override the default implementation of toString — in effect, creating your own hashing algorithm. For example,
function ComplexKey(a,b) {
this.a = a;
this.b = b;
}
ComplexKey.prototype.toString = function() {
return this.a + ':' + this.b;
}
var o = {};
o[new ComplexKey(1,2)] = 'x';
o[new ComplexKey(3,4)] = 'y';
Results in:
o = {
'1:2': 'x',
'3:4': 'y'
}
JavaScript does not have "hashtables".
It has Dictionaries which are collections of Key/Value pairs, with the restriction that a Key must be unique. The difference is that the implementation for a Dictionary does not imply a hash, although a Hash table will likely be used internally by implementations for performance reasons.
All objects in JavaScript function as Dictionaries (this excluded primitive types such as string and number). Generally an empty object is used for a generic "hashtable":
var o = {};
o[propExpression] = valueExpression;
However, here is the important thing: all property/key values are first converted to strings.
Thus the following are identical:
o[true] = 1
o["true"] = 1
Following through the ECMAScript is a bit confusing, but the key part to "knowing" that property names are all strings is found in Property Descriptors:
The Property Identifier type is used to associate a property name with a Property Descriptor. Values of the Property Identifier type are pairs of the form (name, descriptor), where name is a String and descriptor is a Property Descriptor value.