Как сделать ассоциативный массив / хэширование в JavaScript

574

Мне нужно хранить некоторую статистику с использованием JavaScript таким образом, как я сделал бы это в C #:

Dictionary<string, int> statistics;

statistics["Foo"] = 10;
statistics["Goo"] = statistics["Goo"] + 1;
statistics.Add("Zoo", 1);

Есть Hashtableили что-то вроде Dictionary<TKey, TValue>в JavaScript?
Как я могу хранить значения таким образом?

George2
источник
1
js свободно набирается, поэтому нет способа просто объявить строку или int, вы можете просто объявить var и присвоить ей строку или int. : D
Гордон Густафсон
Вы можете проверить xDict. jsfiddle.net/very/MuVwd Это словарь String => все, что написано на Javascript.
Роберт
Эта статья имеет превосходное объяснение того , как ассоциативные массивы реализуются под капотом в Javascript jayconrod.com/posts/52/a-tour-of-v8-object-representation
Shuklaswag
Принятый ответ был написан в 2009 году - он поддерживает только строковые ключи. Для нестроковых ключей используйте Map или WeakMap, как в ответе Виталия .
ToolmakerSteve

Ответы:

565

Используйте объекты JavaScript в качестве ассоциативных массивов .

Ассоциативный массив: в простых словах ассоциативные массивы используют строки вместо целых чисел в качестве индекса.

Создать объект с

var dictionary = {};

Javascript позволяет добавлять свойства к объектам, используя следующий синтаксис:

Object.yourProperty = value;

Альтернативный синтаксис для того же:

Object["yourProperty"] = value;

Если вы также можете создать ключ к значению карты объектов со следующим синтаксисом

var point = { x:3, y:2 };

point["x"] // returns 3
point.y // returns 2

Вы можете перебрать ассоциативный массив с помощью конструкции цикла for..in следующим образом

for(var key in Object.keys(dict)){
  var value = dict[key];
  /* use key/value for intended purpose */
}
Алек Дэвис
источник
36
Обратите внимание, что авторский подход к инициализации «ассоциативного массива» new Array()хмурится. В конце концов, статья упоминает о своих недостатках и предлагает new Object()или в {}качестве предпочтительных альтернатив, но это близко к концу, и я боюсь, что большинство читателей не доберутся до этого.
Даниэль Любаров
24
Потерпеть поражение. JavaScript не поддерживает ссылки на объекты в виде ключей, в отличие от словаря Flash / AS3. В JavaScript, var obj1 = {}; var obj2 = {}; var table= {}; table[obj1] = "A"; table[obj2] = "B"; alert(table[obj1]); //displays Bпотому что он не может различить ключи obj1 и obj2; они оба преобразуются в строку и просто становятся чем-то вроде «объекта». Полный сбой и делает безопасную типизированную сериализацию со ссылками и нетронутыми циклическими ссылками трудными или неэффективными в JavaScript. Это легко во Flash / AS3.
Триынко
Что ж, единственный способ в JS - это проверить, проверив равенство или определив метод equals примерно так: Point.prototype.equals = function(obj) { return (obj instanceof Point) && (obj.x === this.x) && (obj.y === this.y); };
Nadeem
1
@Leo console.log ({A: 'B', C: 'D'} [foo]) должен дать вам B
ychaouche
2
@Leo Пример кажется неправильным. for... inсловарь будет зацикливаться на его ключах, поэтому, Object.keysкажется, там неуместен. Object.keysвозвращает массив ключей словаря, и for... inдля массива циклы над его «ключами», которые для массива являются его индексами, а не его значениями.
JHH
434
var associativeArray = {};
associativeArray["one"] = "First";
associativeArray["two"] = "Second";
associativeArray["three"] = "Third";

Если вы пришли из объектно-ориентированного языка, вы должны проверить эту статью .

Дани Крико
источник
38
Вы также можете сделать это в несколько строк: var associativeArray = {"one": "First", "two": "second", "three": "Third"}; Затем assocativeArray ["one"] возвращает "First", а assocativeArray ["four"] возвращает null.
Тони Уикхем
2
Извините @JuusoOhtonen, я написал пост 6 лет назад (невероятно, как быстро проходит время). Я обновил ссылку. Пожалуйста, проверьте это и не стесняйтесь спрашивать, если у вас есть какие-либо сомнения
Дани Крико
145

Все современные браузеры поддерживают JavaScript- объект Map . Есть несколько причин, по которым использование карты лучше, чем Object:

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

Пример:

