在这个答案的更新3中已经明确表示，这个符号:
var hash = {};
hash[X]
实际上并不散列对象X;它实际上只是将X转换为一个字符串(如果它是一个对象，则通过. tostring()，或者其他一些用于各种基本类型的内置转换)，然后在“哈希”中查找该字符串，而不散列它。对象相等性也不检查-如果两个不同的对象具有相同的字符串转换，它们将相互覆盖。
鉴于此，JavaScript中是否有有效的hashmap实现?
(例如，javascript hashmap的第二个谷歌结果对任何操作产生的实现都是O(n)。其他各种结果忽略了具有等效字符串表示的不同对象会相互覆盖这一事实。
当前回答
不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似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()方法。
其他回答
不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似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()方法。
现在有一些非常好的外部库解决方案:
collections.js Immutable.js
JavaScript也有其语言提供的Map。
地图
你必须在某些内部状态下存储对象/值对:
HashMap = function(){
this._dict = [];
}
HashMap.prototype._get = function(key){
for(var i=0, couplet; couplet = this._dict[i]; i++){
if(couplet[0] === key){
return couplet;
}
}
}
HashMap.prototype.put = function(key, value){
var couplet = this._get(key);
if(couplet){
couplet[1] = value;
}else{
this._dict.push([key, value]);
}
return this; // for chaining
}
HashMap.prototype.get = function(key){
var couplet = this._get(key);
if(couplet){
return couplet[1];
}
}
并这样使用它:
var color = {}; // Unique object instance
var shape = {}; // Unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));
当然，这个实现也类似于O(n)。Eugene的例子是获得能够以实际哈希所期望的任何速度工作的哈希的唯一方法。
另一种方法，沿着Eugene的答案，是以某种方式为所有对象附加一个唯一的ID。我最喜欢的方法之一是从Object超类继承的内置方法之一，将其替换为自定义函数传递，并将属性附加到该函数对象。如果你重写我的HashMap方法来做到这一点，它看起来像:
HashMap = function(){
this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
if(typeof key == "object"){
if(!key.hasOwnProperty._id){
key.hasOwnProperty = function(key){
return Object.prototype.hasOwnProperty.call(this, key);
}
key.hasOwnProperty._id = this._shared.id++;
}
this._dict[key.hasOwnProperty._id] = value;
}else{
this._dict[key] = value;
}
return this; // for chaining
}
HashMap.prototype.get = function get(key){
if(typeof key == "object"){
return this._dict[key.hasOwnProperty._id];
}
return this._dict[key];
}
这个版本看起来只是稍微快一点，但在理论上，对于大数据集来说，它会快得多。
您可以使用ECMAScript 6 WeakMap或Map:
weakmap是键/值映射，其中键是对象。
映射对象是简单的键/值映射。任何值(包括对象和基本值)都可以用作键或值。
请注意，这两者都没有得到广泛支持，但您可以使用ECMAScript 6 Shim(需要本地ECMAScript 5或ECMAScript 5 Shim)来支持Map，但不能使用WeakMap(请参阅原因)。
这是我的另一个地图实现。使用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
*/
