10

以下面的代码示例为例：

var myObject = {};
var i = 100;

while (i--) {
    myObject["foo"+i] = new Foo(i);
}

console.log(myObject["foo42"].bar());

我有几个问题。

主要引擎（IE、Mozilla、Chrome、Safari）使用什么样的数据结构来存储键值对？我希望它是某种二进制搜索树，但我认为它们可能使用链表（因为迭代是按插入顺序完成的）。

如果他们确实使用搜索树，它是自我平衡的吗？因为上面的代码使用传统的搜索树会创建一个不平衡的树，导致搜索的最坏情况是 O(n)，而不是平衡树的 O(log n)。

我之所以这么问，是因为我将编写一个库，该库需要从数据结构中有效检索键，虽然我可以实现自己的或现有的红黑树，但如果它们是，我宁愿使用本机对象属性足够高效。

4

1 回答 1

21

由于几个原因，这个问题很难回答。首先，现代浏览器在代码执行时都会对代码进行大量动态优化，因此选择访问属性的算法对于相同的代码可能会有所不同。其次，每个引擎使用不同的算法和启发式方法来确定使用哪种访问算法。第三，ECMA 规范规定了结果必须是什么，而不是如何获得结果，因此引擎在该领域有很大的创新自由。

也就是说，鉴于您的示例，我熟悉的所有引擎都将使用某种形式的哈希表来检索与foo42from关联的值myobject. 如果你使用像关联数组这样的对象，JavaScript 引擎会倾向于使用哈希表。我不知道将树用于字符串属性。哈希表是最坏情况 O(N)，最好情况 O(1)，如果密钥生成器好的话，它往往更接近 O(1) 而不是 O(N)。每个引擎都会有一个模式，您可以使用它来让它执行 O(N)，但每个引擎都会有所不同。平衡树将保证最坏情况 O(log N)，但在保持平衡的同时修改平衡树不是 O(log N)，并且对于字符串键，哈希表通常比 O(log N) 更好，并且是 O(1)更新（一旦您确定需要，

然而，数值属性是特殊的。如果您使用范围内几乎没有或没有间隙的整数数字属性访问对象，也就是说，像使用数组一样使用对象，则值将倾向于存储在具有 O(1) 访问权限的线性内存块中。即使您的访问存在间隙，引擎也可能会转向稀疏数组访问，最坏的情况可能是 O(log N)。

通过标识符访问属性也很特殊。如果您像这样访问该物业，

myObject.foo42

并经常执行此代码（即，此代码的速度很重要），并且对于相同或相似的对象，这可能会优化为一两条机器指令。每个引擎使对象相似的原因也不同，但如果它们是由相同的文字或函数构造的，则它们更有可能被视为相似。

在 JavaScript 基准测试中表现出色的引擎不会对每个对象使用相同的算法。它们都必须动态确定对象的使用方式，并尝试相应地调整访问算法。

于 2012-08-22T07:42:57.660 回答