主要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 相关联的值C $ C>。如果你使用像关联数组这样的对象，JavaScript引擎往往倾向于使用哈希表。没有我知道使用树来进行字符串属性。哈希表是最坏的情况O（N），最好的情况是O（1）并且如果密钥生成器是任何好的，则往往比O（N）更接近O（1）。每个引擎都有一个模式可以用来让它执行O（N），但每个引擎都会有所不同。平衡树将保证最坏情况O（log N），但是在保持平衡的同时修改平衡树不是O（log N），并且对于字符串键，哈希表通常比O（log N）更好并且是O（1）更新（一旦你确定你需要，它与读取的大O一样）如果表中有空格（定期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屋！