Data structures - Hash Tables

hashtable.js

// Hash Tables
// The rate of collusion is determined by how good the hash function is
// - A good hashing function is the key to an efficient hash table
// Search - best case O(1), worst case O(n) (based on the frequency of collusions)

// Handling collisions
// - seperate chaning *
// - open addressing

// Insert => O(1);
// Delete => O(1);
// Search => O(1) worst case O(n);
// Space => O(n);

function hashFunc(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % size;
}

function HashTable(size) {
  this.list = new Array(size);
  this.size = size;
}

HashTable.prototype.set = function(key, value) {
  const index = hashFunc(key, this.size);
  if (!this.list[index]) {
      this.list[index] = []
  }
  this.list[index].push([key, value]);
  this.size = this.list.length;
};


HashTable.prototype.get = function(key) {
  const index = hashFunc(key, this.size);

  if (!this.list[index]) {
     return null;
  }
  for (let i = 0; i < this.list[index].length; i++) {
    if (this.list[index][i][0] === key) {
      return this.list[index][i][1];   
    }
  }
}


let a = new HashTable(3);

a.set("x", 12);

console.log(a.get("t")); // null

a.set("y", 13);
a.set("z", 14);

console.log(a.get("x")); // 12
console.log(a.get("z")); // 14
console.log(a.get("y")); // 13