var myMap = new Map();

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

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

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

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

Виталий Федоренко
источник
5
Надеюсь, через несколько лет это будет наиболее проголосовали за ответ.
Кэмерон Ли
1
@CameronLee, безусловно, будет
Loïc Faure-Lacroix
1
Это Mapвряд ли полезно, когда ваш ключ является объектом, но его следует сравнивать по значению, а не по ссылке.
Сиюань Рен
7
Спустя больше года после того, как этот ответ был написан, все еще НЕ верно, что «все современные браузеры поддерживают Map». Только на рабочем столе вы можете рассчитывать как минимум на базовую поддержку Map. Не на мобильных устройствах. Например, браузер Android вообще не поддерживает карты. Даже на рабочем столе некоторые реализации являются неполными. Например, IE11 по-прежнему не поддерживает перечисление через «for ... of ...», поэтому, если вы хотите совместимости с IE, вы должны использовать отвратительный .forEach kludge. Кроме того, JSON.stringify () не работает для Map в любом браузере, который я пробовал. Также инициализаторы не работают в IE или Safari.
Дейв Бертон,
3
Отличная поддержка браузера. Проверить снова. В любом случае, это довольно легко заполнить, поэтому поддержка нативного браузера не является проблемой.
бред
132

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

var hashtable = {};
hashtable.foo = "bar";
hashtable['bar'] = "foo";

Оба fooи barэлементы теперь могут затем ссылаться как:

hashtable['foo'];
hashtable['bar'];
// or
hashtable.foo;
hashtable.bar;

Конечно, это означает, что ваши ключи должны быть строками. Если они не являются строками, они конвертируются внутренне в строки, так что это все равно может работать, YMMV.

roryf
источник
1
Ключи как целые числа не доставили мне проблем. stackoverflow.com/questions/2380019/…
Йонас Эльфстрем
10
Джонас: имейте в виду, что ваши целые числа преобразуются в строки при установке свойства: var hash = {}; hash[1] = "foo"; alert(hash["1"]);оповещения "foo".
Тим Даун
17
Что если один из ваших ключей - « прото » или « родитель »?
Пожалуйста, разместите
5
Обратите внимание, что объекты нельзя использовать в качестве ключей в JavaScript. Что ж, они могут, но они преобразуются в свои представления String, поэтому любой объект в конечном итоге будет иметь тот же ключ. Посмотрите предложение jshashtable @ TimDown ниже.
ericsoco
21
Этот пример сбивает с толку, потому что вы используете foo и bar как ключ и значение в двух случаях. Гораздо понятнее показать, что var dict = {}; dict.key1 = "val1"; dict["key2"] = "val2";на элемент ключа dic1 dict могут ссылаться эквивалентно как dict["key1"]и, так и dict.key1.
Джим
49

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

var hashSweetHashTable = {};
Shog9
источник
26
Понижено, потому что не показывает, как на самом деле получить доступ к значениям в «хэш-таблице».
IQAndreas
Я опоздал на 9 лет (я ничего не знал о программировании, не говоря уже об этом сайте), но ... Что, если вы пытаетесь сохранить точки на карте, и вам нужно посмотреть, что-то уже есть в точке на карте? В этом случае для этого лучше всего использовать HashTable, ища по координатам ( объект , а не строка ).
Майк Уоррен,
@MikeWarren if (hashSweetHashTable.foo)должен ввести блок if, если fooустановлен.
Корай Тугай
21

поэтому в C # код выглядит так:

Dictionary<string,int> dictionary = new Dictionary<string,int>();
dictionary.add("sample1", 1);
dictionary.add("sample2", 2);

или

var dictionary = new Dictionary<string, int> {
    {"sample1", 1},
    {"sample2", 2}
};

в JavaScript

var dictionary = {
    "sample1": 1,
    "sample2": 2
}

Словарь C # содержит полезные методы, как dictionary.ContainsKey() в JavaScript, мы могли бы использовать hasOwnPropertyкак

if (dictionary.hasOwnProperty("sample1"))
    console.log("sample1 key found and its value is"+ dictionary["sample1"]);
Радж
источник
1
Upvote для меня не нужно писать ответ оhasOwnProperty
Brichins
18

Если вы хотите, чтобы ваши ключи были любым объектом, а не просто строкой, вы можете использовать мою jshashtable .

