¿Cómo se implementa un mapa hash de JavaScript?

88

Actualmente trabajo con OpenLayers y tengo un gran conjunto de datos para dibujar en una capa vectorial (más de 100000 vectores).

Ahora estoy tratando de poner todos estos vectores en un mapa hash de JavaScript para analizar el rendimiento. Quiero saber cómo se implementa el mapa hash en JavaScript, ¿es una función hash real o simplemente una función envuelta que usa una estructura de datos simple y un algoritmo de búsqueda?

Patrick Hillert
fuente
2
No hay solo una implementación de JS, por lo que no hay forma de responder a esto. ECMAScript no especifica qué estructura de datos usar para los objetos, ni especifica restricciones en el tiempo de acceso. Los hashes son típicos, pero se pueden utilizar árboles equilibrados.
Salida
1
ES6 tiene mapas puros. El enlace describe las diferencias entre el objeto plano y el mapa, detalles clave, etc.: MDN JavaScript Map
Den Roman

Respuestas:

193

cada objeto javascript es un mapa hash simple que acepta una cadena o un símbolo como clave, por lo que puede escribir su código como:

var map = {};
// add a item
map[key1] = value1;
// or remove it
delete map[key1];
// or determine whether a key exists
key1 in map;

El objeto javascript es un hashmap real en su implementación, por lo que la complejidad en la búsqueda es O (1), pero no hay una hashcode()función dedicada para las cadenas javascript, se implementa internamente mediante un motor javascript (V8, SpiderMonkey, JScript.dll, etc. .)

Actualización 2020:

Hoy en día, javascript también admite otros tipos de datos: Mapy WeakMap. Se comportan más de cerca como mapas hash que los objetos tradicionales.

otakustay
fuente
Perfecto. Estaba usando $ ('div # someDiv'). Data (key, value) antes y este es mucho más simple y probablemente también tenga mejor soporte para navegadores más antiguos. Gracias
Swaroop
¿Hay alguna forma de encontrar la longitud del mapa?
Rolling Stone
2
@Sridhar usa Object.keys (mapa) .length
otakustay
1
Tenga en cuenta que puede usar un número como clave, map[2] = 'foo'pero se convierte en una cadena internamente> map = { '2': 'foo' }
Harry Moreno
@otakustay esa fue una característica genial que llegué a conocer hoy :) Realmente necesito aprender Javascript de cerca.
Pankaj Prakash
31

Los objetos JavaScript no se pueden implementar únicamente sobre mapas hash.

Pruebe esto en la consola de su navegador:

var foo = {
    a: true,
    b: true,
    z: true,
    c: true
}

for (var i in foo) {
    console.log(i);
}

... y los recibirá de nuevo en el orden de inserción, que es el estándar de facto comportamiento .

Los mapas hash intrínsecamente no mantienen el orden, por lo que las implementaciones de JavaScript pueden usar mapas hash de alguna manera, pero si lo hacen, requerirán al menos un índice separado y una contabilidad adicional para las inserciones.

Aquí hay un video de Lars Bak que explica por qué la v8 no usa mapas hash para implementar objetos .

Craig Barnes
fuente
3
"otakustay está técnicamente mal, el peor tipo de mal". Eso es un poco duro. Puede que no sea 1: 1, pero para los propósitos y propósitos de usar un hash como un diccionario, funciona de la misma manera.
probablemente hasta el
1
Solo quiero aclarar que esto puede ser cierto para algunas implementaciones de JavaScript (como la mayoría de los navegadores) pero no necesariamente siempre es cierto. El orden de iteración sobre las claves no está definido por los estándares ECMAScript y puede ser cualquier orden y aún ser una implementación JS válida.
TheZ
19

Aquí hay una forma fácil y conveniente de usar algo similar al mapa de Java :

var map= {
    'map_name_1': map_value_1,
    'map_name_2': map_value_2,
    'map_name_3': map_value_3,
    'map_name_4': map_value_4
    }

Y para obtener el valor:

alert( map['map_name_1'] );    // fives the value of map_value_1

......  etc  .....
Miloš
fuente
12

Deberías probar esta clase Map:

var myMap = new Map();

// setting the values
myMap.set("1", 'value1');
myMap.set("2", 'value2');
myMap.set("3", 'value3');

myMap.size; // 3

// getting the values
myMap.get("1");    // "value associated with "value1"
myMap.get("2");       // "value associated with "value1"
myMap.get("3");      // "value associated with "value3"

Aviso: la clave y el valor pueden ser de cualquier tipo.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Nguyen Tan Dat
fuente
4

Si bien los objetos de JavaScript antiguos y sencillos se pueden usar como mapas, generalmente se implementan de una manera para preservar el orden de inserción para que sean compatibles con la mayoría de los navegadores (consulte la respuesta de Craig Barnes) y, por lo tanto, no son simples mapas hash.

ES6 introduce mapas adecuados (consulte MDN JavaScript Map ) de los cuales el estándar dice :

El objeto de mapa debe implementarse utilizando tablas hash u otros mecanismos que, en promedio, proporcionan tiempos de acceso que son sublineales en el número de elementos de la colección.

mb21
fuente
1
<html>
<head>
<script type="text/javascript">
function test(){
var map= {'m1': 12,'m2': 13,'m3': 14,'m4': 15}
     alert(map['m3']);
}
</script>
</head>
<body>
<input type="button" value="click" onclick="test()"/>
</body>
</html>
rajendra kumar
fuente
0

Me estaba encontrando con el problema en el que tenía el json con algunas claves comunes. Quería agrupar todos los valores con la misma clave. Después de navegar encontré el paquete hashmap . Lo que es realmente útil.

Para agrupar el elemento con la misma clave, usé multi(key:*, value:*, key2:*, value2:*, ...).

Este paquete es algo similar a la colección Java Hashmap, pero no tan poderoso como Java Hashmap.

dd619
fuente