Imagine you're in a vast library with millions of books 📚. How do you find the exact book you're looking for without spending hours searching through every shelf? 🕵️‍♀️ The answer lies in the library's catalog system - a powerful tool that allows you to locate any book in seconds ⚡. This is precisely the real-world analogy of a Hash Table, a fundamental data structure that enables lightning-fast data storage and retrieval 🚀.

Hi 👋, welcome to this article on Hash Tables! In this article, we'll be demystifying Hash Tables 🧩, exploring their inner workings and implementing them in JavaScript.

Before we move on, let's take a look at what we'll be covering in this article:

Table of Contents

• Introduction
• What is a Hash Table?
• Common Terminologies Used in Hash Tables
• How Hash Tables Work
• Implementing a Hash Table in JavaScript
  • Creating the Hash Table
  • Adding Values to the Hash Table
  • Retrieving Values from the Hash Table
  • Removing Values from the Hash Table
  • Checking if a Value exists in the Hash Table
• Conclusion

Introduction

The importance of Hash Tables in the world of programming cannot be overstated. They are the backbone of many real-world applications, from database indexing to caching systems, and from compilers to blockchain technology. Moreover, Hash Tables are a favorite topic in coding interviews, making them an essential skill for any aspiring software developer.

You might be wondering why we need a Hash Table in the first place. A Hash Table is a data structure designed to be fast to work with.

The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.

In a Linked List, finding a person "Esther" takes time because we would have to go from one node to the next, checking each node, until the node with "Esther" is found.

And finding "Esther" in an Array could be fast if we knew the index, but when we only know the name "Esther", we need to compare each element (like with Linked Lists), and that takes time.

With a Hash Table however, finding "Esther" is done really fast because there is a way to go directly to where "Esther" is stored, using something called a hash function.

In this comprehensive article, we'll demystify Hash Tables, explore their inner workings, implement them in JavaScript, and solve popular LeetCode problems. By the end of this journey, you'll have a solid understanding of Hash Tables and be well-equipped to optimize your code and ace your next coding interview.

That being said, let's dive into the world of Hash Tables!

What is a Hash Table?

A hash table is a data structure that allows you to store data in key-value pairs and quickly access it using a key. Think of it like a dictionary or a phone book, where you can look up information (value) by a name (key). A hash table is a data structure that stores values using keys. It uses a hash function to compute an index into an array in which an element will be stored.

Common Terminologies Used in Hash Tables

How Hash Tables Work

Again, let use the analogy of a vast library of books to get key insight into how Hash Table works. Think of a hash table like a library where you want to store books on shelves, but instead of just throwing them anywhere, you use a clever way of organizing them.

Here’s how it works step-by-step:

Step 1: Hashing is Like Labeling the Book
When you have a book, you need to figure out where to place it in the library. You don’t just choose a random shelf. Instead, you calculate the shelf number based on the book’s title.

This is where the hash function comes in. A hash function is like a special librarian that looks at the title of a book (like the key in a hash table) and decides which shelf the book should go on (like the index in an array). For example:

• Title: "Alice in Wonderland"
• The librarian (hash function) checks the title and decides: "Put it on Shelf 3." It calculates a shelf number based on the title in a consistent way, so every time you bring "Alice in Wonderland," it will always tell you to use Shelf 3.

Step 2: Storing the Book (Key-Value Pair)
In a hash table, each shelf is actually a bucket. When you know the shelf number (from the hash function), you place the book (value) on that shelf.

• You store the book (value) along with its title (key) on the shelf.
  This key-value relationship ensures that you can easily find the book later.
  For example:

• Shelf 3 (bucket) now contains:

  • "Alice in Wonderland" → 555-1234 (phone number)

Step 3: Retrieving a Book (Getting a Value)
Let’s say you want to find the phone number for "Alice in Wonderland". The hash table process works as follows:

• You go to the librarian (hash function) and ask, "Where is 'Alice in Wonderland'?"
• The librarian calculates the same shelf number: Shelf 3.
• You walk over to Shelf 3 and find the book, which has the phone number 555-1234. This is the efficiency of a hash table: It doesn't need to search every shelf; it knows exactly where to look!

Step 4: Handling Collisions (Multiple Books on One Shelf)
Sometimes, two books may end up on the same shelf (because of the way the hash function works). This is called a collision.

For example:

• "Alice in Wonderland" and "Anna Karenina" might both be placed on Shelf 3. When you retrieve a book from Shelf 3, you might have multiple books there, so you just look through the few that are on that shelf. This is why buckets sometimes contain more than one key-value pair.

This structure is highly efficient and is used for fast data retrieval in many applications, such as dictionaries and databases.

Implementing a Hash Table in JavaScript

Let's roll up our sleeves and implement a simple Hash Table in JavaScript. We'll go through this process step-by-step, explaining each part of the implementation.

When it comes to implementing a Hash Table, the first thing we need to do is to create a hash function. This hash function will take a key and return an index in the array where the value should be stored. To implement this, we'll use a simple algorithm that involves multiplying by a prime number and taking the modulo with the array length.

A hash map uses a simple array (or a list of buckets) to store data. The data is accessed by using a key and the hash function maps that key to an index in the array.

• Hash Map: We'll represent the hash map as an array.
• Hash Function: This will take a string key, convert it into a hash code (an index in the array), and return that index. The hash function needs to ensure that keys are mapped to valid indices within the array bounds.

Let's start by creating our Hash Map class and the hash function:

Creating the Hash Table

// Hash Map class
class HashTable {
  constructor(size) {
    this.size = size; // size of the hash map (number of buckets)
    this.buckets = new Array(size); // create an array of the given size (buckets)
  }