Тим Даун
источник
3
Сколько часов я потратил на то, чтобы понять, что объекты действительно нельзя использовать в качестве ключей для массивов JS-style-Object-as-ассоциативных-массивов, прежде чем я обнаружил это? Спасибо, Тим.
ericsoco
1
Flash / AS3 Dictionary, как и большинство других языков, поддерживает ссылки на объекты в качестве ключей. JavaScript до сих пор не реализовал его, но я думаю, что он будет в будущем в качестве своего рода класса Map. Снова с полифилами в это время; так много для стандартов. Ой, подождите ... наконец-то в 2015 году карта, похоже, прибыла: stackoverflow.com/a/30088129/88409 и поддерживается "современными" браузерами, lol: kangax.github.io/compat-table/es6/# Карта (и не очень широко поддерживается). Всего лишь десятилетие позади AS3.
Трийнко
Тим, возможно, тебе следует обновить jshashtable, чтобы использовать Map () там, где это возможно.
Дейв Бертон,
1
@DaveBurton: Хороший план. Я сделаю это, как только у меня будет время.
Тим Даун
6
function HashTable() {
    this.length = 0;
    this.items = new Array();
    for (var i = 0; i < arguments.length; i += 2) {
        if (typeof (arguments[i + 1]) != 'undefined') {
            this.items[arguments[i]] = arguments[i + 1];
            this.length++;
        }
    }

    this.removeItem = function (in_key) {
        var tmp_previous;
        if (typeof (this.items[in_key]) != 'undefined') {
            this.length--;
            var tmp_previous = this.items[in_key];
            delete this.items[in_key];
        }

        return tmp_previous;
    }

    this.getItem = function (in_key) {
        return this.items[in_key];
    }

    this.setItem = function (in_key, in_value) {
        var tmp_previous;
        if (typeof (in_value) != 'undefined') {
            if (typeof (this.items[in_key]) == 'undefined') {
                this.length++;
            } else {
                tmp_previous = this.items[in_key];
            }

            this.items[in_key] = in_value;
        }

        return tmp_previous;
    }

    this.hasItem = function (in_key) {
        return typeof (this.items[in_key]) != 'undefined';
    }

    this.clear = function () {
        for (var i in this.items) {
            delete this.items[i];
        }

        this.length = 0;
    }
}
Birey
источник
1
Для людей, которые проголосовали против, не могли бы вы прокомментировать, почему? Этот ответ был опубликован в 2011 году, а не в текущей дате.
Бирей
2
Я не голосовал против, но ... вы не должны использовать массив в качестве объекта. Не уверен на 100%, если это было твоим намерением. Используйте срезы в массивах, а не удаляйте их для повторного индексирования; удаление в порядке, но будет установлено неопределенным - лучше быть явным; use = undefined для объекта тоже, потому что он быстрее (но больше памяти). Короче говоря: всегда используйте объект: {}не массив: []или new Array()если вы намереваетесь иметь строковые ключи, иначе у движка js есть проблема - он либо увидит 2 типа для 1 переменной, что означает отсутствие оптимизации, либо будет работать с массивом и реализует это должно измениться к объекту (возможное перераспределение).
Грэм Уикстед
2
Как и в случае с ответом Алекса Хокинса, приведите несколько объяснений, почему этот довольно сложный код действительно полезен и лучше, чем другие более короткие ответы, приведенные здесь.
Томас Темпельманн
6

Я создал это для решения некоторых проблем, таких как сопоставление ключей объекта, возможность перечисления (с помощью forEach()метода) и очистки.

function Hashtable() {
    this._map = new Map();
    this._indexes = new Map();
    this._keys = [];
    this._values = [];
    this.put = function(key, value) {
        var newKey = !this.containsKey(key);
        this._map.set(key, value);
        if (newKey) {
            this._indexes.set(key, this.length);
            this._keys.push(key);
            this._values.push(value);
        }
    };
    this.remove = function(key) {
        if (!this.containsKey(key))
            return;
        this._map.delete(key);
        var index = this._indexes.get(key);
        this._indexes.delete(key);
        this._keys.splice(index, 1);
        this._values.splice(index, 1);
    };
    this.indexOfKey = function(key) {
        return this._indexes.get(key);
    };
    this.indexOfValue = function(value) {
        return this._values.indexOf(value) != -1;
    };
    this.get = function(key) {
        return this._map.get(key);
    };
    this.entryAt = function(index) {
        var item = {};
        Object.defineProperty(item, "key", {
            value: this.keys[index],
            writable: false
        });
        Object.defineProperty(item, "value", {
            value: this.values[index],
            writable: false
        });
        return item;
    };
    this.clear = function() {
        var length = this.length;
        for (var i = 0; i < length; i++) {
            var key = this.keys[i];
            this._map.delete(key);
            this._indexes.delete(key);
        }
        this._keys.splice(0, length);
    };
    this.containsKey = function(key) {
        return this._map.has(key);
    };
    this.containsValue = function(value) {
        return this._values.indexOf(value) != -1;
    };
    this.forEach = function(iterator) {
        for (var i = 0; i < this.length; i++)
            iterator(this.keys[i], this.values[i], i);
    };
    Object.defineProperty(this, "length", {
        get: function() {
            return this._keys.length;
        }
    });
    Object.defineProperty(this, "keys", {
        get: function() {
            return this._keys;
        }
    });
    Object.defineProperty(this, "values", {
        get: function() {
            return this._values;
        }
    });
    Object.defineProperty(this, "entries", {
        get: function() {
            var entries = new Array(this.length);
            for (var i = 0; i < entries.length; i++)
                entries[i] = this.entryAt(i);
            return entries;
        }
    });
}


