在这个答案的更新3中已经明确表示，这个符号:
var hash = {};
hash[X]
实际上并不散列对象X;它实际上只是将X转换为一个字符串(如果它是一个对象，则通过. tostring()，或者其他一些用于各种基本类型的内置转换)，然后在“哈希”中查找该字符串，而不散列它。对象相等性也不检查-如果两个不同的对象具有相同的字符串转换，它们将相互覆盖。
鉴于此，JavaScript中是否有有效的hashmap实现?
(例如，javascript hashmap的第二个谷歌结果对任何操作产生的实现都是O(n)。其他各种结果忽略了具有等效字符串表示的不同对象会相互覆盖这一事实。
当前回答
这是我的另一个地图实现。使用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
*/
其他回答
现在有一些非常好的外部库解决方案:
collections.js Immutable.js
JavaScript也有其语言提供的Map。
地图
试试我的JavaScript哈希表实现:http://www.timdown.co.uk/jshashtable
它查找关键对象的hashCode()方法，或者您可以在创建Hashtable对象时提供哈希函数。
不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似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()方法。
根据ECMAScript 2015 (ES6)，标准JavaScript有一个Map实现。更多信息可以在这里找到。
基本用法:
var myMap = new Map();
var keyString = "a string",
keyObj = {},
keyFunc = function () {};
// Setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");
myMap.size; // 3
// Getting the values
myMap.get(keyString); // "value associated with 'a string'"
myMap.get(keyObj); // "value associated with keyObj"
myMap.get(keyFunc); // "value associated with keyFunc"
您可以使用ECMAScript 6 WeakMap或Map:
weakmap是键/值映射，其中键是对象。
映射对象是简单的键/值映射。任何值(包括对象和基本值)都可以用作键或值。
请注意，这两者都没有得到广泛支持，但您可以使用ECMAScript 6 Shim(需要本地ECMAScript 5或ECMAScript 5 Shim)来支持Map，但不能使用WeakMap(请参阅原因)。
