JavaScript对象中键查找的性能

问题描述 投票:53回答:3

我刚刚读了这个问题:are there dictionaries in javascript like python?

答案之一说,您可以使用Python字典等JavaScript对象。真的吗?对象中键查找的性能如何?是O(1)吗?向对象添加键也是恒定时间(散列)吗?

javascript dictionary hash
3个回答
57
投票

V8 design docs表示查找至少会如此快,如果不是更快的话:

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

为了减少访问JavaScript属性所需的时间,V8不要使用动态查找来访问属性。而是V8动态在幕后创建隐藏的类。 [...] 在V8中,对象发生了变化添加新属性后,其隐藏的类。

听起来,由于创建了隐藏的类,因此添加新键可能会稍微慢一些。


20
投票

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

[引擎盖引擎可能会应用某些技术来优化后续查找,但是出于任何算法的目的,您可以假定O(1)。


0
投票

除了Domenic的answer,大多数现代JS引擎都使用非常相似的技术来加速对象属性的访问。该技术基于所谓的隐藏类形状。如果您想编写高效的JS代码,了解此优化的工作原理非常重要。

JS对象看起来像一本字典,那么为什么不使用它来存储属性呢?哈希表具有O(1)访问复杂性,它看起来是一个不错的解决方案。实际上,第一个JS引擎已经以这种方式实现了对象。但是在静态类型的语言(例如C ++或Java)中,类实例属性的访问速度很快。在此类语言中,类实例只是内存的一部分,结束时每个属性都有其自己的常量偏移量,因此要获取属性值,我们只需要获取实例指针并将其添加偏移量即可。换句话说,在编译时,像这样的表达式point.x会被其在内存中的地址替换。

也许我们可以在JS中实现一些类似的技术?但是如何?让我们看一个简单的JS函数:

function getX(point) {
  return point.x;
}

如何获得point.x值?这里的第一个问题是我们没有描述point的类(或形状)。但是我们可以计算出一个,这就是现代JS引擎所做的。在运行时,大多数JS对象具有绑定到该对象的形状。形状描述对象的属性以及属性值的存储位置。这与类定义如何使用C ++或Java描述类非常相似。这是一个很大的问题,如何计算对象的形状,在此不再赘述。我推荐this article,其中包含对总体形状的很好解释,this post则解释了如何在V8中实现这些内容。关于形状,您应该了解的最重要的事情是,具有相同属性并以相同顺序添加的所有对象都将具有相同的形状。很少有例外,例如,如果一个对象具有很多经常更改的属性,或者如果您使用delete运算符删除了一些对象属性,则该对象将切换到词典模式并且没有形状。

[现在,让我们假设point对象具有属性值的数组,并且附加了一个形状,该形状描述了此属性数组中x值的存储位置。但是问题在于我们可以将任何对象传递给函数,甚至没有必要对象具有x属性。此问题通过称为Inline caching的技术解决。这很简单,当第一次执行getX()时,它会记住该点的形状和x查找的结果。第二次调用该函数时,它将点的形状与上一个点的形状进行比较。如果形状匹配,则不需要查找,我们可以获取以前的查找结果。

主要要点是,描述同一事物的所有对象都应具有相同的形状,即它们应具有以相同顺序添加的相同属性集。它还说明了为什么最好总是初始化对象属性,即使默认情况下它们是undefinedhere is也很好地说明了问题。

相对资源:

© www.soinside.com 2019 - 2024. All rights reserved.