Документация класса Hashtable

Методы:

  • get(key)
    Возвращает значение, связанное с указанным ключом.
    Параметры::
    key ключ, из которого извлекается значение.

  • put(key, value)
    Связывает указанное значение с указанным ключом.
    Параметры::
    key ключ, с которым связывается значение.
    value: Значение для привязки к ключу.

  • remove(key)
    Удаляет указанный ключ с его значением.
    Параметры::
    key ключ для удаления.

  • clear()
    Очищает всю хеш-таблицу, удаляя ключи и значения.

  • indexOfKey(key)
    Возвращает индекс указанного ключа на основе порядка добавления.
    Параметры::
    key ключ, из которого получают индекс.

  • indexOfValue(value)
    Возвращает индекс указанного значения на основе порядка добавления.
    Параметры::
    value значение которого получить индекс.
    Примечания:
    эта информация извлекается indexOf()методом массива, поэтому он сравнивает объект только с toString()методом.

  • entryAt(index)
    Возвращает объект с двумя свойствами: ключ и значение, представляющие запись по указанному индексу.
    Параметры::
    index индекс записи для получения.

  • containsKey(key)
    Возвращает, содержит ли хеш-таблица указанный ключ.
    Параметры::
    key ключ для проверки.

  • containsValue(value)
    Возвращает, содержит ли хеш-таблица указанное значение.
    Параметры::
    value значение для проверки.

  • forEach(iterator)
    Итерирует все записи в указанном iterator.
    Параметры:
    value : Метод с 3 - мя параметрами: key, valueи index, где indexпредставляет собой индекс записи.

    Свойства:

  • length ( Только для чтения )
    Получает количество записей в хеш-таблице.

  • keys ( Только для чтения )
    Получает массив всех ключей в хеш-таблице.

  • values ( Только для чтения )
    Получает массив всех значений в хеш-таблице.

  • entries ( Только для чтения )
    Получает массив всех записей в хеш-таблице. Они представлены в одной и той же форме метода entryAt().

Давиде Канниццо
источник
2

https://gist.github.com/alexhawkins/f6329420f40e5cafa0a4

var HashTable = function() {
  this._storage = [];
  this._count = 0;
  this._limit = 8;
}


HashTable.prototype.insert = function(key, value) {
  //create an index for our storage location by passing it through our hashing function
  var index = this.hashFunc(key, this._limit);
  //retrieve the bucket at this particular index in our storage, if one exists
  //[[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ]  [ [k,v] ] ]
  var bucket = this._storage[index]
    //does a bucket exist or do we get undefined when trying to retrieve said index?
  if (!bucket) {
    //create the bucket
    var bucket = [];
    //insert the bucket into our hashTable
    this._storage[index] = bucket;
  }

  var override = false;
  //now iterate through our bucket to see if there are any conflicting
  //key value pairs within our bucket. If there are any, override them.
  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    if (tuple[0] === key) {
      //overide value stored at this key
      tuple[1] = value;
      override = true;
    }
  }

  if (!override) {
    //create a new tuple in our bucket
    //note that this could either be the new empty bucket we created above
    //or a bucket with other tupules with keys that are different than 
    //the key of the tuple we are inserting. These tupules are in the same
    //bucket because their keys all equate to the same numeric index when
    //passing through our hash function.
    bucket.push([key, value]);
    this._count++
      //now that we've added our new key/val pair to our storage
      //let's check to see if we need to resize our storage
      if (this._count > this._limit * 0.75) {
        this.resize(this._limit * 2);
      }
  }
  return this;
};


