Gibt es eine hashmap-Bibliothek für JavaScript?

Question

In JavaScript verhalten sich alle Objekte wie hashmaps. Die Schlüssel zu diesen hashmaps müssen jedoch Strings sein. Wenn nicht, werden sie mit toString() konvertiert. Das heißt:

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

Das heißt, da die toString() jeder Ebene Objekt ist [object Object], sie alle den gleichen Wert adressieren.

Ich möchte eine Hashmap erstellen, wobei Objekte mit denselben Eigenschaften und Werten den gleichen Wert adressieren, Objekte mit unterschiedlichen Eigenschaften oder Werten jedoch unterschiedliche Werte haben. Das heißt:

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 

Mein erster Instinkt war JSON.stringify() zu verwenden, um Objekte in Strings zu drehen, aber:

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}' 

Das heißt, JSON Serialisierung ist auftragsabhängig.

Gibt es eine gute Bibliothek oder Technik, um eine Hashmap so zu implementieren?

aktualisieren:

Gleichwertig, gibt es eine gute Hash-Funktion, so dass:

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

Answer 1

Hier ist ein schneller Proof-of-concept ...

ich es kaum überhaupt getestet habe, und ich bin sicher, dass es Ecke Fälle sein, dass es nicht mit umgehen kann.

Die Leistung wird schrecklich ineffizient sein, da die __createHash Funktion muss durch die Mitglieder aller Objekte recurse und dann sortieren, um einen "Hash" zu generieren, der Ihren Anforderungen entspricht.

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

Sie könnten Ihre eigene Klasse mit einem toString implementieren, die eine Ordnung der Schlüssel gewährleistet.

Answer 3

Prototyp hat Hash ganz gut http://prototypejs.org/api/hash bedeckt

Answer 4

Ich würde Sie das jshashtable Projekt von Tim Down empfehlen.

Answer 5

könnte geändert werden, um Objekte mit denselben Eigenschaften (aber in anderer Reihenfolge) als identisch zu behandeln, wenn eine Indexsuche durchgeführt wird.

Wenn Sie das Objekt {bar: 2, baz: 3, val: 200} in Ihrer Liste, und Sie haben setzen vorher eine passende Index auf einer Jörder Tabelle wie folgt aus:

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

Dann jetzt table.where([{bar: 2, baz: 3}])[0].val 200 zurück, aber table.where([{baz: 3, bar: 2}])[0].val wird nicht . Es würde jedoch nicht viel Mühe kosten, es nicht von der Reihenfolge der Eigenschaften abhängig zu machen. Lassen Sie es mich wissen, wenn Sie interessiert sind und ich werde die Reparatur so schnell wie möglich an GitHub weitergeben.

Answer 6

Die Antwort ist, zwei Arrays zu verwenden, eins für Schlüssel, eins für Werte.

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

Answer 7

Dieser Thread führte mich tatsächlich zu einem Fehler in meinem aktuellen Projekt. Dies ist jedoch jetzt behoben und meine HashMap-Implementierung in meinem Projekt (https://github.com/Airblader/jsava) wird genau das tun, was Sie beschrieben haben. Im Gegensatz zu jshashtable gibt es keine Buckets.

Answer 8

Dies ist eine alte Frage, aber ES6 verfügt über eine Funktion, die relevant sein können: Map

Karten beliebiger Objekte als Schlüssel und beliebige Werte als Werte haben können. Der Hauptunterschied besteht darin, dass die als Schlüssel verwendeten Objekte auch dann eindeutig sind, wenn die Objekte identisch sind.

Hier ist ein Beispiel:

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 die Objekte ing nicht zwischen o1 und o2 unterscheiden würde.

MDN hat more info. Es gibt auch eine WeakMap, die keine Verweise auf die als Schlüssel verwendeten Objekte enthält, so dass sie als Garbage Collected betrachtet werden können.

Die Traceur compiler hat noch keine offiziellen Polyfills für Map und Weakmap, aber es gibt eine offene Pull-Anfrage mit Polyfills für beide. Der Code für diese Polyfills (falls jemand sie einzeln hinzufügen möchte) ist hier: Map und WeakMap. Wenn diese Polyfills gut funktionieren, können Sie heute Map oder WeakMap verwenden. :)