  // Hash function to generate an index based on the key
  _hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {
      hashValue += key.charCodeAt(i); // get the ASCII value () of each character and sum it
    }
    return hashValue % this.size; // ensure the index is within the bounds of the array
  }
}

// Create a hash map of size 10 and test the hash function
let myHashTable = new HashTable(10);
console.log(myHashTable._hash("Alice")); // This will return the index for "Alice"
console.log(myHashTable._hash("Bob")); // This will return the index for "Bob"

Explanation:

1. We created a HashTable class with a size and an array of buckets (empty spots).
2. The hash function (_hash) takes a key, sums up the ASCII values of the characters, and modulo the result by the size of the array to ensure the result stays within the array’s bounds.
3. This function is private (indicated by _) because we don't want it to be directly accessible outside the class.

ASCII, which stands for American Standard Code for Information Interchange, is a character encoding standard used to represent text in computers and other devices that use text. It is a 7-bit code, meaning it uses seven bits to represent a character, allowing for 128 possible characters (0-127). The ASCII table includes control characters (0-31 and 127), printable characters (32-126), and extended ASCII characters (128-255).

Now that we can generate an index from a key, the next step is to insert values into the hash table. We'll create a function called set that:

Adding Values to the Hash Table

Now that we can generate an index from a key, the next step is to insert values into the hash map. We'll create a function called set that:

1. Takes a key-value pair.
2. Uses the hash function to find the index (bucket) where the value should be stored.
3. Adds the key-value pair into that bucket. We will use chaining (a list at each bucket) to handle potential collisions (when two keys map to the same bucket).

// Add values to the hash map

set(key, value) {
  const index = this._hash(key); // Get the index for the key

  // Initialize the bucket if it's empty
  if (!this.buckets[index]) {
    this.buckets[index] = []; // Use an array to handle multiple values (chaining)
  }

  // Add the key-value pair to the bucket
  this.buckets[index].push([key, value]);
  console.log(`Set ${key}: ${value} at index ${index}`);
}

// Example of adding values
myHashMap.set("Alice", "555-1234");
myHashMap.set("Bob", "555-5678");
myHashTable.set("Charlie", "555-9999");

Explanation:

• The set method uses the hash function to find the correct index.
• If the bucket at that index is empty, it initializes an empty list.
• The key-value pair is then pushed into that bucket.
• This implementation handles collisions by chaining—storing multiple key-value pairs in a list if two keys map to the same bucket.

Retrieving Values from the Hash Table

Once we've inserted values, the next logical step is to retrieve values. We'll create a function get that:

1. Takes a key.
2. Uses the hash function to find the index (bucket) where the value should be stored.
3. Searches the bucket for the key and returns the value if found.

// Retrieve values from the hash map

get(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket at that index exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      return pair[1]; // Return the value if the key is found
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of retrieving values
console.log(myHashMap.get("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Bob"));     // Should print "555-5678"
console.log(myHashMap.get("Charlie")); // Should print "555-9999"
console.log(myHashMap.get("Dave"));    // Should print null (not found)

Explanation:

• The get function finds the index for the key using the hash function.
• If the bucket at that index is empty, it returns null because the key doesn't exist.
• If there are multiple entries in that bucket (due to collisions), the function searches through the list to find the correct key and returns its value.

Removing Values from the Hash Table

To complete the basic operations of a hash table, we'll add a method to remove a key-value pair. This function will:

1. Take a key.
2. Use the hash function to find the bucket.
3. Remove the key-value pair if found.

// Remove values from the hash map

// Remove values from the hash map
remove(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      this.buckets[index].splice(i, 1); // Remove the key-value pair from the bucket
      return pair[1]; // Return the removed value
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of removing values
console.log(myHashMap.remove("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Alice"));      // Should now print null (not found)

Explanation:

• The remove function searches for the key in the appropriate bucket and removes the key-value pair if found.
• After removal, it returns the value that was removed.
• If the key doesn't exist, it returns null.

Checking if a Value exists in the Hash Table

The contains function will:

1. Loop through all the buckets in the hash map.
2. Check each key-value pair in the bucket.
3. Return true if the value is found, and false if it's not.

// Check if the hash map contains a specific value
contains(value) {
  // Loop through all the buckets
  for (let i = 0; i < this.size; i++) {
    const bucket = this.buckets[i];

    // If the bucket exists, search through its key-value pairs
    if (bucket) {
      for (let j = 0; j < bucket.length; j++) {
        const pair = bucket[j];
        if (pair[1] === value) { // Check if the value matches
          return true; // Return true if the value is found
        }
      }
    }
  }

  return false; // Return false if the value is not found in any bucket
}

// Example of checking for values
console.log(myHashMap.contains("555-1234")); // Should return false (because Alice was removed)
console.log(myHashMap.contains("555-5678")); // Should return true (Bob's number)
console.log(myHashMap.contains("555-9999")); // Should return true (Charlie's number)
console.log(myHashMap.contains("555-8888")); // Should return false (not found)

Explanation:

• The contains function loops through each bucket in the hash map.
• If the bucket exists (i.e., it contains some key-value pairs), it checks whether any value in that bucket matches the value we are looking for.
• If it finds a match, it returns true; otherwise, after searching all buckets, it returns false.

Conclusion

Hash Tables are a powerful and versatile data structure that offer efficient data storage and retrieval. Through this guide, we've explored their inner workings, implemented them in JavaScript, and solved several LeetCode problems that leverage their strengths.

In our next article, we'll be solving some LeetCode problems that use Hash Tables. Until then, happy coding!

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