Hashmaps in javascript from integer keys

Question

I am coding in javascript & I need HashMap type structure . Normally when I need hashmaps , I would use associative arrays only (with strings as keys). But this time I need integers as keys to hashmaps.

So if I try to store A[1000]=obj, 1001 sized array is created & A[1001] is put as obj. Even if I try A["1000"]=obj , it still allocates 1001 spaces & fills them with undefined.

I dont want that as my keys could be very large ( around 1 mill). I could use it as A["dummy1000"]=obj but I dont want to use this dirty method.

Anyway of doing it elegantly & with ease too ?

Answer 1

Create a hash code from the key, and use that as index. Make the hash code limited to a small range, so that you get a reasonably small array of buckets.

Something like:

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;
  }
}

Disclaimer: Code is not tested.

Answer 2

Doing A[1000] = 1 doesn't create an array with 1000 elements. It creates an array object whose length attribute is 1001, but this is only because the length attribute in JavaScript arrays is defined as the maximum index + 1.

The reason it works like this is so you can do for(var i = 0; i < A.length; i++).

I see you're confused about the allocation of the array. To you it looks like JavaScript has filled the elements with undefined - actually there isn't anything there, but if you try to access any element in an array that hasn't been defined you get undefined.