Hello 🙂  in this section we will talk about hash tables in Data Structures and Algorithms. Hash table is one of the lovely Data Structures you don’t want to miss out on as it provides a better and efficient way or accessing, inserting and deleting from a data structure operation. A Hash table/map is a Key value pair Data structure in which every value is an indices of it’s position in the table. So the process of mapping a value to it’s index relation is called Hashing and sometimes we refer to a hash table as mapping. Say we have a key represented by k then the hash function of any number x is denoted as h(x)=k. Think of a hash table as a vertical array or a JavaScript Object. the power of a hash function can not be describe in this section but it’s being used in almost every programming language and systems especially in security sectors and online transaction processes. widely used in crypto process and in fact it has become one of the best ways to store sensitive information throughout the web of these days where security poses a huge problem in our terms of privacy. there wouldn’t be a need to re-invent the wheels anyway but it worth knowing how hashing it’s done as it forms part of you being a software engineer. in the domain a lot of top senior engineers works tirelessly to improve many of these methods. Well enough of the history now let’s see how a basic hashing can be written or translated into codes.

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }
}

A hash table in a nut shell just consist of the size of the array on which the mapping is to be done as it plays a big role in allocating the index and the portion to any hashed key in memory.
Hashing basically will accept a key to be hashed where several methods can be used to encrypt the given key in such a way that it is deterministic which means if the same key is to hashed any number of times it gives as the same value to be store in the table. so let’s say a table of array size 10 and a given set of values from 1 to 7, in the event of allocation a key to these numbers we can say 1 will map to the index 1 of the array, 2 —> index 2, 3 —> index 3, etc….. until all the values are allocated to the memory. This is done in order to have an easy way of retrieval when we need to pull the value of x from the k key in our h(x) function.

Actually doing tis comes with some prices in some context, assuming we have the same values to be stored in one index match memory that means the in a a one to one function it’s absolutely a no go because only one value can be assign to one index, this is what we call Hash Collusion where a hash table generate the same index for multiple identical values. fortunately enough we have various solutions to this challenges in a hash table. One of the solution is by Chaining where force all the elements to be stored in the same index by using Doubly Linked list where all the elements will have a link that remember where they’re coming from by having their next and previous values in memory. We can equally use Nested arrays (Arrays in Array) to solve the same problem. Another popular solution to this anomaly is Linear or Quadratic probing  where instead of chaining where there is a duplicate we just move to the next available slot. So let’s say if the collusion occurs at index 2 then the next index ie 2+1 is used to store the collusion value if available to when retrieving the values and at the index where there is a mismatch then that value is considered a group of it’s preceding one, the problem with Linear probing is doing so will put element in a cluster close to each other that might not belong to their right slot preventing some very close element to rather shift to a remote part from their rightful place so introducing  Quadratic Probing which is the same as the Linear but in this case element are jumped by the square of where they should be paving ways for lucky element to feature in their right slot preventing longer time taken to traverse looking for them. Other methods are out there which also make sense to solve the same problems.

We also talk about a Good Hash Method which obviously will prove to be much better that other methods and despite the fact they will be preferred over other they may not be able to totally prevent the collusions in the hash table partitions or mapping but will definitely help to reduce the as mush as possible. There are 3 popular Methods that help Achieve this process ie. Division, multiplication and hashing. the full implementation of the hash table is written bellow, take a look and try to make your ways out of it.

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }
  set(key, value) {
    let index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  get(key) {
    let index = this._hash(key);
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          return this.keyMap[index][i][1];
        }
      }
    }
    return undefined;
  }
  keys() {
    let keysArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!keysArr.includes(this.keyMap[i][j][0])) {
            keysArr.push(this.keyMap[i][j][0]);
          }
        }
      }
    }
    return keysArr;
  }
  values() {
    let valuesArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!valuesArr.includes(this.keyMap[i][j][1])) {
            valuesArr.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    return valuesArr;
  }
}

let ht = new HashTable(17);

ht.set('maroon', '#800000');
ht.set('yellow', '#FFFF00');
ht.set('olive', '#808000');
ht.set('salmon', '#FA8072');
ht.set('lightcoral', '#F08080');
ht.set('mediumvioletred', '#C71585');
ht.set('plum', '#DDA0DD');
ht.set('purple', '#DDA0DD');
ht.set('violet', '#DDA0DD');

ht.keys().forEach(function (key) {
  console.log(ht.get(key));
});

in a hash table like I said they have very good time complexity on their average case as O(1) Constant time which is the highest score we can get. in some cases we approach o(log n) which seems to be fairly very good if you ask me.
Insert O(1) Constant time
Deletion O(1) Constant time
Access O(1) Constant time.

hash table are actually not a crack head if time is taken to go through patiently.

Until next time Stay Safe 🙂