Эквивалент JavaScript Hashmap

Question

Как поясняется в обновлении 3 на этот ответ , это обозначение:

var hash = {};
hash[X]

на самом деле не хэширует объект X; на самом деле он просто конвертирует X в строку (через .toString(), если это объект, или некоторые другие встроенные преобразования для различных типов примитивов), а затем просматривает эту строку без хеширования в "hash". Равенство объектов также не проверяется - если два разных объекта имеют одинаковое преобразование строк, они просто перезаписывают друг друга.

Учитывая это - существуют ли эффективные реализации хэш-карт в javascript? (Например, 2-й результат Google javascript hashmap дает реализацию, которая является O (n) для любой операции. Различные другие результаты игнорируют тот факт, что различные объекты с эквивалентными строковыми представлениями перезаписывают друг друга.

Answer 1

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

Пример:

var key = function(obj){
  // some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // just an example
};

var dict = {};

dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;

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

Конечно, если вы действительно хотите «решение промышленного уровня», вы можете создать класс, параметризованный функцией ключа и со всеми необходимыми API контейнера, но & hellip; мы используем JavaScript и пытаемся быть простыми и легкими, поэтому это функциональное решение является простым и быстрым.

Функция ключа может быть такой же простой, как выбор правильных атрибутов объекта, например, ключа или набора ключей, которые уже являются уникальными, комбинации клавиш, которые вместе уникальны, или такой сложной, как использование некоторых криптографические хэши, как в DojoX Encoding или DojoX UUID . Хотя последние решения могут создавать уникальные ключи, лично я стараюсь избегать их любой ценой, особенно если я знаю, что делает мои объекты уникальными.

Обновление в 2014 году: В 2008 году ответили, что это простое решение все еще требует дополнительных объяснений. Позвольте мне прояснить идею в форме вопросов и ответов.

Ваше решение не имеет реального хэша. Где это ???

JavaScript - это язык высокого уровня. Его основной примитив ( Объект * +1025 *) включает в себя хэш-таблицу для сохранения свойств. Эта хеш-таблица обычно пишется на языке низкого уровня для эффективности. Используя простой объект со строковыми ключами, мы используем эффективно реализованную хеш-таблицу без каких-либо усилий с нашей стороны.

Откуда вы знаете, что они используют хеш?

Существует три основных способа сохранить коллекцию объектов, адресуемых ключом:

• Unordered. В этом случае, чтобы получить объект по его ключу, мы должны пройти все ключи, останавливаясь, когда мы его находим. В среднем для сравнения потребуется n / 2.
• Заказанный.
  • Пример # 1: отсортированный массив & mdash; выполняя бинарный поиск, мы найдем наш ключ после сравнения ~ log2 (n) в среднем. Намного лучше.
  • Пример # 2: дерево. Опять это будет ~ log (n) попыток.
• Хеш-таблица. В среднем это требует постоянного времени. Сравните: O (n) против O (log n) против O (1). Boom.

Очевидно, что объекты JavaScript используют хеш-таблицы в той или иной форме для обработки общих случаев.

Действительно ли производители браузеров используют хеш-таблицы ???

Действительно.

• Хром / Node.js / V8 : JSObject . Ищу NameDictionary и NameDictionaryShape с соответствующие детали в objects.cc и objects-inl.h .
• Firefox / Gecko : JSObject , NativeObject и PlainObject с соответствующими подробностями в jsobj.cpp и ут / NativeObject.cpp .

Они обрабатывают столкновения?

Да. Смотри выше. Если вы обнаружили столкновение с неравными строками, не стесняйтесь сообщать об ошибке поставщику.

Так что вы думаете?

Если вы хотите хешировать объект, найдите, что делает его уникальным, и используйте его в качестве ключа. Не пытайтесь вычислять реальный хеш или эмулировать хеш-таблицы & mdash; он уже эффективно обрабатывается базовым объектом JavaScript.

Используйте этот ключ с JavaScript Object, чтобы использовать встроенную хэш-таблицу, избегая возможных конфликтов со свойствами по умолчанию.

Примеры, с чего можно начать:

• Если ваши объекты содержат уникальное имя пользователя & mdash; используйте его как ключ.
• Если он содержит уникальный номер клиента & mdash; используйте это как ключ.
  • Если он включает в себя уникальные номера, выданные правительством, такие как номер SSN или номер паспорта, и ваша система не допускает дублирование & mdash; используйте его как ключ.
• Если комбинация полей уникальна & mdash; используйте это как ключ.
  • Штатная аббревиатура + номер водительского удостоверения - отличный ключ.
  • Аббревиатура страны + номер паспорта тоже отличный ключ.
• Некоторые функции для полей или всего объекта могут возвращать уникальное значение & mdash; используйте его как ключ.

Я использовал ваше предложение и кэшировал все объекты, используя имя пользователя. Но какого-то мудрого парня зовут «toString», который является встроенным свойством! Что мне теперь делать?

Очевидно, что если даже отдаленно возможно, что полученный ключ будет состоять исключительно из латинских символов, вы должны что-то с этим сделать. Например, добавьте любые нелатинские символы Юникода, которые вам нравятся в начале или в конце, чтобы снять конфликт со свойствами по умолчанию: "#toString", "#MarySmith". Если используется составной ключ, разделите ключевые компоненты, используя некий латинский разделитель: «имя, город, штат».

В общем, это место, где мы должны проявлять креативность и выбирать самые простые ключи с заданными ограничениями (уникальность, потенциальные конфликты со свойствами по умолчанию).

Примечание: уникальные ключи не конфликтуют по определению, в то время как потенциальные конфликты хешей будут обрабатываться базовым Object.

Почему вам не нравятся промышленные решения?

ИМХО, лучший код - это вовсе не код: он не содержит ошибок, не требует обслуживания, прост в понимании и выполняется мгновенно. Все «хеш-таблицы в JavaScript», которые я видел, были> 100 строками кода и включали несколько объектов. Сравните это с: dict[key] = value.

Еще один момент: возможно ли даже превзойти производительность изначального объекта, написанного на низкоуровневом языке, с использованием JavaScript и тех же самых изначальных объектов для реализации того, что уже реализовано?

Я все еще хочу хешировать свои объекты без каких-либо ключей!

Нам повезло: ECMAScript 6 (выпуск запланирован на середину 2015 года, дайте или возьмите 1-2 года после этого, чтобы стать широко распространенным) определяет карта и набор .

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

Сравнительная разбивка от MDN :

Объекты похожи на Карты в том, что оба позволяют вам устанавливать ключи к значениям, получить эти значения, удалить ключи и определить, является ли что-то хранится в ключе. Из-за этого (и потому что не было встроенного альтернативы), Объекты исторически использовались как Карты; тем не мение, Есть важные отличия, которые делают использование карты предпочтительным в некоторые случаи:

• Ключами объекта являются строки и символы, в то время как они могут иметь любое значение для карты, включая функции, объекты и любые примитивы.
• Ключи в Map упорядочены, а ключи, добавленные к объекту, не упорядочены. Таким образом, при выполнении итерации объект Map возвращает ключи в порядке вставки.
• Вы можете легко получить размер Карты с помощью свойства size, в то время как количество свойств в Объекте должно быть определено вручную.
• Карта является итеративной и, таким образом, может быть напрямую повторена, тогда как для итерации по объекту требуется получить его ключи некоторым способом и перебирая их.
• Объект имеет прототип, поэтому на карте есть ключи по умолчанию, которые могут столкнуться с вашими ключами, если вы не будете осторожны. Начиная с ES5 это может можно обойти с помощью map = Object.create (null), но это редко сделано.
• Карта может работать лучше в сценариях, связанных с частым добавлением и удалением пар ключей.

Answer 2

Описание проблемы

JavaScript не имеет встроенного общего типа map (иногда его называют ассоциативный массив или словарь ), который позволяет получить доступ к произвольным значениям по произвольным ключам. Основной структурой данных JavaScript является объект , специальный тип карты, который принимает только строки в качестве ключей и имеет специальную семантику, такую ​​как наследование прототипов, методы получения и установки и некоторые другие voodoo.

Когда вы используете объекты в качестве карт, вы должны помнить, что ключ будет преобразован в строковое значение через toString(), что приведет к отображению 5 и '5' в одно и то же значение и всем объектам, которые не переписать метод toString() на значение, индексированное '[object Object]'. Вы также можете невольно получить доступ к его унаследованным свойствам, если не отметите hasOwnProperty().

Встроенный в JavaScript тип array не помогает ни на секунду: массивы JavaScript - это не ассоциативные массивы, а просто объекты с еще несколькими особыми свойствами. Если вы хотите знать, почему их нельзя использовать в качестве карт, посмотрите здесь .

Решение Евгения

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

• Примечание: Хеш-таблицы (иногда называемые хеш-картами ) представляют собой конкретную реализацию концепции карты с использованием резервного массива и поиска через числовые хеш-значения. Среда выполнения может использовать другие структуры (такие как деревья поиска или пропускать списки ) для реализации объектов JavaScript, но поскольку объекты являются фундаментальной структурой данных, они должны быть достаточно оптимизированы.

Чтобы получить уникальное хеш-значение для произвольных объектов, можно использовать глобальный счетчик и кэшировать хеш-значение в самом объекте (например, в свойстве с именем __hash).

Хеш-функция, которая делает это и работает как для примитивных значений, так и для объектов:

function hash(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
}

hash.current = 0;

Эта функция может использоваться, как описано Евгением. Для удобства мы еще обернем его в класс Map.

Моя Map реализация

Следующая реализация дополнительно сохранит пары ключ-значение в двусвязном списке, чтобы обеспечить быструю итерацию как по ключам, так и по значениям. Чтобы предоставить собственную хеш-функцию, вы можете переписать метод экземпляра hash() после создания.

// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        this.disableLinking();
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;

    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }

    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;
    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
    this.removeAll = Map.illegal;

    return this;
};

// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;

    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];

    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }

    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

Пример * * один тысяча шестьдесят-один Следующий скрипт var map = new Map; map.put('spam', 'eggs'). put('foo', 'bar'). put('foo', 'baz'). put({}, 'an object'). put({}, 'another object'). put(5, 'five'). put(5, 'five again'). put('5', 'another five'); for(var i = 0; i++ < map.size; map.next()) document.writeln(map.hash(map.key()) + ' : ' + map.value()); генерирует этот вывод: string spam : eggs string foo : baz object 1 : an object object 2 : another object number 5 : five again string 5 : another five Дополнительные соображения

PEZ предложил переписать метод toString(), предположительно, с нашей хэш-функцией. Это неосуществимо, потому что оно не работает для примитивных значений (изменение toString() для примитивов является очень плохой идеей). Если мы хотим, чтобы toString() возвращал значимые значения для произвольных объектов, нам пришлось бы изменить Object.prototype, что некоторые люди (включая меня) не считают verboten .

---

Редактировать: Текущая версия моей Map реализации, а также другие вкусности JavaScript можно получить здесь .

Answer 3

Я знаю, что этот вопрос довольно старый, но сейчас есть несколько действительно хороших решений с внешними библиотеками.

• collections.js
• неизменное

JavaScript также имеет свой язык Map.

