javascript - JavaScript Hashmap等效(JavaScript Hashmap Equivalent)

Question

As made clear in update 3 on this answer , this notation:(正如在这个答案的更新3中所表明的那样，这种表示法：)

var hash = {}; hash[X] does not actually hash the object X ;(实际上并没有散列对象X ;) it actually just converts X to a string (via .toString() if it's an object, or some other built-in conversions for various primitive types) and then looks that string up, without hashing it, in " hash ".(它实际上只是将X转换为字符串（如果它是一个对象，则通过.toString() ，或者为各种基本类型转换为其他一些内置转换），然后在“ hash ”中查找该字符串，而不对其进行hash 。) Object equality is also not checked - if two different objects have the same string conversion, they will just overwrite each other.(也不检查对象相等性 - 如果两个不同的对象具有相同的字符串转换，它们将仅相互覆盖。) Given this - are there any efficient implementations of hashmaps in javascript?(鉴于此 - 在JavaScript中是否有任何有效的哈希映射实现？) (For example, the 2nd Google result of javascript hashmap yields an implementation which is O(n) for any operation. Various other results ignore the fact that different objects with equivalent string representations overwrite each other.(（例如， javascript hashmap的第二个Google结果产生了任何操作的O（n）实现。各种其他结果忽略了具有等效字符串表示的不同对象相互覆盖的事实。)   ask by Claudiu translate from so

Answer 1

Why not hash your objects yourself manually, and use the resulting strings as keys for a regular JavaScript dictionary?(为什么不自己手动散列对象，并使用生成的字符串作为常规JavaScript字典的键？)

After all you are in the best position to know what makes your objects unique.(毕竟，您处于最佳位置，无法知道是什么让您的对象与众不同。) That's what I do.(我就是做这个的。) Example:(例：) 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; This way you can control indexing done by JavaScript without heavy lifting of memory allocation, and overflow handling.(通过这种方式，您可以控制JavaScript完成的索引，而无需大量提升内存分配和溢出处理。) Of course, if you truly want the "industrial-grade solution", you can build a class parameterized by the key function, and with all necessary API of the container, but … we use JavaScript, and trying to be simple and lightweight, so this functional solution is simple and fast.(当然，如果您真的想要“工业级解决方案”，您可以构建一个由关键函数参数化的类，并使用容器的所有必需API，但是...我们使用JavaScript，并尝试简单轻量级，所以这种功能解决方案简单快捷。) The key function can be as simple as selecting right attributes of the object, eg, a key, or a set of keys, which are already unique, a combination of keys, which are unique together, or as complex as using some cryptographic hashes like in DojoX Encoding , or DojoX UUID .(关键功能可以像选择对象的正确属性一样简单，例如，键或一组键，它们已经是唯一的，键的组合，它们是唯一的，或者像使用某些加密哈希一样复杂在DojoX编码或DojoX UUID中 。) While the latter solutions may produce unique keys, personally I try to avoid them at all costs, especially, if I know what makes my objects unique.(虽然后面的解决方案可能会产生独特的密钥，但我个人试图不惜一切代价避免它们，特别是，如果我知道是什么让我的对象独特。) Update in 2014: Answered back in 2008 this simple solution still requires more explanations.(2014年更新： 2008年回答这个简单的解决方案仍需要更多解释。) Let me clarify the idea in a Q&A form.(让我以问答形式澄清这个想法。) Your solution doesn't have a real hash.(您的解决方案没有真正的哈希值。) Where is it???(它在哪里？？？) JavaScript is a high-level language.(JavaScript是一种高级语言。) Its basic primitive ( Object ) includes a hash table to keep properties.(它的基本原语（ Object ）包含一个用于保存属性的哈希表。) This hash table is usually written in a low-level language for efficiency.(此哈希表通常以低级语言编写以提高效率。) Using a simple object with string keys we use an efficiently implemented hash table with no efforts on our part.(使用带有字符串键的简单对象，我们使用有效实现的哈希表而不需要我们的努力。) How do you know they use hash?(你怎么知道他们使用哈希？) There are three major ways to keep a collection of objects addressable by a key:(有三种主要方法可以保存按键可以寻址的对象集合：) Unordered.(无序。) In this case to retrieve an object by its key we have to go over all keys stopping when we find it.(在这种情况下，要通过其键检索对象，我们必须在找到它时检查所有键。) On average it will take n/2 comparisons.(平均而言，它将进行n / 2次比较。) Ordered.(有序。) Example #1: a sorted array — doing a binary search we will find our key after ~log2(n) comparisons on average.(示例＃1：排序数组 - 执行二进制搜索我们将在~log2（n）平均比较之后找到我们的密钥。) Much better.(好多了。) Example #2: a tree.(示例＃2：一棵树。) Again it'll be ~log(n) attempts.(再次，这将是~log（n）次尝试。) Hash table.(哈希表。) On average it requires a constant time.(平均而言，它需要一个恒定的时间。) Compare: O(n) vs. O(log n) vs. O(1).(比较：O（n）与O（log n）对比O（1）。) Boom.(繁荣。) Obviously JavaScript objects use hash tables in some form to handle general cases.(显然，JavaScript对象以某种形式使用哈希表来处理一般情况。) Do browser vendors really use hash tables???(浏览器供应商真的使用哈希表???) Really.(真。) Chrome/node.js/ V8 : JSObject .(Chrome / node.js / V8 ： JSObject 。) Look for NameDictionary and NameDictionaryShape with pertinent details in objects.cc and objects-inl.h .(查找NameDictionary和NameDictionaryShape以及objects.cc和objects-inl.h中的相关详细信息。) Firefox/ Gecko : JSObject , NativeObject , and PlainObject with pertinent details in jsobj.cpp and vm/NativeObject.cpp .(火狐/ 壁虎 ： JSObject ， NativeObject和PlainObject与相关细节jsobj.cpp和VM / NativeObject.cpp 。) Do they handle collisions?(他们处理碰撞了吗？) Yes.(是。) See above.(往上看。) If you found a collision on unequal strings, please do not hesitate to file a bug with a vendor.(如果您发现不相等的字符串发生冲突，请不要犹豫，向供应商提交错误。) So what is your idea?(那么你的想法是什么？) If you want to hash an object, find what makes it unique and use it as a key.(如果要散列对象，请查找使其唯一的内容并将其用作键。) Do not try to calculate real hash or emulate hash tables — it is already efficiently handled by the underlying JavaScript object.(不要尝试计算实际哈希值或模拟哈希表 - 它已经被底层JavaScript对象有效处理。) Use this key with JavaScript Object to leverage its built-in hash table while steering clear of possible clashes with default properties.(将此键与JavaScript Object一起使用可以利用其内置的哈希表，同时避免使用默认属性进行可能的冲突。) Examples to get you started:(开始的示例：) 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 an SSN, or a passport number, and your system doesn't allow duplicates — use it as a key.(如果它包括政府颁发的唯一号码（如SSN或护照号码），并且您的系统不允许重复 - 请将其用作密钥。) If a combination of fields is unique — use it as a key.(如果字段组合是唯一的 - 将其用作键。) 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.(字段或整个对象上的某些函数可以返回唯一值 - 将其用作键。) I used your suggestion and cached all objects using a user name.(我使用了您的建议并使用用户名缓存了所有对象。) But some wise guy is named "toString", which is a built-in property!(但有些聪明人被命