主要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)使用什么样的数据结构来存储键值对？我希望它是一种二进制搜索树,但我认为它们可能会使用链表(因为迭代是按插入顺序完成的).

如果他们确实使用搜索树,它是自我平衡的吗？因为具有传统搜索树的上述代码将创建不平衡树,导致用于搜索的O(n)的最坏情况场景,而不是用于平衡树的O(log n).

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

Answer 1

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

也就是说,根据您的示例,我熟悉的所有引擎都将使用某种形式的哈希表来检索与foo42from 相关联的值myobject.如果你使用像关联数组这样的对象,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倍).

但是,数字属性是特殊的.如果使用范围内间隙很小或没有间隙的整数数字属性访问对象,也就是说,使用对象就像是一个数组一样,这些值将倾向于存储在具有O(1)访问权限的线性内存块中.即使您的访问存在间隙,引擎也可能会转移到稀疏阵列访问,最坏情况下可能是O(log N).

按标识符访问属性也很特殊.如果您访问该物业,如,

myObject.foo42

并且经常执行此代码(即,这很重要),并且使用相同或类似的对象,这可能会被优化为一个或两个机器指令.对象的相似之处也因每个引擎而异,但如果它们由相同的文字或函数构成,则它们更可能被视为相似.

在JavaScript基准测试中没有任何好的引擎都会对每个对象使用相同的算法.它们都必须动态确定对象的使用方式,并尝试相应地调整访问算法.