JavaScript 对象中键查找的性能

IT技术 javascript dictionary hash
2021-02-07 07:13:29

我刚读到这个问题:javascript 中是否有像 python 一样的字典?

其中一个答案说你可以使用像 Python 字典这样的 JavaScript 对象。真的吗?在对象中进行键查找的性能如何?是 O(1) 吗?向对象添加键是否也是恒定时间(散列)?

3个回答

V8设计文档暗示查询将至少这快,如果不是更快:

大多数 JavaScript 引擎使用类似字典的数据结构作为对象属性的存储- 每个属性访问都需要动态查找来解析属性在内存中的位置。这种方法使得在 JavaScript 中访问属性通常比在 Java 和 Smalltalk 等编程语言中访问实例变量慢得多。在这些语言中,由于对象类定义的固定对象布局,实例变量位于由编译器确定的固定偏移量处。访问只是内存加载或存储的问题,通常只需要一条指令。

为了减少访问 JavaScript 属性所需的时间,V8 不使用动态查找来访问属性。相反,V8 在幕后动态创建隐藏类。[...]在 V8 中,当添加新属性时,对象会更改其隐藏类。

不过,由于隐藏类的创建,听起来添加新密钥可能会稍微慢一些。

谢谢多梅尼克!因此,如果我进行的查找次数多于散列,则将对象查找用作字典查找对我来说似乎是安全的。
2021-03-18 07:13:29
对于 V8,动态查找不用于点表示法和方括号表示法是真的吗?
2021-03-21 07:13:29

是的,您可以假设添加密钥,然后将其用于访问是有效的恒定时间操作。

在幕后,JS 引擎可能会应用一些技术来优化后续查找,但对于任何算法,您都可以假设 O(1)。

var first = new Map([ [1, 'one'], [2, 'two'], [3, 'three'], ]);效率如何比较var second={'1': one, '2': two, '3': 'three'}
2021-04-01 07:13:29

看一个类似的问题JavaScript VM 如何实现对象属性访问?答案在这里,我描述了 JS 引擎使用的优化技术以及它如何影响关键查找性能。希望这些细节能帮助你写出更高效的 JS 代码。