在这个答案的更新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(请参阅原因)。
其他回答
不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似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()方法。
这是我的另一个地图实现。使用randomizer， 'generics'和'iterator' =)
var HashMap = function (TKey, TValue) {
var db = [];
var keyType, valueType;
(function () {
keyType = TKey;
valueType = TValue;
})();
var getIndexOfKey = function (key) {
if (typeof key !== keyType)
throw new Error('Type of key should be ' + keyType);
for (var i = 0; i < db.length; i++) {
if (db[i][0] == key)
return i;
}
return -1;
}
this.add = function (key, value) {
if (typeof key !== keyType) {
throw new Error('Type of key should be ' + keyType);
} else if (typeof value !== valueType) {
throw new Error('Type of value should be ' + valueType);
}
var index = getIndexOfKey(key);
if (index === -1)
db.push([key, value]);
else
db[index][1] = value;
return this;
}
this.get = function (key) {
if (typeof key !== keyType || db.length === 0)
return null;
for (var i = 0; i < db.length; i++) {
if (db[i][0] == key)
return db[i][1];
}
return null;
}
this.size = function () {
return db.length;
}
this.keys = function () {
if (db.length === 0)
return [];
var result = [];
for (var i = 0; i < db.length; i++) {
result.push(db[i][0]);
}
return result;
}
this.values = function () {
if (db.length === 0)
return [];
var result = [];
for (var i = 0; i < db.length; i++) {
result.push(db[i][1]);
}
return result;
}
this.randomize = function () {
if (db.length === 0)
return this;
var currentIndex = db.length, temporaryValue, randomIndex;
while (0 !== currentIndex) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
temporaryValue = db[currentIndex];
db[currentIndex] = db[randomIndex];
db[randomIndex] = temporaryValue;
}
return this;
}
this.iterate = function (callback) {
if (db.length === 0)
return false;
for (var i = 0; i < db.length; i++) {
callback(db[i][0], db[i][1]);
}
return true;
}
}
例子:
var a = new HashMap("string", "number");
a.add('test', 1132)
.add('test14', 666)
.add('1421test14', 12312666)
.iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/
我的“地图”实现，源自Christoph的例子:
使用示例:
var map = new Map(); // Creates an "in-memory" map
var map = new Map("storageId"); // Creates a map that is loaded/persisted using html5 storage
function Map(storageId) {
this.current = undefined;
this.size = 0;
this.storageId = storageId;
if (this.storageId) {
this.keys = new Array();
this.disableLinking();
}
}
Map.noop = function() {
return this;
};
Map.illegal = function() {
throw new Error("illegal operation for maps without linking");
};
// Map initialisation from an existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
var map = new Map;
for(var prop in obj) {
if(foreignKeys || obj.hasOwnProperty(prop))
map.put(prop, obj[prop]);
}
return map;
};
Map.prototype.disableLinking = function() {
this.link = Map.noop;
this.unlink = Map.noop;
this.disableLinking = Map.noop;
this.next = Map.illegal;
this.key = Map.illegal;
this.value = Map.illegal;
// this.removeAll = Map.illegal;
return this;
};
// Overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
};
Map.prototype.hash.current = 0;
// --- Mapping functions
Map.prototype.get = function(key) {
var item = this[this.hash(key)];
if (item === undefined) {
if (this.storageId) {
try {
var itemStr = localStorage.getItem(this.storageId + key);
if (itemStr && itemStr !== 'undefined') {
item = JSON.parse(itemStr);
this[this.hash(key)] = item;
this.keys.push(key);
++this.size;
}
} catch (e) {
console.log(e);
}
}
}
return item === undefined ? undefined : item.value;
};
Map.prototype.put = function(key, value) {
var hash = this.hash(key);
if(this[hash] === undefined) {
var item = { key : key, value : value };
this[hash] = item;
this.link(item);
++this.size;
}
else this[hash].value = value;
if (this.storageId) {
this.keys.push(key);
try {
localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
} catch (e) {
console.log(e);
}
}
return this;
};
Map.prototype.remove = function(key) {
var hash = this.hash(key);
var item = this[hash];
if(item !== undefined) {
--this.size;
this.unlink(item);
delete this[hash];
}
if (this.storageId) {
try {
localStorage.setItem(this.storageId + key, undefined);
} catch (e) {
console.log(e);
}
}
return this;
};
// Only works if linked
Map.prototype.removeAll = function() {
if (this.storageId) {
for (var i=0; i<this.keys.length; i++) {
this.remove(this.keys[i]);
}
this.keys.length = 0;
} else {
while(this.size)
this.remove(this.key());
}
return this;
};
// --- Linked list helper functions
Map.prototype.link = function(item) {
if (this.storageId) {
return;
}
if(this.size == 0) {
item.prev = item;
item.next = item;
this.current = item;
}
else {
item.prev = this.current.prev;
item.prev.next = item;
item.next = this.current;
this.current.prev = item;
}
};
Map.prototype.unlink = function(item) {
if (this.storageId) {
return;
}
if(this.size == 0)
this.current = undefined;
else {
item.prev.next = item.next;
item.next.prev = item.prev;
if(item === this.current)
this.current = item.next;
}
};
// --- Iterator functions - only work if map is linked
Map.prototype.next = function() {
this.current = this.current.next;
};
Map.prototype.key = function() {
if (this.storageId) {
return undefined;
} else {
return this.current.key;
}
};
Map.prototype.value = function() {
if (this.storageId) {
return undefined;
}
return this.current.value;
};
如果性能不是很关键(例如，键的数量相对较小)，并且你不想用额外的字段(如_hash， _id等)污染你的(或可能不是你的)对象，那么你可以利用Array.prototype.indexOf采用严格相等的事实。下面是一个简单的实现:
var Dict = (function(){
// Internet Explorer 8 and earlier does not have any Array.prototype.indexOf
function indexOfPolyfill(val) {
for (var i = 0, l = this.length; i < l; ++i) {
if (this[i] === val) {
return i;
}
}
return -1;
}
function Dict(){
this.keys = [];
this.values = [];
if (!this.keys.indexOf) {
this.keys.indexOf = indexOfPolyfill;
}
};
Dict.prototype.has = function(key){
return this.keys.indexOf(key) != -1;
};
Dict.prototype.get = function(key, defaultValue){
var index = this.keys.indexOf(key);
return index == -1 ? defaultValue : this.values[index];
};
Dict.prototype.set = function(key, value){
var index = this.keys.indexOf(key);
if (index == -1) {
this.keys.push(key);
this.values.push(value);
} else {
var prevValue = this.values[index];
this.values[index] = value;
return prevValue;
}
};
Dict.prototype.delete = function(key){
var index = this.keys.indexOf(key);
if (index != -1) {
this.keys.splice(index, 1);
return this.values.splice(index, 1)[0];
}
};
Dict.prototype.clear = function(){
this.keys.splice(0, this.keys.length);
this.values.splice(0, this.values.length);
};
return Dict;
})();
用法示例:
var a = {}, b = {},
c = { toString: function(){ return '1'; } },
d = 1, s = '1', u = undefined, n = null,
dict = new Dict();
// Keys and values can be anything
dict.set(a, 'a');
dict.set(b, 'b');
dict.set(c, 'c');
dict.set(d, 'd');
dict.set(s, 's');
dict.set(u, 'u');
dict.set(n, 'n');
dict.get(a); // 'a'
dict.get(b); // 'b'
dict.get(s); // 's'
dict.get(u); // 'u'
dict.get(n); // 'n'
// etc.
与ECMAScript 6 WeakMap相比，它有两个问题:O(n)搜索时间和非弱(即如果不使用delete或clear释放键会导致内存泄漏)。
JavaScript没有内置的map/hashmap。它应该被称为关联数组。
hash["X"]等于hash。X，但它允许“X”作为字符串变量。 换句话说，hash[x]在函数上等于eval("hash."+x. tostring())。
它更类似于object。属性而不是键值映射。 如果你在JavaScript中寻找一个更好的键/值映射，请使用Map对象。
