Hashmaps в JavaScript от целочисленных ключей

Question

Я кодирую в javascript и мне нужна структура типа HashMap. Обычно, когда мне нужны хеш-карты, я бы использовал только ассоциативные массивы (со строками в качестве ключей). Но на этот раз мне нужны целые числа в качестве ключей к хэш-картам.

Так что, если я попытаюсь сохранить A [1000] = obj, будет создан массив размером 1001 и A [1001] будет помещен как obj. Даже если я попробую A ["1000"] = obj, он все равно выделяет 1001 пробел и заполняет их неопределенным.

Я не хочу этого, потому что мои ключи могут быть очень большими (около 1 миль). Я мог бы использовать его как A ["dummy1000"] = obj, но я не хочу использовать этот грязный метод.

В любом случае, делать это элегантно и легко?

Answer 1

Выполнение A[1000] = 1 не создает массив с 1000 элементами.Он создает объект массива, атрибут длины которого равен 1001, но это только потому, что атрибут длины в массивах JavaScript определен как максимальный индекс + 1.

Причина, по которой он работает так, - вы можете сделать for(var i = 0; i < A.length; i++).

Я вижу, вы запутались в распределении массива.Вам кажется, что JavaScript заполнил элементы неопределенным - на самом деле там ничего нет, но если вы попытаетесь получить доступ к любому элементу в массиве, который не был определен, вы получите undefined.

Answer 2

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

Что-то вроде:

function HashMap() {
  // make an array of 256 buckets
  this.buckets = [];
  for (var i = 0; i < 256; i++) this.buckets.push([]);
}

HashMap.prototype.getHash = function(key) {
  return key % 256;
}

HashMap.prototype.getBucket = function(key) {
  return this.buckets[this.getHash(key)];
}

HashMap.prototype.getBucketItem = function(bucket, key) {
  for (var i = 0; i < bucket.length; i++) {
    if (bucket[i].key == key) return i:
  }
  return -1;
}

HashMap.prototype.setItem = function(key, value) {
  var bucket = this.getBucket(key);
  var index = this.getBucketItem(bucket, key);
  if (index == -1) {
    bucket.push({ key: key, value: value });
  } else {
    bucket[index].value = value;
  }
}

HashMap.prototype.getItem = function(key) {
  var bucket = this.getBucket(key);
  var index = this.getBucketItem(bucket, key);
  if (index == -1) {
    return null;
  } else {
    return bucket[index].value;
  }
}

Отказ от ответственности: код не проверен.