• Карта

Answer 4

Вот простой и удобный способ использовать что-то похожее на карту Java:

var map= {
        'map_name_1': map_value_1,
        'map_name_2': map_value_2,
        'map_name_3': map_value_3,
        'map_name_4': map_value_4
        }

И чтобы получить значение:

alert( map['map_name_1'] );    // fives the value of map_value_1

......  etc  .....

Answer 5

Вы можете использовать ES6 WeakMap или Map:

• Слабые карты - это карты ключ / значение, в которых ключи являются объектами.

• Map объекты являются простыми картами ключ / значение. Любое значение (как объекты, так и примитивные значения) может использоваться в качестве ключа или значения.

Имейте в виду, что ни один из них широко не поддерживается, но вы можете использовать ES6 Shim (требуется встроенный ES5 или ES5 Shim ) для поддержки Map, но не WeakMap ( понятно почему ).

Answer 6

В соответствии со стандартом ECMAScript 2015 (ES6) javascript имеет реализацию Map. Подробнее о том, что можно найти здесь

Основное использование:

var myMap = new Map();
var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"

Answer 7

Вы должны хранить в некоторых внутренних состояниях парные пары объект / значение

HashMap = function(){
  this._dict = [];
}
HashMap.prototype._get = function(key){
  for(var i=0, couplet; couplet = this._dict[i]; i++){
    if(couplet[0] === key){
      return couplet;
    }
  }
}
HashMap.prototype.put = function(key, value){
  var couplet = this._get(key);
  if(couplet){
    couplet[1] = value;
  }else{
    this._dict.push([key, value]);
  }
  return this; // for chaining
}
HashMap.prototype.get = function(key){
  var couplet = this._get(key);
  if(couplet){
    return couplet[1];
  }
}

