Czy istnieje biblioteka hashmap dla JavaScript?

Question

W JavaScript wszystkie obiekty działają trochę jak hashmapy. Jednak klucze do tych hadmsap muszą być ciągami. Jeśli nie, zostaną przekonwertowane na toString(). Oznacza to, że:

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

że jest, ponieważ toString() jakiegokolwiek zwykłego przedmiotu jest [object Object], wszystkie one zająć taką samą wartość.

Chciałbym utworzyć hashmap gdzie Obiekty o tych samych właściwościach i wartościach odnoszą się do tej samej wartości, ale obiekty o różnych właściwościach lub wartościach odnoszą się do różnych wartości. Czyli:

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 

Moim pierwszym odruchem było wykorzystanie JSON.stringify() włączyć przedmiotów do strun, ale:

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

że jest JSON serializacji jest zamówienie zależne.

Czy istnieje dobra biblioteka lub technika do wdrożenia takiej mapy?

Aktualizacja:

równoważnie jest tam dobra funkcja mieszania taka, że:

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

Answer 1

Oto proof-of-concept szybkie ...

Mam ledwie testowałem go w ogóle, a jestem pewien, że nie będzie narożnych przypadki, że nie może sobie poradzić.

Wydajność będzie ohydnie nieefektywna, ponieważ funkcja __createHash musi rekursować się przez elementy dowolnych obiektów, a następnie sortować je, aby wygenerować "hash", który spełnia Twoje wymagania.

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

Można zaimplementować własną klasę z toString zapewniającego uporządkowanie kluczy.

Answer 3

prototyp ma Hash całkiem ładnie pokryte http://prototypejs.org/api/hash

Answer 4

Polecam Ci projekt jshashtable od Tim Down.

Answer 5

jOrder można zmodyfikować tak, aby traktować obiekty o takich samych właściwościach (ale w innej kolejności) identyczne, jak podczas wyszukiwania indeksu.

Jeśli masz obiekt {bar: 2, baz: 3, val: 200} na liście, a wcześniej umieścić wskaźnik montażu na stole jOrder jak ten:

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

Potem teraz table.where([{bar: 2, baz: 3}])[0].val powróci 200, ale nie będzie table.where([{baz: 3, bar: 2}])[0].val . Nie wymagałoby to jednak wiele wysiłku, aby nie zależało od kolejności właściwości. Daj mi znać, jeśli jesteś zainteresowany, a ja wypchnę poprawkę do GitHub tak szybko, jak tylko będę mógł.

Answer 6

odpowiedź polega na użyciu dwóch tablic, jednej dla kluczy, jednej dla wartości.

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

Answer 7

Wątek ten doprowadził mnie do znalezienia błędu w moim bieżącym projekcie. Jednak jest to teraz naprawione, a moja implementacja HashMap w moim projekcie (https://github.com/Airblader/jsava) zrobi dokładnie to, co opisałeś. W przeciwieństwie do jshashtable, nie ma wiader.

Answer 8

To stara sprawa, ale ES6 posiada funkcję, która może mieć znaczenie: Map

Mapy mogą mieć dowolne przedmioty jak klucze i arbitralnych wartości jako wartości. Główną różnicą jest to, że obiekty używane jako klucze pozostają unikalne, nawet jeśli obiekty są identyczne.

Oto przykład:

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 obiektów nie będzie w stanie odróżnić o1 i o2.

MDN ma more info. Istnieje również WeakMap, który nie zachowuje odwołań do obiektów używanych jako klucze, więc mogą one być zbierane śmieci.

Model Traceur compiler nie ma jeszcze oficjalnych narzędzi do tworzenia map dla map i map Weakmap, ale dla obu istnieje otwarte żądanie ściągania z polifillami. Kod dla tych polyfills (w przypadku, gdy ktoś chce dodać je indywidualnie) są tutaj: Map i WeakMap. Zakładając, że te produkty wielofunkcyjne działają dobrze, możesz zacząć korzystać z Map lub WeakMap już dziś. :)