HashTable.prototype.remove = function(key) {
  var index = this.hashFunc(key, this._limit);
  var bucket = this._storage[index];
  if (!bucket) {
    return null;
  }
  //iterate over the bucket
  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    //check to see if key is inside bucket
    if (tuple[0] === key) {
      //if it is, get rid of this tuple
      bucket.splice(i, 1);
      this._count--;
      if (this._count < this._limit * 0.25) {
        this._resize(this._limit / 2);
      }
      return tuple[1];
    }
  }
};



HashTable.prototype.retrieve = function(key) {
  var index = this.hashFunc(key, this._limit);
  var bucket = this._storage[index];

  if (!bucket) {
    return null;
  }

  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    if (tuple[0] === key) {
      return tuple[1];
    }
  }

  return null;
};


HashTable.prototype.hashFunc = function(str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    var letter = str[i];
    hash = (hash << 5) + letter.charCodeAt(0);
    hash = (hash & hash) % max;
  }
  return hash;
};


HashTable.prototype.resize = function(newLimit) {
  var oldStorage = this._storage;

  this._limit = newLimit;
  this._count = 0;
  this._storage = [];

  oldStorage.forEach(function(bucket) {
    if (!bucket) {
      return;
    }
    for (var i = 0; i < bucket.length; i++) {
      var tuple = bucket[i];
      this.insert(tuple[0], tuple[1]);
    }
  }.bind(this));
};


HashTable.prototype.retrieveAll = function() {
  console.log(this._storage);
  //console.log(this._limit);
};

/******************************TESTS*******************************/

var hashT = new HashTable();

hashT.insert('Alex Hawkins', '510-599-1930');
//hashT.retrieve();
//[ , , , [ [ 'Alex Hawkins', '510-599-1930' ] ] ]
hashT.insert('Boo Radley', '520-589-1970');
//hashT.retrieve();
//[ , [ [ 'Boo Radley', '520-589-1970' ] ], , [ [ 'Alex Hawkins', '510-599-1930' ] ] ]
hashT.insert('Vance Carter', '120-589-1970').insert('Rick Mires', '520-589-1970').insert('Tom Bradey', '520-589-1970').insert('Biff Tanin', '520-589-1970');
//hashT.retrieveAll();
/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Tom Bradey', '520-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Rick Mires', '520-589-1970' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '520-589-1970' ] ] ]
*/

//overide example (Phone Number Change)
//
hashT.insert('Rick Mires', '650-589-1970').insert('Tom Bradey', '818-589-1970').insert('Biff Tanin', '987-589-1970');
//hashT.retrieveAll();

/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Tom Bradey', '818-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Rick Mires', '650-589-1970' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]

*/

hashT.remove('Rick Mires');
hashT.remove('Tom Bradey');
//hashT.retrieveAll();

/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]


*/

hashT.insert('Dick Mires', '650-589-1970').insert('Lam James', '818-589-1970').insert('Ricky Ticky Tavi', '987-589-1970');
hashT.retrieveAll();


/* NOTICE HOW HASH TABLE HAS NOW DOUBLED IN SIZE UPON REACHING 75% CAPACITY ie 6/8. It is now size 16.
 [,
  ,
  [ [ 'Vance Carter', '120-589-1970' ] ],
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Dick Mires', '650-589-1970' ],
    [ 'Lam James', '818-589-1970' ] ],
  ,
  ,
  ,
  ,
  ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Ricky Ticky Tavi', '987-589-1970' ] ],
  ,
  ,
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]




*/
console.log(hashT.retrieve('Lam James'));  //818-589-1970
console.log(hashT.retrieve('Dick Mires')); //650-589-1970
console.log(hashT.retrieve('Ricky Ticky Tavi')); //987-589-1970
console.log(hashT.retrieve('Alex Hawkins')); //510-599-1930
console.log(hashT.retrieve('Lebron James')); //null
Алекс Хокинс
источник
3
Выглядит хорошо. Теперь, пожалуйста, также объясните, ПОЧЕМУ это полезно и может быть лучше, чем все остальные ответы здесь.
Томас Темпельманн
1

Вы можете создать его, используя следующие:

var dictionary = { Name:"Some Programmer", Age:24, Job:"Writing Programs"  };

//Iterate Over using keys
for (var key in dictionary) {
  console.log("Key: " + key + " , " + "Value: "+ dictionary[key]);
}

//access a key using object notation:
console.log("Her Name is: " + dictionary.Name)

Али Эззат Одех
источник