javascript - Object.keys() 复杂性？

Question

有人知道 ECMAScript5 的 Object.keys() 在常见实现中的时间复杂度吗？ n 个键的时间复杂度是 O(n) 吗？假设采用哈希实现，时间与哈希表的大小成正比吗？

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

Answer 1

在 V8(chrome、node.js)中至少是 O(n):

> 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