小编典典

等效于JavaScript Hashmap

javascript

该表示法是:

var hash = {};
hash[X]

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

鉴于此-在JavaScript中是否有任何有效的hashmap实现?(例如,第二个Google结果javascripthashmap产生的实现对任何操作都是O(n)。其他各种结果都忽略了这样的事实,即具有等效字符串表示形式的不同对象会相互覆盖。


阅读 305

收藏
2020-04-25

共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字符,以使用默认属性“

toString”,“#MarySmith”取消冲突。如果使用复合键,请使用某种非拉丁定界符来分隔键组件:“名称,城市,州”。

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

注意:根据定义,唯一键不会发生冲突,而潜在的哈希冲突将由底层进行处理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的性能可能更好。
2020-04-25