Deep Dive into Hash Maps: Building a Hash Map with JavaScript

Introduction

Today, we’ll focus on an essential and efficient data structure known as the Hash Map.

Hash maps are known by various names across different programming languages and contexts. They are also called Dictionaries, Hash Tables, Objects, or just Maps in some languages.

What is a Hash Map?

A Hash Map is like a virtual shelf, where each shelf has a name, called a key, and something stored on it, called a value. The key leads you to the exact 'shelf' or value you need.

A special function called the hash function translates the key into a specific shelf number.

For example, in JavaScript, we have the built-in Map object that encapsulates this hash map. It lets us set, get, and delete key-value pairs in an optimized manner.

let myHashMap = new Map();  // Creating our hash map

myHashMap.set("apple", "fruit");  // Setting a key-value pair
myHashMap.set("carrot", "vegetable");  // Another pair

let category = myHashMap.get("apple");  // Fetching the value for the key "apple"

When to Use Hash Maps

Hash Maps are excellent when you need fast access to data using unique keys.

They’re often used in databases to retrieve your data or in caching systems, where speed is crucial.

Many of these utilize Hash Maps under the hood, offering stellar performance even with millions of entries.

Big O Complexities of Hash Map Operations

With Hash Maps, you can quickly insert, delete, or search for a value, usually in constant time, O(1). This efficiency comes from the hash function that directly computes the index of the value in the table.

Insertion (O(1)): You can quickly place a value in the hash map by computing its position using the hash function.

Deletion (O(1)): Similar to insertion, you can directly access and delete a value using its key.

Search (O(1)): Searching is rapid because the hash function leads you directly to the value.

Hash Map Collisions

However, there are times when two distinct keys, after hashing, aim for the same spot. This is what we call a hash map collision.

In cases where collisions occur, our hash map operations might take longer due to the need to search through the collided items.

But there are various strategies to resolve these collisions:

1. Chaining: Where each slot maintains a list of all its entries.

2. Open Addressing: If a spot is taken, we simply find the next available one.

Implementing a Hash Map in JavaScript

Let’s see how to create a basic Hash Map from scratch in JavaScript.

First, we need to set the size of our hash map (tableSize) and a table that will store our key-value pairs.

class HashMap {
  constructor(tableSize = 16) {
    this.table = new Array(tableSize);
    this.tableSize = tableSize;
  }
}

Then, we need a hash function to translate our keys into hash codes.

hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {
      hashValue = (hashValue + key.charCodeAt(i) * i) % this.tableSize;
    }
    return hashValue;
}

This function creates a unique number for each unique key. It uses a for loop to create each unique number, but since in most hash table use cases, the keys have a relatively fixed, small size (like strings of reasonable length), in practice, this computation is still treated as a constant time operation, and the hash function is considered to be O(1).

Now, let’s add the key-value pairs to our Hash Map. We’ll call this method set.

set(key, value) {
    const index = this.hash(key);
    this.table[index] = value;
}

We can also remove key-value pairs from our Hash Map. We’ll create a remove function for that.

remove(key) {
    const index = this.hash(key);
    delete this.table[index];
}

Finally, let’s create a get function to find a value by its key in our Hash Map. Our full implementation of HashMap will look like this:

class HashMap {
  constructor(tableSize = 16) {
    this.table = new Array(tableSize);
    this.tableSize = tableSize;
  }

  hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {
      hashValue = (hashValue + key.charCodeAt(i) * i) % this.tableSize;
    }
    return hashValue;
  }

  set(key, value) {
    const index = this.hash(key);
    this.table[index] = value;
  }

  remove(key) {
    const index = this.hash(key);
    delete this.table[index];
  }

  get(key) {
    const index = this.hash(key);
    return this.table[index];
  }
}

And there you have it! A basic Hash Map implemented in JavaScript.

Quick Recap

Hash Maps offer near-instantaneous data access by associating keys and values. Their primary operations — Set, Get, and Delete — are ultra-fast, usually O(1).

While collisions can be a bump in the road, efficient resolution still keeps Hash Maps performing super fast.

If you’re interested more about how to apply hash maps in coding problems check out my other article on Solving a LeetCode problem using Hash Maps

.