JavaScript对象和在引擎盖下排序的整数键

Question

我已经搜索了许多其他资源，但一直未能找到这个问题的高质量答案。

JavaScript对象按升序排序它们的整数键，而不是插入顺序。

const lookup = {}

lookup['1'] = 1
lookup['3'] = 3
lookup['2'] = 2

console.log(Object.keys(lookup)) -> ['1', '2', '3']

这么多很简单。但是，内部排序过程的大O符号是什么呢？某些排序算法必须发生在引擎盖下，以便在插入这些键时对它们进行排序，但我无法确定它是哪一个。

长度为Array.sort()的<= 10为插入排序，长度大于10的Array.sort()为快速排序

但是Array.sort()是根据对象值的排序重新排序对象的键。

引擎盖下的JavaScript如何在插入时对其键进行排序？

Answer 1

(这里是V8开发人员。)

这取决于，就像经常发生的那样。

如果整数键化属性足够密集，则对象将使用遮罩下的数组来存储它们。与排序算法相比，排序算法最接近于“基排序”，其显著区别在于没有明确的排序步骤:排序顺序是元素存储方式的“自由”副作用。当执行lookup[2] = ...时，该值将被写入数组的相应槽中。如果数组不够大，则分配一个新数组，并复制现有条目；由于这种情况不经常发生，插入的成本仍然是"O(1)摊还“。当获取整数键属性列表时，数组已按排序顺序排列.

如果整数键属性太稀疏，则对象将切换到使用字典作为后备存储。基于哈希的字典按照自己的“随机”顺序存储条目，因此在这种情况下，Object.keys()和类似的操作实际上必须执行显式排序步骤。看起来我们目前依赖于C++的std::sort，但这在很大程度上是一个可能改变的实现细节(不仅在V8方面，std::sort的实现方式也取决于V8所链接的标准库)。

长度为10的

Array.sort()是插入排序，长度> 10的Array.sort()是快速排序

不，不再是了。我们在2018年转向了TimSort。