Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in JavaScript

Building a Hash Table from Scratch

Explore the process of constructing a hash table from scratch in JavaScript by implementing a bucket chaining strategy to handle collisions. Understand how to create hash entries and the hash table class while managing resizing and hash functions to optimize data storage and retrieval.

We'll cover the following...

Hash Table Using Bucket Chaining

We will use the chaining strategy along with the resize operation to avoid collisions in the table.

All elements with the same hash key will be stored in an array at that index. In data structures, these arrays are called buckets. The size of the hash table is set as n*m where n is the number of keys it can hold, and m is the number of slots each bucket contains. Each slot holds a key/value pair.

Implementation

We will start by building a simple HashEntry class. As discussed earlier, a typical hash entry consists of three data members: the key, the value and the reference to a new entry. Here’s how we will code this in JavaScript:

Node.js
class HashEntry{
    constructor(key, data){
        this.key = key;
        // data to be stored
        this.value = data;
        // reference to new entry
        this.next = null;
    }
}
        
let entry = new HashEntry(3, "Educative");
console.log (String(entry.key) + ", " + entry.value);

Now, we’ll create the HashTable class which is a collection of HashEntry objects. We will also keep track of the total number of slots in the hash table and the current size of the hash table. These two variables​ will come in handy when we need to resize the table.

Here is the basic implementation in JavaScript:

Node.js
class HashTable{
  //Constructor
  constructor(){
    //Size of the HashTable
    this.slots = 10;
    //Current entries in the table
    //Used while resizing the table when half of the table gets filled
    this.size = 0;
    //Array of HashEntry objects (by deafult all None)
    this.bucket = [];
    for (var i=0; i<this.slots; i++){
      this.bucket[i]=null;
    }
  }
  //Helper Functions  
  get_size(){
    return this.size;
  }
  isEmpty(){
    return this.get_size() == 0;
  }
}
  
let ht = new HashTable();
console.log(ht.isEmpty());

The last thing we need is a hash function. We tried out some different approaches in the previous lessons. For our implementation, we will simply take the modular of the key with the total size of the hash table (slots).

Node.js
//Hash Function
getIndex(key){
	let index = key % this.slots;
	return index;
}