Complexité Object.keys() ?

Question

Quelqu'un connaît-il la complexité temporelle de Object.keys() d'ECMAScript5 dans les implémentations courantes ? Est-ce O(n) pour les clés n Le temps est-il proportionnel à la taille de la table de hachage, en supposant une implémentation de hachage ?

Je recherche soit des garanties de la part des implémenteurs de langage, soit des analyses comparatives du monde réel.

Answer 1

Il semble que ce soit O(n) en V8 (chrome, node.js) au moins :

 > 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