javascript - 主要 JavaScript 引擎中 JavaScript 关联数组(动态对象属性)的检索/插入的复杂性是多少？

Question

以下面的代码为例:

var myObject = {};
var i = 100;

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

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

我有几个问题。

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

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

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

Answer 1

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

就是说，鉴于您的示例，我熟悉的所有引擎都将使用某种形式的哈希表从 myobject 中检索与 foo42 关联的值。如果你使用像关联数组这样的对象，JavaScript 引擎将倾向于使用哈希表。据我所知，没有人将树用于字符串属性。哈希表是最坏情况 O(N)，最好情况 O(1)，如果 key 生成器好的话，哈希表往往更接近 O(1) 而不是 O(N)。每个引擎都有一个模式，您可以使用它来执行 O(N)，但每个引擎都会有所不同。平衡树将保证最坏情况 O(log N) 但在保持平衡的同时修改平衡树不是 O(log N) 并且哈希表通常比字符串键的 O(log N) 更好并且是 O(1)更新(一旦你确定你需要，这与读取相同的大O)如果表中有空间(定期O(N)重建表但表通常在空间中加倍，这意味着你只需支付O(N) 7 或 8 次表的生命周期)。

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

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

myObject.foo42

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

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