Есть ли библиотека hashmap для JavaScript?

Question

В JavaScript все объекты действуют как хэш-карты. Однако ключи к этим хэш-картам должны быть строками. Если это не так, они преобразуются с toString(). Это означает, что:

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

То есть, так как toString() любого простого объект является [object Object], все они относятся к тому же значению.

Я хотел бы создать хэш-карту, где объекты с одинаковыми свойствами и значениями обращаются к одному и тому же значению, но объекты с разными свойствами или значениями адресуют разные значения. То есть:

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 

Мой первый инстинкт должен был использовать JSON.stringify() превратить объекты в строки, но:

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

То есть, JSON сериализации зависящих от порядка.

Есть ли хорошая библиотека или техника для реализации хэш-карты?

Update:

Эквивалентного, есть хорошая функция хеширования, что:

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

Answer 1

Вот краткое понятие корректуры из-...

Я едва протестировал его на всех, и я уверен, что там будут уголки случаи, что он не может иметь дело.

Производительность будет ужасно неэффективной, потому что функция __createHash должна перезаписывать элементы любых объектов, а затем сортировать их, чтобы генерировать «хэш», который соответствует вашим требованиям.

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

Вы могли бы реализовать свой собственный класс с toString, который обеспечивает упорядоченность ключей.

Answer 3

Прототип имеет Hash довольно красиво покрыты http://prototypejs.org/api/hash

Answer 4

Я бы порекомендовал вам проект jshashtable от Tim Down.

Answer 5

jOrder может быть изменен для обработки объектов с одинаковыми свойствами (но в другом порядке) как идентичные при выполнении поиска индекса.

Если у вас есть объект {bar: 2, baz: 3, val: 200} в списке, и вы ранее положил фитинга индекс на столе jOrder, как это:

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

Тогда прямо сейчас table.where([{bar: 2, baz: 3}])[0].val возвратит 200, но table.where([{baz: 3, bar: 2}])[0].val не будет , Это не потребует больших усилий, чтобы не зависеть от порядка свойств. Дайте мне знать, если вы заинтересованы, и я исправлю решение GitHub, как только смогу.

Answer 6

Ответ заключается в использовании двух массивов, один для ключей, один для значений.

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

Answer 7

Эта нить фактически привела меня к обнаружению ошибки в моем текущем проекте. Тем не менее, теперь это исправлено, и моя реализация HashMap в моем проекте (https://github.com/Airblader/jsava) сделает именно то, что вы описали. В отличие от jshashtable, нет ведер.

Answer 8

Это старый вопрос, но ES6 имеет особенность, которая может иметь отношение: Map

Карты могут иметь произвольные объекты в качестве ключей, и произвольных значений в качестве значений. Основное отличие состоит в том, что объекты, используемые в качестве ключей, остаются уникальными, даже если объекты идентичны.

Вот пример:

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 ИНГИ объектов не было бы в состоянии различать o1 и o2.

MDN имеет more info. Также есть WeakMap, который не поддерживает ссылки на объекты, используемые в качестве ключей, поэтому они могут быть собраны в мусор.

Traceur compiler еще не имеет официальных полисов для Карты и Weakmap, но есть открытый запрос на растяжение с полиполками для обоих. Код для этих полифиллов (в случае, если кто-то хочет их добавить отдельно): Map и WeakMap. Предполагая, что эти полисы хорошо работают, вы можете начать использовать Map или WeakMap сегодня. :)