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

В 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 зависит от порядка.

Есть ли хорошая библиотека или техника для реализации хешмапа, подобного этому?

Обновление

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

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

Ответы

Ответ 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 = {};
}

Ответ 3

Это старый вопрос, но у 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 есть дополнительная информация. Там также WeakMap, который не поддерживает ссылки на объекты, используемые в качестве ключей, поэтому они могут быть собраны в мусор.

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

Ответ 4

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

Ответ 6

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, как только смогу.

Ответ 7

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

Ответ 8

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

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