Object.keys()复杂性？

Question

有人知道ECMAScript5的Object.keys()在常见实现中的时间复杂度吗？它是O(n)用于n钥匙？假设哈希实现,时间是否与哈希表的大小成比例？

我正在寻找语言实现者或某些现实世界基准测试的保证.

Answer 1

它似乎O(n)至少在V8(chrome,node.js)中:

> var hash = {}
>   ,    c = 0;
> 
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
0
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
26
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
49
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
75
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
102    

Answer 2

（此处为 V8 开发人员。）

Mark Kahn 的答案对于足够密集的整数键控/“索引”属性是正确的，其中 的复杂度Object.keys()确实是 O(n)。

虽然 JavaScript 规范假装所有对象属性都是字符串键/“命名”的，但这不是现代高性能引擎实现它的方式。内部差异很大！索引属性被存储在一个阵列（只要它们是足够密集），这给了通常多更好的性能比{'1': 1, ...}字典会。

对于具有数千个命名属性的对象，我们的实现确实使用了一个哈希表（正如问题所猜测的那样），这意味着复杂度Object.keys()为 O(n log n)。那是因为哈希表（当然）按自己的顺序存储条目。Object.keys()必须按照它们创建的顺序返回命名属性，我们将其存储为附加元数据，这意味着我们必须在从哈希表中检索键后对键进行排序，这是一个 O(n log n) 操作。

在实践中出现的大多数对象上的命名属性（最多大约一千个属性）（通常）按创建顺序存储在一种特殊类型的内部数组中，因此它们可以在 O(n) 中检索并且不需要排序。

所以总结真的是“视情况而定”:-)