等效的 JavaScript HashMap

Question

正如 this answer 上的更新 3 中所明确的那样，这个符号:

var hash = {};
hash[X]

实际上并没有散列对象 X ;它实际上只是转换 X到一个字符串(通过 .toString() 如果它是一个对象，或者其他一些用于各种原始类型的内置转换)，然后在“ hash”中查找该字符串，而不对其进行哈希处理。也不检查对象相等性 - 如果两个不同的对象具有相同的字符串转换，它们将相互覆盖。
鉴于此 - JavaScript 中是否有任何有效的哈希图实现？
(例如， javascript hashmap 的第二个 Google 结果产生的实现对于任何操作都是 O(n)。其他各种结果忽略了具有等效字符串表示的不同对象相互覆盖这一事实。

Answer 1

自己手动散列对象，并将结果字符串用作常规 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，并力求简单和轻量级，所以这个功能性的解决方案既简单又快速。
key 功能可以像选择对象的正确属性一样简单，例如，一个 key 或一组 key ，它们已经是唯一的， key 的组合，它们在一起是唯一的，或者像使用一些加密哈希一样复杂，例如在 DojoX encoding , 或 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 .

火狐/Gecko :
JSObject ,
NativeObject ， 和
PlainObject相关细节
jsobj.cpp和
vm/NativeObject.cpp .

他们处理碰撞吗？
是的。看上面。如果您发现不等字符串发生冲突，请不要犹豫，向供应商提交错误。
那么你的想法是什么？
如果你想散列一个对象，找到它的独特之处并将其用作键。不要试图计算一个真正的哈希或模拟哈希表——它已经被底层的 JavaScript 对象有效地处理了。
将此 key 与 JavaScript 的 Object 一起使用利用其内置的哈希表，同时避免与默认属性可能发生的冲突。
帮助您入门的示例:

如果您的对象包含唯一的用户名 - 将其用作键。

如果它包含唯一的客户编号 - 将其用作 key 。

如果它包含唯一的政府颁发的号码，如美国 SSNs ，或护照号码，并且您的系统不允许重复 - 将其用作 key 。

如果字段组合是唯一的 - 将其用作键。

美国州缩写 + 驾照号码是很好的 key 。

国家缩写+护照号码也是一个很好的关键。

字段上的某些函数或整个对象可以返回唯一值 — 将其用作键。

我使用了您的建议并使用用户名缓存了所有对象。但是有一个聪明的家伙被命名为“toString”，这是一个内置属性!我现在该怎么办？
显然，如果结果键完全由拉丁字符组成的可能性微乎其微，那么您应该对此采取一些措施。例如，在开头或结尾添加您喜欢的任何非拉丁语 Unicode 字符以取消与默认属性的冲突:“#toString”、“#MarySmith”。如果使用复合键，请使用某种非拉丁分隔符分隔键组件:“name,city,state”。
通常，这是我们必须发挥创造力并选择具有给定限制(唯一性、与默认属性的潜在冲突)的最简单键的地方。
注意:根据定义，唯一键不会发生冲突，而潜在的哈希冲突将由底层 Object 处理。 .
你为什么不喜欢工业解决方案？
恕我直言，最好的代码是根本没有代码:它没有错误，不需要维护，易于理解，并立即执行。我看到的所有“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 isstored at a key. Because of this (and because there were no built-inalternatives), Objects have been used as Maps historically; however,there are important differences that make using a Map preferable incertain 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 ofinsertion.
• 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 fashionand 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 canbe bypassed by using map = Object.create(null), but this is seldomdone.
• A Map may perform better in scenarios involving frequent addition and removal of key pairs.