在主要 javascript 引擎中，在 JavaScript 关联数组(动态对象属性)中检索/插入的复杂性是多少? [英] What is the complexity of retrieval/insertion in JavaScript associative arrays (dynamic object properties) in the major javascript engines?

问题描述

以下面的代码为例:

var myObject = {};
var i = 100;

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

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

我有几个问题.

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

What kind of data structure do the major engines (IE, Mozilla, Chrome, Safari) use for storing key-value pairs? I'd hope it's some kind Binary Search tree, but I think they may use linked lists (due to the fact iterating is done in insertion order).

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

If they do use a search tree, is it self balancing? Because the above code with a conventional search tree will create an unbalanced tree, causing worst case scenario of O(n) for searching, rather than O(log n) for a balanced tree.

我之所以这么问，是因为我将编写一个库，该库需要从数据结构中高效检索密钥，虽然我可以实现自己的或现有的红黑树，但如果它们足够高效.

I'm only asking this because I will be writing a library which will require efficient retrieval of keys from a data structure, and while I could implement my own or an existing red-black tree I would rather use native object properties if they're efficient enough.

推荐答案

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

The question is hard to answer for a couple reasons. First, the modern browsers all heavily and dynamically optimize code while it is executing so the algorithms chosen to access the properties might be different for the same code. Second, each engine uses different algorithms and heuristics to determine which access algorithm to use. Third, the ECMA specification dictates what the result of must be, not how the result is achieved so the engines have a lot of freedom to innovate in this area.

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

That said, given your example all the engines I am familiar with will use some form of a hash table to retrieve the value associated with foo42 from myobject. If you use an object like an associative array JavaScript engines will tend to favor a hash table. None that I am aware of use a tree for string properties. Hash tables are worst case O(N), best case O(1) and tend to be closer to O(1) than O(N) if the key generator is any good. Each engine will have a pattern you could use to get it to perform O(N) but that will be different for each engine. A balanced tree would guarantee worst case O(log N) but modifying a balanced tree while keeping it balanced is not O(log N) and hash tables are more often better than O(log N) for string keys and are O(1) to update (once you determine you need to, which is the same big-O as read) if there is space in the table (periodically O(N) to rebuild the table but the tables usually double in space which means you will only pay O(N) 7 or 8 times for the life of the table).

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

Numeric properties are special, however. If you access an object using integer numeric properties that have few or no gaps in range, that is, use the object like it is an array, the values will tend to be stored in a linear block of memory with O(1) access. Even if your access has gaps the engines will probably shift to a sparse array access which will probably be, at worst, O(log N).

通过标识符访问属性也很特殊.如果您访问该属性，

Accessing a property by identifier is also special. If you access the property like,

myObject.foo42

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

and execute this code often (that is, the speed of this matters) and with the same or similar object this is likely to be optimized into one or two machine instructions. What makes objects similar also differs for each engine but if they are constructed by the same literal or function they are more likely to be treated as similar.

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

No engine that does at all well on the JavaScript benchmarks will use the same algorithm for every object. They all must dynamically determine how the object is being used and try to adjust the access algorithm accordingly.

这篇关于在主要 javascript 引擎中，在 JavaScript 关联数组(动态对象属性)中检索/插入的复杂性是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！