试试我的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()方法。

我已经实现了一个JavaScript HashMap，其代码可以从http://github.com/lambder/HashMapJS/tree/master获得

代码如下:

/*
 =====================================================================
 @license MIT
 @author Lambder
 @copyright 2009 Lambder.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   Maps value to key returning previous association
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   Returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   Deletes association by given key.
   Returns true if the association existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// Creation

var my_map = new HashMap();

// Insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// Retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// Deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}

问题描述

JavaScript没有内置的通用映射类型(有时称为关联数组或字典)，允许通过任意键访问任意值。JavaScript的基本数据结构是对象，这是一种特殊类型的映射，它只接受字符串作为键，并具有特殊的语义，如原型继承、getter和setter以及一些进一步的巫术。

当使用对象作为映射时，你必须记住键将通过toString()转换为字符串值，这将导致将5和'5'映射到相同的值，并且所有没有覆盖toString()方法的对象都映射到'[object object]'索引的值。如果不检查hasOwnProperty()，您可能还会不由自主地访问其继承的属性。

JavaScript内置的数组类型一点帮助都没有:JavaScript数组不是关联数组，而只是具有一些特殊属性的对象。如果你想知道为什么它们不能用作地图，请看这里。

尤金的解决方案

Eugene Lazutkin已经描述了使用自定义哈希函数生成唯一字符串的基本思想，这些字符串可用于作为字典对象的属性查找相关值。这很可能是最快的解决方案，因为对象在内部实现为哈希表。

注意:哈希表(有时称为哈希映射)是映射概念的一种特殊实现，它使用一个支持数组，并通过数值哈希值进行查找。运行时环境可能使用其他结构(如搜索树或跳过列表)来实现JavaScript对象，但由于对象是基本的数据结构，因此应该对它们进行充分优化。

为了获得任意对象的唯一哈希值，一种可能是使用全局计数器并在对象本身中缓存哈希值(例如，在名为__hash的属性中)。

这样做的哈希函数是并且对基本值和对象都有效:

function hash(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
}

hash.current = 0;

这个函数可以像Eugene描述的那样使用。为了方便起见，我们将它进一步包装在Map类中。

我的地图实现

下面的实现将额外地将键-值对存储在双链表中，以便对键和值进行快速迭代。要提供自己的哈希函数，可以在创建实例后重写实例的hash()方法。

// Linking the key-value-pairs is optional.
// If no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        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)];
    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;

    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];
    }

    return this;
};

// Only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- Linked list helper functions

Map.prototype.link = function(item) {
    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.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() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

例子

下面的脚本，

var map = new Map;

map.put('spam', 'eggs').
    put('foo', 'bar').
    put('foo', 'baz').
    put({}, 'an object').
    put({}, 'another object').
    put(5, 'five').
    put(5, 'five again').
    put('5', 'another five');

for(var i = 0; i++ < map.size; map.next())
    document.writeln(map.hash(map.key()) + ' : ' + map.value());

生成以下输出:

string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five

进一步的考虑

PEZ建议重写toString()方法，大概是用我们的哈希函数。这是不可行的，因为它不适用于基本值(为基本值更改toString()是一个非常糟糕的主意)。如果希望toString()为任意对象返回有意义的值，则必须修改Object。原型，有些人(不包括我自己)认为这是禁止的。

我的地图实现的当前版本以及其他JavaScript好东西可以从这里获得。

这是我的另一个地图实现。使用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
*/

下面是一种使用类似Java映射的简单而方便的方法:

var map = {
              'map_name_1': map_value_1,
              'map_name_2': map_value_2,
              'map_name_3': map_value_3,
              'map_name_4': map_value_4
          }

为了得到值:

alert(map['map_name_1']);    // Gives the value of map_value_1

... etc. ...