¿Hay una biblioteca de hashmap para JavaScript?

Question

En JavaScript, todos los objetos actúan de forma parecida a los hashmaps. Sin embargo, las claves para estos hashmaps deben ser cadenas. Si no lo son, se convierten con toString(). Eso significa:

var a = {foo: 1}; 
var b = {bar: 2}; 
var o = {}; 
o[a] = 100; 
o[b];    // 100 
JSON.stringify(o); // '{"[object Object]":100}' 

que es, ya que el toString() de cualquier objeto normal es [object Object], todos ellos abordan el mismo valor.

Me gustaría crear un hashmap donde los objetos con las mismas propiedades y valores aborden el mismo valor, pero los objetos con diferentes propiedades o valores abordan valores diferentes. Es decir:

var a = {foo: 1}; 
var b = {bar: 2, baz: 3}; 
var c = {baz: 3, bar: 2}; 
var hash = new Hash(); 
hash.set(a, 100); 
hash.get(b);  // undefined 
hash.set(b, 200); 
hash.get(b);  // 200 
hash.get(c);  // 200 

Mi primer instinto fue utilizar JSON.stringify() para convertir objetos en cadenas, pero:

var hash = {}; 
var b = {bar: 2, baz: 3}; 
var c = {baz: 3, bar: 2}; 
hash[JSON.stringify(b)] = 100 
hash[JSON.stringify(b)] // 100 
hash[JSON.stringify(c)] // undefined 
JSON.stringify(b)  // '{"bar":2,"baz":3}' 
JSON.stringify(c)  // '{"baz":3,"bar":2}' 

Es decir, la serialización JSON depende del orden.

¿Existe una buena biblioteca o técnica para implementar un hashmap como este?

actualización:

De manera equivalente, es que hay una buena función hash tal que:

hash({foo: 1, bar: 2}) == hash({bar: 2, foo: 1}) 

Answer 1

He aquí una prueba de concepto-rápida ...

casi no lo he probado en absoluto, y estoy seguro de que habrá angulares casos que no se puede tratar.

rendimiento será terriblemente ineficiente porque la función __createHash necesita recursivo a través de los miembros de todos los objetos y luego ordenarlos, con el fin de generar un "control" que satisfaga sus necesidades.

HashMap = function() { 
    this.get = function(key) { 
     var hash = this.__createHash(key); 
     return this.__map[hash]; 
    }; 

    this.set = function(key, value) { 
     var hash = this.__createHash(key); 
     this.__map[hash] = value; 
    }; 

    this.__createHash = function(key) { 
     switch (typeof key) { 
      case 'function': 
       return 'function'; 

      case 'undefined': 
       return 'undefined'; 

      case 'string': 
       return '"' + key.replace('"', '""') + '"'; 

      case 'object': 
       if (!key) { 
        return 'null'; 
       } 

       switch (Object.prototype.toString.apply(key)) { 
        case '[object Array]': 
         var elements = []; 
         for (var i = 0; i < key.length; i++) { 
          elements.push(this.__createHash(key[i])); 
         } 
         return '[' + elements.join(',') + ']'; 

        case '[object Date]': 
         return '#' + key.getUTCFullYear().toString() 
            + (key.getUTCMonth() + 1).toString() 
            + key.getUTCDate().toString() 
            + key.getUTCHours().toString() 
            + key.getUTCMinutes().toString() 
            + key.getUTCSeconds().toString() + '#'; 

        default: 
         var members = []; 
         for (var m in key) { 
          members.push(m + '=' + this.__createHash(key[m])); 
         } 
         members.sort(); 
         return '{' + members.join(',') + '}'; 
       } 

      default: 
       return key.toString(); 
     } 
    }; 

    this.__map = {}; 
} 

Answer 2

Se podría implementar su propia clase con un toString que asegura una ordenación de llaves.

Answer 3

prototipo tiene Hash bastante bien cubierto http://prototypejs.org/api/hash

Answer 4

Yo te recomendaría el proyecto jshashtable de Tim Down.

Answer 5

jOrder podría modificarse para tratar objetos con las mismas propiedades (pero en diferente orden) que idénticos al realizar una búsqueda de índice.

Si tiene el objeto {bar: 2, baz: 3, val: 200} en su lista, y que ha puesto previamente un índice apropiado en una mesa jOrder así:

var table = jOrder(data) 
    .index('signature', ['bar', 'baz'], {grouped: true}); 

Entonces ahora table.where([{bar: 2, baz: 3}])[0].val volverán 200, pero no lo hará table.where([{baz: 3, bar: 2}])[0].val . No requerirá mucho esfuerzo para que no dependa del orden de las propiedades. Avíseme si está interesado y enviaré la corrección a GitHub tan pronto como pueda.

Answer 6

la respuesta es utilizar dos matrices, una para las claves, una para los valores.

var i = keys.indexOf(key) 
if (i == -1) 
    {keys.push(key); values.push(value)} 
else 
    {values[i] = value; } 

Answer 7

Este hilo en realidad me llevó a encontrar un error en mi proyecto actual. Sin embargo, esto está solucionado ahora y mi implementación de HashMap en mi proyecto (https://github.com/Airblader/jsava) hará exactamente lo que usted describió. A diferencia de jshashtable, no hay cubos.

Answer 8

Esta es una vieja pregunta, pero ES6 tiene una característica que puede ser relevante: Map

mapas pueden tener objetos arbitrarios como claves y valores arbitrarios como valores. La principal distinción es que los objetos utilizados como claves permanecen únicos, incluso si los objetos son idénticos.

He aquí un ejemplo:

var map = new WeakMap(); 

var o1 = {x: 1}; 
var o2 = {x: 1}; 

map.set(o1, 'first object'); 
map.set(o2, 'second object'); 

// The keys are unique despite the objects being identical. 

map.get(o1); // 'first object' 
map.get(o2); // 'second object' 
map.get({x: 1}); // undefined 

JSON.stringify ing los objetos no sería capaz de distinguir entre o1 y o2.

MDN tiene more info. También hay un WeakMap que no mantiene referencias a los objetos utilizados como claves, por lo que pueden ser basura.

Traceur compiler todavía no tiene polyfills oficiales para Map y Weakmap, pero hay una solicitud de extracción abierta con polyfills para ambos. El código para esos polyfills (en caso de que alguien quiera agregarlos individualmente) está aquí: Map y WeakMap. Suponiendo que esos polyfills funcionan bien, puede comenzar a usar Map o WeakMap hoy. :)