И используйте это так:

var color = {}; // unique object instance
var shape = {}; // unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));

Конечно, эта реализация также находится где-то на уровне O (n). Приведенные выше примеры Юджина - единственный способ получить хеш, который работает с любой скоростью, которую вы ожидаете получить от реального хеша.

Обновление:

Другой подход, аналогичный ответу Юджина, состоит в том, чтобы каким-то образом прикрепить уникальный идентификатор ко всем объектам. Один из моих любимых подходов - взять один из встроенных методов, унаследованных от суперкласса Object, заменить его на выборку пользовательской функции и присоединить свойства к этому объекту функции. Если бы вы переписали мой метод HashMap для этого, он бы выглядел так:

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Эта версия, кажется, лишь немного быстрее, но теоретически она будет значительно быстрее для больших наборов данных.

Answer 8

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

function HashMap() {
    this.buckets = {};
}

HashMap.prototype.put = function(key, value) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        bucket = new Array();
        this.buckets[hashCode] = bucket;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            bucket[i].value = value;
            return;
        }
    }
    bucket.push({ key: key, value: value });
}

HashMap.prototype.get = function(key) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        return null;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            return bucket[i].value;
        }
    }
}

HashMap.prototype.keys = function() {
    var keys = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            keys.push(bucket[i].key);
        }
    }
    return keys;
}

HashMap.prototype.values = function() {
    var values = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            values.push(bucket[i].value);
        }
    }
    return values;
}

Примечание: ключевые объекты должны "реализовывать" методы hashCode () и equals ().

Answer 9

В ECMA6 вы можете использовать WeakMap

Пример:

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // undefined, because there is no value for o2 on wm2
wm2.get(o3); // undefined, because that is the set value

wm1.has(o2); // true
wm2.has(o2); // false
wm2.has(o3); // true (even if the value itself is 'undefined')

wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // undefined, because wm3 was cleared and there is no value for o1 anymore

wm1.has(o1);   // true
wm1.delete(o1);
wm1.has(o1);   // false

Но:

Because of references being weak, WeakMap keys are not enumerable (i.e. there is no method giving you a list of the keys). 

Answer 10

Я реализовал JavaScript HashMap, код которого можно получить из http://github.com/lambder/HashMapJS/tree/master

Вот код:

/*
 =====================================================================
 @license MIT
 @author Lambder
 @copyright 2009 Lambder.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   maps value to key returning previous assocciation
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   deletes association by given key.
   Returns true if the assocciation existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// creation

var my_map = new HashMap();

// insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}