Есть ли библиотека хэш-карт для 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 зависит от порядка.

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

Обновление :

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

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

Answer 1

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

Answer 2

Это старый вопрос, но 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 уже сегодня. :)

Answer 3

Вот краткое подтверждение концепции ...

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

Производительность будет ужасно неэффективной, потому что функция __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 4

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

Answer 5

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

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

Answer 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.

Answer 7

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

Answer 8

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