¿Cuál es la gran O de serie de JavaScript cuando se utiliza como un hash?

Question

¿Cuál es la gran O de acceso a una matriz de JavaScript cuando se utiliza como un 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 motores JS no va a usar una búsqueda lineal internamente O (n), pero es a ciencia cierta?

Answer 1

En primer lugar matrices son de hecho hash. Siempre . Es por eso que x[5] === x["5"]:

var x = []; 
x[5] = 10; 
alert(x[5] === x["5"]); // true 

Los objetos son los hashes y arrays son sólo objetos especiales. Si desea usar hashes generales vaya para Objetos. Las "matrices asociativas" en Javascript son objetos. Las matrices son para datos numéricos indexados. Las matrices tienen una length propiedades y métodos de matriz similar a como push, pop, sort, etc., que no tiene sentido para ser utilizado en los hashes.

En cuanto a la gran O para buscar en Objetos: es implementación dependiente.

Probablemente los 2 mejores cosas que puede hacer para:

1. Comprobar el código fuente de algunas implementaciones de navegador

2. Haga un poco de punto de referencia para grandes n y hacer que su conclusión

---

la parte correspondiente del language specification:

4.3.3 objeto

un objeto es una colección de propiedades y tiene un solo objeto prototipo.

8.6.2 Propiedades de los objetos interna y los métodos

objetos Array tienen una implementación del método interno [[DefineOwnProperty]] ligeramente diferente. objetos Array dan tratamiento especial a una determinada clase de nombres de propiedades.

Answer 2

Se supone sintácticamente que se realiza el acceso a propiedades de objeto y elementos de matriz en JavaScript en constant time: O (1). Las características de rendimiento no están garantizadas en la especificación ECMAScript, pero todos los motores modernos de JavaScript recuperan propiedades de objetos en tiempo constante.

Aquí está un ejemplo simple que muestra cómo crecen los tiempos de acceso cuando el contenedor está tiempos x1000 más grandes:

var largeObject = {}; 
var smallObject = {}; 

var x, i; 

for (i = 0; i < 1000000; i++) { 
    largeObject['a' + i] = i; 
} 

for (i = 0; i < 1000; i++) { 
    smallObject['b' + i] = i; 
} 

console.time('10k Accesses from largeObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)]; 
console.timeEnd('10k Accesses from largeObject'); 

console.time('10k Accesses from smallObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)]; 
console.timeEnd('10k Accesses from smallObject'); 

Resultados en Firebug, Firefox 3.6.10 (Mac OS X 10.6.4 - 2,93 GHz Intel Core 2 Duo):

10k Accesses from largeObject: 22ms 
10k Accesses from smallObject: 19ms 

resultados en Chrome 6.0.472 Herramientas de desarrollo:

10k Accesses from largeObject: 15ms 
10k Accesses from smallObject: 15ms 

Internet Expl ORER 8.0.7600 con Firebug Lite en Windows 7

10k Accesses from largeObject: 250ms 
10k Accesses from smallObject: 219ms