Object.keys () сложность?

Question

Кто-нибудь знает временную сложность Object.keys () ECMAScript5 в распространенных реализациях? Это O(n) для n ключей? Пропорционально ли время размеру хеш-таблицы при условии реализации хеш-функции?

Я ищу либо гарантии от языковых разработчиков, либо какой-то реальный сравнительный анализ.

Answer 1

Похоже, что * V1 (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