Hash Table - Data Structures in JavaScript: Part #4

Hash table is a data structure that implements an associative array. An associative array is a structure that can map keys to values. In JavaScript, an object can act as an associative array.

ECMAScript 2015 introduced a new data structure Map to map keys to values.

To add a key-value pair into a hash table, we take a key and pass it through a hash function, which will output a number that corresponds to an index in an array of buckets. This is what we call hashing.

Buckets/slots are placeholders in a hash table where we will store values. They are often set with an initial max capacity.

Hash functions are:

• Irreversible - you cannot take the output of a hash function put into the same hash function and get the original data (input) back.
• Consistent - if you put an input in a hash function over and over again, you should expect the same result each time.

To retrieve an item from a hash we take a key, run it through that same exact hash function and then directly access that bucket in the array where the value is stored.

It is possible to have two or more different inputs return the same output. This is called a collision. To handle collisions we just store the key-value pairs at that same index using other collections like an array or linked list.

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


//hash table
class HashTable {
 constructor() {
   this.size = 10
   this.buckets = Array(this.size)

 // populate each bucket with a Map()
   for (let i = 0; this.buckets.length; i++) {
     this.buckets[i] = new Map()
   }
 }

 insert(key, value) {
   let idx = hash(key, this.size)
   this.buckets[idx].set(key, value)
 }


 remove(key) {
   let idx = hash(key, this.size)
   let deleted = this.buckets[idx].get(key)
   this.buckets[idx].delete(key)
   return deleted
 }


 search(key) {
   let idx = hash(key, this.size)
   return this.buckets[idx].get(key)
 }
}