等效于JavaScript Hashmap

Question

该表示法是：

var hash = {};
hash[X]

实际上不哈希对象X；它实际上只是转换X为字符串（通过.toString()它是一个对象，还是其他各种原始类型的内置转换），然后在“
hash”中查找该字符串，而不对其进行哈希处理。也不会检查对象是否相等-如果两个不同的对象具有相同的字符串转换，则它们将彼此覆盖。

鉴于此-在JavaScript中是否有任何有效的hashmap实现？（例如，第二个Google结果javascripthashmap产生的实现对任何操作都是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，并试图做到简单轻巧，因此此功能解决方案既简单又快速。

密钥功能可以很简单，例如，选择对象的正确属性（例如，一个密钥或一组密钥，这些属性已经是唯一的），密钥的组合（这些密钥一起是唯一的），或者像使用某些加密哈希一样复杂在DojoXEncoding或DojoXUUID中。尽管后一种解决方案可能会产生唯一键，但我个人还是不惜一切代价避免使用它们，特别是如果我知道是什么使我的对象变得唯一时。

2014年更新： 早在2008年就回答了这个简单的解决方案，但仍需要更多说明。让我以问答形式澄清这个想法。

您的解决方案没有真正的哈希。 它在哪里？？？

JavaScript是一种高级语言。它的基本原语（Object）包括用于保留属性的哈希表。为了提高效率，通常用低级语言编写此哈希表。通过使用带有字符串键的简单对象，我们无需任何努力即可使用高效实现的哈希表。

您怎么知道他们使用哈希？

保持键可寻址的对象集合的三种主要方法：

• 无序的。在这种情况下，要通过对象的键检索对象，我们必须遍历所有找到键时停止的键。平均而言，将进行n / 2个比较。
• 订购了。
  • 例子1：一个有序的数组—做一个二分查找，我们将在平均〜log2（n）比较之后找到我们的密钥。好多了。
  • 示例2：一棵树。再次尝试〜log（n）。
• 哈希表。平均而言，它需要一个恒定的时间。比较：O（n）与O（log n）与O（1）。繁荣。

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

浏览器供应商是否真的使用哈希表？？？

真。

Chrome / node.js / V8： JSObject。寻找 NameDictionary和 NameDictionaryShape与相关细节objects.cc 和对象- inl.h。
Firefox/Gecko： JSObject， NativeObject和 PlainObject与相关细节 jsobj.cpp和 VM / NativeObject.cpp。

他们会处理碰撞吗？

是。看上面。如果发现不相等的字符串发生冲突，请立即向供应商提交错误报告。

那你的主意是什么？

如果要对对象进行哈希处理，请查找使其唯一的原因并将其用作键。不要尝试计算真实的哈希或模拟哈希表-基础JavaScript对象已经有效地处理了它。

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

入门示例：

• 如果您的对象包含唯一的用户名，请使用它作为键。
• 如果它包含唯一的客户编号，请使用它作为密钥。
  • 如果它包含政府发行的唯一号码（例如SSN或护照号码），并且您的系统不允许重复，请使用它作为密钥。
• 如果字段的组合是唯一的，则将其用作键。
  • 状态缩写+驾驶执照号码是一个很好的钥匙。
  • 国家缩写+护照号码也是一个很好的钥匙。
• 字段上的某些函数或整个对象可以返回唯一值-将其用作键。

我使用了您的建议，并使用用户名缓存了所有对象。 但是，一个聪明人被称为“ toString”，这是一个内置属性！我现在应该怎么做？

显然，如果生成的键很可能仅由拉丁字符组成，那么您应该对此做一些事情。例如，在开头或结尾添加您喜欢的任何非拉丁Unicode字符，以使用默认属性“

通常，这里是我们必须发挥创造力的地方，然后选择具有给定限制（唯一性，具有默认属性的潜在冲突）的最简单的键。

注意：根据定义，唯一键不会发生冲突，而潜在的哈希冲突将由底层进行处理Object。

您为什么不喜欢工业解决方案？

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

还有一点：使用JavaScript和完全相同的原始对象来实现已经实现的东西，甚至有可能击败以低级语言编写的原始对象的性能吗？

我仍然想散列没有任何键的对象！

我们很幸运：ECMAScript 6（计划于2015年中期发布，在此之后花上一到两年的时间才能普及）定义了地图和集合。

根据定义判断，他们可以将对象的地址用作键，这使对象无需人工键即可立即与众不同。OTOH，两个不同但相同的对象，将被映射为不同的对象。

来自MDN的比较细分：

对象与Maps相似，两者都允许您将键设置为值，检索这些值，删除键以及检测是否在键处存储了某些内容。因此（由于没有内置的替代方法），对象在历史上一直被用作地图。但是，在某些情况下，使用地图有一些重要的区别：

• 对象的键是字符串和符号，而它们的键可以是Map的任何值，包括函数，对象和任何基元。
• Map中的键是有序的，而添加到对象中的键则没有顺序。因此，在对其进行迭代时，Map对象将按插入顺序返回键。
• 您可以使用size属性轻松获得Map的大小，而Object中的属性数量则必须手动确定。
• Map是可迭代的，因此可以直接进行迭代，而对Object进行迭代需要以某种方式获取其键并对其进行迭代。
• 对象具有原型，因此如果不小心，地图中的默认键可能会与您的键冲突。从ES5开始，可以通过使用map =
  Object.create（null）绕过此方法，但这很少完成。
• 在涉及频繁添加和删除密钥对的情况下，Map的性能可能更好。