¿Cuál es la gran O para el acceso a la matriz de JavaScript cuando se usa como hash?

Por ejemplo,

var x= [];
for(var i=0; i<100000; i++){
   x[i.toString()+'a'] = 123; // using string to illustrate x[alpha]
}
alert(x['9999a']); // linear search?

Uno puede esperar que los motores JS no usen una búsqueda lineal internamente O (n), pero ¿es esto seguro?