Hash Table

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


HashTable.prototype.insert = function(key, value) {
  var index = this.hashFunc(key, this._limit);
  var bucket = this._storage[index]
  if (!bucket) {
    var bucket = [];
    this._storage[index] = bucket;
  }

  var override = false;
  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
    bucket.push([key, value]);
    this._count++;
    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;
  }
  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    if (tuple[0] === key) {
      bucket.splice(i, 1);  //delete this tuple
      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);
  return this._storage;
};

The fastest way of storing and retrieving an item is to use index array. We get put in 1 cycle. This approach is great at beginning, but as we put more and more items in the indexed storage slots, we start to forget which ones have already been occupied and which ones are empty. As a result, we tend to put more and more items in our favorite slots, so those slots getting cluttered and finding things becoming harder and harder. We don't have to suffer this, there are plenty of empty slots out there, why don't we distribute the items. The simple answer is, we can't, as human, our choice of slot index are always biased and we don't want to waste time to exam all the slots to find the empty ones neither. We need to break our bias, so we write a function to choose the index. The function takes the item, give us a random number. This randomness removes the bias, so we distribute the items evenly across the slots. The "random" number is actually not pure random, next time, when we give the item and ask that function for the index, it must give us the exact same "random" number, otherwise, we will loose trace of the item. That magic function is called hash function. Mathematicians did their job to find the way to map an object to the same random number across function calls, its array index. We call that function to find the index before put an item to an array or get an item from that array. That is the essence of hash table.

https://xyzcode.blogspot.com/2020/02/seperatechainstjava.html