在这个答案的更新3中已经明确表示，这个符号:
var hash = {};
hash[X]
实际上并不散列对象X;它实际上只是将X转换为一个字符串(如果它是一个对象，则通过. tostring()，或者其他一些用于各种基本类型的内置转换)，然后在“哈希”中查找该字符串，而不散列它。对象相等性也不检查-如果两个不同的对象具有相同的字符串转换，它们将相互覆盖。
鉴于此，JavaScript中是否有有效的hashmap实现?
(例如，javascript hashmap的第二个谷歌结果对任何操作产生的实现都是O(n)。其他各种结果忽略了具有等效字符串表示的不同对象会相互覆盖这一事实。
当前回答
您可以使用ECMAScript 6 WeakMap或Map:
weakmap是键/值映射，其中键是对象。
映射对象是简单的键/值映射。任何值(包括对象和基本值)都可以用作键或值。
请注意，这两者都没有得到广泛支持，但您可以使用ECMAScript 6 Shim(需要本地ECMAScript 5或ECMAScript 5 Shim)来支持Map，但不能使用WeakMap(请参阅原因)。
其他回答
现在有一些非常好的外部库解决方案:
collections.js Immutable.js
JavaScript也有其语言提供的Map。
地图
JavaScript没有内置的map/hashmap。它应该被称为关联数组。
hash["X"]等于hash。X，但它允许“X”作为字符串变量。 换句话说，hash[x]在函数上等于eval("hash."+x. tostring())。
它更类似于object。属性而不是键值映射。 如果你在JavaScript中寻找一个更好的键/值映射，请使用Map对象。
在ECMAScript 6中，你可以使用WeakMap。
例子:
var wm1 = new WeakMap(),
wm2 = new WeakMap(),
wm3 = new WeakMap();
var o1 = {},
o2 = function(){},
o3 = window;
wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // A value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // Keys and values can be any objects. Even WeakMaps!
wm1.get(o2); // "azerty"
wm2.get(o2); // Undefined, because there is no value for o2 on wm2
wm2.get(o3); // Undefined, because that is the set value
wm1.has(o2); // True
wm2.has(o2); // False
wm2.has(o3); // True (even if the value itself is 'undefined')
wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // Undefined, because wm3 was cleared and there is no value for o1 anymore
wm1.has(o1); // True
wm1.delete(o1);
wm1.has(o1); // False
But:
因为引用是弱的，WeakMap键是不可枚举的(也就是说，没有方法给你一个键的列表)。
添加另一个解决方案:HashMap几乎是我从Java移植到JavaScript的第一个类。可以说有很多开销，但是实现几乎100%等于Java的实现，并且包含了所有的接口和子类。
该项目可以在这里找到:https://github.com/Airblader/jsava 我还将附加HashMap类的(当前)源代码，但正如前面所述，它还取决于超类等。所使用的面向对象框架是qooxdoo。
请注意，这段代码已经过时，请参考GitHub项目了解当前的工作。在撰写本文时，还有一个ArrayList实现。
qx.Class.define( 'jsava.util.HashMap', {
extend: jsava.util.AbstractMap,
implement: [jsava.util.Map, jsava.io.Serializable, jsava.lang.Cloneable],
construct: function () {
var args = Array.prototype.slice.call( arguments ),
initialCapacity = this.self( arguments ).DEFAULT_INITIAL_CAPACITY,
loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
switch( args.length ) {
case 1:
if( qx.Class.implementsInterface( args[0], jsava.util.Map ) ) {
initialCapacity = Math.max( ((args[0].size() / this.self( arguments ).DEFAULT_LOAD_FACTOR) | 0) + 1,
this.self( arguments ).DEFAULT_INITIAL_CAPACITY );
loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
} else {
initialCapacity = args[0];
}
break;
case 2:
initialCapacity = args[0];
loadFactor = args[1];
break;
}
if( initialCapacity < 0 ) {
throw new jsava.lang.IllegalArgumentException( 'Illegal initial capacity: ' + initialCapacity );
}
if( initialCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
initialCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
}
if( loadFactor <= 0 || isNaN( loadFactor ) ) {
throw new jsava.lang.IllegalArgumentException( 'Illegal load factor: ' + loadFactor );
}
var capacity = 1;
while( capacity < initialCapacity ) {
capacity <<= 1;
}
this._loadFactor = loadFactor;
this._threshold = (capacity * loadFactor) | 0;
this._table = jsava.JsavaUtils.emptyArrayOfGivenSize( capacity, null );
this._init();
},
statics: {
serialVersionUID: 1,
DEFAULT_INITIAL_CAPACITY: 16,
MAXIMUM_CAPACITY: 1 << 30,
DEFAULT_LOAD_FACTOR: 0.75,
_hash: function (hash) {
hash ^= (hash >>> 20) ^ (hash >>> 12);
return hash ^ (hash >>> 7) ^ (hash >>> 4);
},
_indexFor: function (hashCode, length) {
return hashCode & (length - 1);
},
Entry: qx.Class.define( 'jsava.util.HashMap.Entry', {
extend: jsava.lang.Object,
implement: [jsava.util.Map.Entry],
construct: function (hash, key, value, nextEntry) {
this._value = value;
this._next = nextEntry;
this._key = key;
this._hash = hash;
},
members: {
_key: null,
_value: null,
/** @type jsava.util.HashMap.Entry */
_next: null,
/** @type Number */
_hash: 0,
getKey: function () {
return this._key;
},
getValue: function () {
return this._value;
},
setValue: function (newValue) {
var oldValue = this._value;
this._value = newValue;
return oldValue;
},
equals: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.HashMap.Entry ) ) {
return false;
}
/** @type jsava.util.HashMap.Entry */
var entry = obj,
key1 = this.getKey(),
key2 = entry.getKey();
if( key1 === key2 || (key1 !== null && key1.equals( key2 )) ) {
var value1 = this.getValue(),
value2 = entry.getValue();
if( value1 === value2 || (value1 !== null && value1.equals( value2 )) ) {
return true;
}
}
return false;
},
hashCode: function () {
return (this._key === null ? 0 : this._key.hashCode()) ^
(this._value === null ? 0 : this._value.hashCode());
},
toString: function () {
return this.getKey() + '=' + this.getValue();
},
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
_recordAccess: function (map) {
},
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
_recordRemoval: function (map) {
}
}
} )
},
members: {
/** @type jsava.util.HashMap.Entry[] */
_table: null,
/** @type Number */
_size: 0,
/** @type Number */
_threshold: 0,
/** @type Number */
_loadFactor: 0,
/** @type Number */
_modCount: 0,
/** @implements jsava.util.Set */
__entrySet: null,
/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
* after HashMap has been initialized but before any entries have
* been inserted. (In the absence of this method, readObject would
* require explicit knowledge of subclasses.)
*/
_init: function () {
},
size: function () {
return this._size;
},
isEmpty: function () {
return this._size === 0;
},
get: function (key) {
if( key === null ) {
return this.__getForNullKey();
}
var hash = this.self( arguments )._hash( key.hashCode() );
for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash && ((k = entry._key) === key || key.equals( k )) ) {
return entry._value;
}
}
return null;
},
__getForNullKey: function () {
for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
if( entry._key === null ) {
return entry._value;
}
}
return null;
},
containsKey: function (key) {
return this._getEntry( key ) !== null;
},
_getEntry: function (key) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() );
for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash
&& ( ( k = entry._key ) === key || ( key !== null && key.equals( k ) ) ) ) {
return entry;
}
}
return null;
},
put: function (key, value) {
if( key === null ) {
return this.__putForNullKey( value );
}
var hash = this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length );
for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash && ( (k = entry._key) === key || key.equals( k ) ) ) {
var oldValue = entry._value;
entry._value = value;
entry._recordAccess( this );
return oldValue;
}
}
this._modCount++;
this._addEntry( hash, key, value, i );
return null;
},
__putForNullKey: function (value) {
for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
if( entry._key === null ) {
var oldValue = entry._value;
entry._value = value;
entry._recordAccess( this );
return oldValue;
}
}
this._modCount++;
this._addEntry( 0, null, value, 0 );
return null;
},
__putForCreate: function (key, value) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length );
for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
/** @type jsava.lang.Object */
var k;
if( entry._hash === hash
&& ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
entry._value = value;
return;
}
}
this._createEntry( hash, key, value, i );
},
__putAllForCreate: function (map) {
var iterator = map.entrySet().iterator();
while( iterator.hasNext() ) {
var entry = iterator.next();
this.__putForCreate( entry.getKey(), entry.getValue() );
}
},
_resize: function (newCapacity) {
var oldTable = this._table,
oldCapacity = oldTable.length;
if( oldCapacity === this.self( arguments ).MAXIMUM_CAPACITY ) {
this._threshold = Number.MAX_VALUE;
return;
}
var newTable = jsava.JsavaUtils.emptyArrayOfGivenSize( newCapacity, null );
this._transfer( newTable );
this._table = newTable;
this._threshold = (newCapacity * this._loadFactor) | 0;
},
_transfer: function (newTable) {
var src = this._table,
newCapacity = newTable.length;
for( var j = 0; j < src.length; j++ ) {
var entry = src[j];
if( entry !== null ) {
src[j] = null;
do {
var next = entry._next,
i = this.self( arguments )._indexFor( entry._hash, newCapacity );
entry._next = newTable[i];
newTable[i] = entry;
entry = next;
} while( entry !== null );
}
}
},
putAll: function (map) {
var numKeyToBeAdded = map.size();
if( numKeyToBeAdded === 0 ) {
return;
}
if( numKeyToBeAdded > this._threshold ) {
var targetCapacity = (numKeyToBeAdded / this._loadFactor + 1) | 0;
if( targetCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
targetCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
}
var newCapacity = this._table.length;
while( newCapacity < targetCapacity ) {
newCapacity <<= 1;
}
if( newCapacity > this._table.length ) {
this._resize( newCapacity );
}
}
var iterator = map.entrySet().iterator();
while( iterator.hasNext() ) {
var entry = iterator.next();
this.put( entry.getKey(), entry.getValue() );
}
},
remove: function (key) {
var entry = this._removeEntryForKey( key );
return entry === null ? null : entry._value;
},
_removeEntryForKey: function (key) {
var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length ),
prev = this._table[i],
entry = prev;
while( entry !== null ) {
var next = entry._next,
/** @type jsava.lang.Object */
k;
if( entry._hash === hash
&& ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
this._modCount++;
this._size--;
if( prev === entry ) {
this._table[i] = next;
} else {
prev._next = next;
}
entry._recordRemoval( this );
return entry;
}
prev = entry;
entry = next;
}
return entry;
},
_removeMapping: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
return null;
}
/** @implements jsava.util.Map.Entry */
var entry = obj,
key = entry.getKey(),
hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
i = this.self( arguments )._indexFor( hash, this._table.length ),
prev = this._table[i],
e = prev;
while( e !== null ) {
var next = e._next;
if( e._hash === hash && e.equals( entry ) ) {
this._modCount++;
this._size--;
if( prev === e ) {
this._table[i] = next;
} else {
prev._next = next;
}
e._recordRemoval( this );
return e;
}
prev = e;
e = next;
}
return e;
},
clear: function () {
this._modCount++;
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
table[i] = null;
}
this._size = 0;
},
containsValue: function (value) {
if( value === null ) {
return this.__containsNullValue();
}
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
for( var entry = table[i]; entry !== null; entry = entry._next ) {
if( value.equals( entry._value ) ) {
return true;
}
}
}
return false;
},
__containsNullValue: function () {
var table = this._table;
for( var i = 0; i < table.length; i++ ) {
for( var entry = table[i]; entry !== null; entry = entry._next ) {
if( entry._value === null ) {
return true;
}
}
}
return false;
},
clone: function () {
/** @type jsava.util.HashMap */
var result = null;
try {
result = this.base( arguments );
} catch( e ) {
if( !qx.Class.isSubClassOf( e.constructor, jsava.lang.CloneNotSupportedException ) ) {
throw e;
}
}
result._table = jsava.JsavaUtils.emptyArrayOfGivenSize( this._table.length, null );
result.__entrySet = null;
result._modCount = 0;
result._size = 0;
result._init();
result.__putAllForCreate( this );
return result;
},
_addEntry: function (hash, key, value, bucketIndex) {
var entry = this._table[bucketIndex];
this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
if( this._size++ >= this._threshold ) {
this._resize( 2 * this._table.length );
}
},
_createEntry: function (hash, key, value, bucketIndex) {
var entry = this._table[bucketIndex];
this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
this._size++;
},
keySet: function () {
var keySet = this._keySet;
return keySet !== null ? keySet : ( this._keySet = new this.KeySet( this ) );
},
values: function () {
var values = this._values;
return values !== null ? values : ( this._values = new this.Values( this ) );
},
entrySet: function () {
return this.__entrySet0();
},
__entrySet0: function () {
var entrySet = this.__entrySet;
return entrySet !== null ? entrySet : ( this.__entrySet = new this.EntrySet( this ) );
},
/** @private */
HashIterator: qx.Class.define( 'jsava.util.HashMap.HashIterator', {
extend: jsava.lang.Object,
implement: [jsava.util.Iterator],
type: 'abstract',
/** @protected */
construct: function (thisHashMap) {
this.__thisHashMap = thisHashMap;
this._expectedModCount = this.__thisHashMap._modCount;
if( this.__thisHashMap._size > 0 ) {
var table = this.__thisHashMap._table;
while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
// do nothing
}
}
},
members: {
__thisHashMap: null,
/** @type jsava.util.HashMap.Entry */
_next: null,
/** @type Number */
_expectedModCount: 0,
/** @type Number */
_index: 0,
/** @type jsava.util.HashMap.Entry */
_current: null,
hasNext: function () {
return this._next !== null;
},
_nextEntry: function () {
if( this.__thisHashMap._modCount !== this._expectedModCount ) {
throw new jsava.lang.ConcurrentModificationException();
}
var entry = this._next;
if( entry === null ) {
throw new jsava.lang.NoSuchElementException();
}
if( (this._next = entry._next) === null ) {
var table = this.__thisHashMap._table;
while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
// do nothing
}
}
this._current = entry;
return entry;
},
remove: function () {
if( this._current === null ) {
throw new jsava.lang.IllegalStateException();
}
if( this.__thisHashMap._modCount !== this._expectedModCount ) {
throw new jsava.lang.ConcurrentModificationException();
}
var key = this._current._key;
this._current = null;
this.__thisHashMap._removeEntryForKey( key );
this._expectedModCount = this.__thisHashMap._modCount;
}
}
} ),
_newKeyIterator: function () {
return new this.KeyIterator( this );
},
_newValueIterator: function () {
return new this.ValueIterator( this );
},
_newEntryIterator: function () {
return new this.EntryIterator( this );
},
/** @private */
ValueIterator: qx.Class.define( 'jsava.util.HashMap.ValueIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry()._value;
}
}
} ),
/** @private */
KeyIterator: qx.Class.define( 'jsava.util.HashMap.KeyIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry().getKey();
}
}
} ),
/** @private */
EntryIterator: qx.Class.define( 'jsava.util.HashMap.EntryIterator', {
extend: jsava.util.HashMap.HashIterator,
construct: function (thisHashMap) {
this.base( arguments, thisHashMap );
},
members: {
next: function () {
return this._nextEntry();
}
}
} ),
/** @private */
KeySet: qx.Class.define( 'jsava.util.HashMap.KeySet', {
extend: jsava.util.AbstractSet,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newKeyIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
return this.__thisHashMap.containsKey( obj );
},
remove: function (obj) {
return this.__thisHashMap._removeEntryForKey( obj ) !== null;
},
clear: function () {
this.__thisHashMap.clear();
}
}
} ),
/** @private */
Values: qx.Class.define( 'jsava.util.HashMap.Values', {
extend: jsava.util.AbstractCollection,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newValueIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
return this.__thisHashMap.containsValue( obj );
},
clear: function () {
this.__thisHashMap.clear();
}
}
} ),
/** @private */
EntrySet: qx.Class.define( 'jsava.util.HashMap.EntrySet', {
extend: jsava.util.AbstractSet,
construct: function (thisHashMap) {
this.base( arguments );
this.__thisHashMap = thisHashMap;
},
members: {
__thisHashMap: null,
iterator: function () {
return this.__thisHashMap._newEntryIterator();
},
size: function () {
return this.__thisHashMap._size;
},
contains: function (obj) {
if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
return false;
}
/** @implements jsava.util.Map.Entry */
var entry = obj,
candidate = this.__thisHashMap._getEntry( entry.getKey() );
return candidate !== null && candidate.equals( entry );
},
remove: function (obj) {
return this.__thisHashMap._removeMapping( obj ) !== null;
},
clear: function () {
this.__thisHashMap.clear();
}
}
} )
}
} );
不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似java的HashMap版本:
function HashMap() {
this.buckets = {};
}
HashMap.prototype.put = function(key, value) {
var hashCode = key.hashCode();
var bucket = this.buckets[hashCode];
if (!bucket) {
bucket = new Array();
this.buckets[hashCode] = bucket;
}
for (var i = 0; i < bucket.length; ++i) {
if (bucket[i].key.equals(key)) {
bucket[i].value = value;
return;
}
}
bucket.push({ key: key, value: value });
}
HashMap.prototype.get = function(key) {
var hashCode = key.hashCode();
var bucket = this.buckets[hashCode];
if (!bucket) {
return null;
}
for (var i = 0; i < bucket.length; ++i) {
if (bucket[i].key.equals(key)) {
return bucket[i].value;
}
}
}
HashMap.prototype.keys = function() {
var keys = new Array();
for (var hashKey in this.buckets) {
var bucket = this.buckets[hashKey];
for (var i = 0; i < bucket.length; ++i) {
keys.push(bucket[i].key);
}
}
return keys;
}
HashMap.prototype.values = function() {
var values = new Array();
for (var hashKey in this.buckets) {
var bucket = this.buckets[hashKey];
for (var i = 0; i < bucket.length; ++i) {
values.push(bucket[i].value);
}
}
return values;
}
注意:键对象必须“实现”hashCode()和equals()方法。
