在这个答案的更新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(请参阅原因)。

其他回答

自己手动散列对象,并将结果字符串用作常规JavaScript字典的键。毕竟,你最清楚是什么让你的对象独一无二。我就是这么做的。

例子:

var key = function(obj){
  // Some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // Just an example
};

var dict = {};

dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;

这样你就可以通过JavaScript控制索引,而不需要大量的内存分配和溢出处理。

当然,如果你真的想要“工业级的解决方案”,你可以构建一个由键函数参数化的类,并使用容器的所有必要API,但是……我们使用JavaScript,并尝试简单和轻量级,所以这个功能解决方案简单而快速。

键函数可以简单到选择对象的正确属性,例如,一个键或一组已经是唯一的键,一个键的组合,它们在一起是唯一的,或者复杂到使用一些加密散列,如DojoX编码或DojoX UUID。虽然后一种解决方案可能会产生唯一的键,但就我个人而言,我会尽量避免使用它们,特别是如果我知道是什么使我的对象唯一的话。

2014年更新:早在2008年,这个简单的解决方案仍然需要更多的解释。让我用问答的形式来阐明这个观点。

你的解决方案并没有真正的哈希值。它在哪里??

JavaScript是一种高级语言。它的基本元素(Object)包括一个哈希表来保存属性。为了提高效率,这个哈希表通常是用低级语言编写的。使用一个简单的对象与字符串键,我们使用一个有效实现的哈希表,而不需要任何努力。

你怎么知道他们用了哈希?

有三种主要的方法来保持一个对象集合的可寻址键:

无序。在这种情况下,通过键来检索对象,我们必须遍历所有在我们找到它时停止的键。平均需要n/2次比较。 命令。 例子#1:一个排序的数组——做一个二分搜索,我们将在平均~log2(n)比较后找到我们的键。好多了。 例2:一棵树。还是要尝试~log(n)次。 哈希表。平均来说,它需要常数时间。比较:O(n) vs O(log n) vs O(1)。繁荣。

显然,JavaScript对象以某种形式使用哈希表来处理一般情况。

浏览器厂商真的使用哈希表吗??

真的。

Chrome / node . js / V8: JSObject。寻找 NameDictionary和 NameDictionaryShape与 相关细节在objects.cc中 和objects-inl.h。 Firefox /壁虎: JSObject, NativeObject, 带有相关细节的PlainObject jsobj.cpp和 vm / NativeObject.cpp。

他们处理碰撞吗?

是的。见上图。如果你发现不相等的字符串发生碰撞,请毫不犹豫地向供应商提交错误。

你的想法是什么?

如果您想对一个对象进行哈希,请找到使它唯一的原因并将其用作键。不要尝试计算真正的哈希或模拟哈希表——底层JavaScript对象已经有效地处理了。

将此键与JavaScript的Object一起使用,可以利用其内置哈希表,同时避免与默认属性发生冲突。

下面的例子让你开始学习:

If your objects include a unique user name — use it as a key. If it includes a unique customer number — use it as a key. If it includes unique government-issued numbers like US SSNs, or a passport number, and your system doesn't allow duplicates — use it as a key. If a combination of fields is unique — use it as a key. US state abbreviation + driver license number makes an excellent key. Country abbreviation + passport number is an excellent key too. Some function on fields, or a whole object, can return a unique value — use it as a key.

我采用了您的建议,并使用用户名缓存所有对象。但是一些聪明的家伙被命名为“toString”,这是一个内置属性!我现在该怎么办?

显然,如果产生的键完全由拉丁字符组成的可能性很小,那么您应该采取一些措施。例如,在开头或结尾添加任何你喜欢的非拉丁Unicode字符,以消除与默认属性的冲突:"#toString", "#MarySmith"。如果使用复合键,则使用某种非拉丁分隔符分隔键组件:“name,city,state”。

一般来说,这是我们必须发挥创意的地方,在给定的限制(唯一性,与默认属性的潜在冲突)下选择最简单的键。

注意:根据定义,唯一键不冲突,而潜在的哈希冲突将由底层对象处理。

你为什么不喜欢工业解决方案?

恕我直言,最好的代码根本就是没有代码:它没有错误,不需要维护,易于理解,并且可以立即执行。我看到的所有“JavaScript哈希表”都是100行代码,并且涉及多个对象。将其与:dict[key] = value进行比较。

另一点:使用JavaScript和相同的原始对象来实现已经实现的内容,是否有可能击败用低级语言编写的原始对象的性能?

我仍然想在没有任何键的情况下散列我的对象!

我们很幸运:ECMAScript 6(2015年6月发布)定义了map和set。

根据定义判断,它们可以使用对象的地址作为键,这使得对象在没有人工键的情况下立即区别开来。OTOH,两个不同但完全相同的对象,将被映射为不同的对象。

来自MDN的比较分解:

Objects are similar to Maps in that both let you set keys to values, retrieve those values, delete keys, and detect whether something is stored at a key. Because of this (and because there were no built-in alternatives), Objects have been used as Maps historically; however, there are important differences that make using a Map preferable in certain cases: The keys of an Object are Strings and Symbols, whereas they can be any value for a Map, including functions, objects, and any primitive. The keys in Map are ordered while keys added to object are not. Thus, when iterating over it, a Map object returns keys in order of insertion. You can get the size of a Map easily with the size property, while the number of properties in an Object must be determined manually. A Map is an iterable and can thus be directly iterated, whereas iterating over an Object requires obtaining its keys in some fashion and iterating over them. An Object has a prototype, so there are default keys in the map that could collide with your keys if you're not careful. As of ES5 this can be bypassed by using map = Object.create(null), but this is seldom done. A Map may perform better in scenarios involving frequent addition and removal of key pairs.

我已经实现了一个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")
}

在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键是不可枚举的(也就是说,没有方法给你一个键的列表)。

试试我的JavaScript哈希表实现:http://www.timdown.co.uk/jshashtable

它查找关键对象的hashCode()方法,或者您可以在创建Hashtable对象时提供哈希函数。

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