有人知道 ECMAScript5 的 Object.keys() 在常见实现中的时间复杂度吗？是O(n)为了n钥匙吗？假设哈希实现，时间是否与哈希表的大小成正比？
我正在寻找语言实现者的保证或一些现实世界的基准测试。
Object.keys() 复杂度？
IT技术
javascript
performance
time-complexity
ecmascript-5
2021-03-05 12:33:20
2个回答
它似乎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
（此处为 V8 开发人员。）
Mark Kahn 的答案对于足够密集的整数键控/“索引”属性是正确的，其中 的复杂度Object.keys()确实是 O(n)。
虽然 JavaScript 规范假设所有对象属性都是字符串键控/“命名”的，但这并不是现代高性能引擎实现它的方式。内部差别很大！索引属性被存储在一个阵列（只要它们是足够密集），这给了通常多更好的性能比{'1': 1, ...}字典会。
对于具有数千个命名属性的对象，我们的实现确实使用了一个哈希表（正如问题所猜测的那样），这意味着复杂度Object.keys()为 O(n log n)。那是因为哈希表（当然）按自己的顺序存储条目。Object.keys()必须按照它们创建的顺序返回命名属性，我们将其存储为附加元数据，这意味着我们必须在从哈希表中检索键后对键进行排序，这是一个 O(n log n) 操作。
在实践中出现的大多数对象上的命名属性（最多大约一千个属性）（通常）以创建顺序存储在一种特殊类型的内部数组中，因此它们可以在 O(n) 中检索并且不需要排序。
所以总结真的是“视情况而定”:-)