Imagine you're managing a massive wall of 1,000 mailboxes in a corporate office. If you had to find a specific person's mail by checking every single box one by one, you'd be there all day. That's an $O(n)$ operation, and it's a nightmare. Instead, you decide to use a system: you take the employee's name, run it through a specific formula—maybe adding up the alphabet positions of the letters—and that formula tells you exactly which mailbox number to go to. You don't search; you just jump straight to the box.

That's exactly how a Hash Table works. We take a key (like a username), pass it through a hash function to get an index (the mailbox number), and store our value (the user's profile data) at that index in an underlying array.

Turning Strings into Numbers

The heart of this whole thing is the hash function. Its job is to take any string and turn it into a number that fits within the bounds of our array. I usually prefer a simple prime-number multiplier to reduce the chance of two different keys ending up with the same index.

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

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      // 31 is a prime number that helps distribute keys more evenly
      hash = (hash << 5) - hash + key.charCodeAt(i);
      hash |= 0; // Convert to a 32bit integer
    }
    return Math.abs(hash) % this.size;
  }
}

Notice that I used a private-ish method _hash. You don't want the outside world messing with how keys are mapped; they just want to set and get data.

The Collision Headache

Here is the reality: no hash function is perfect. Eventually, two different keys—say "JohnDoe" and "JaneSmith"—will hash to the exact same index. In our mailbox analogy, this is like two employees being assigned the same box. If we just overwrite the data, we lose "JohnDoe's" mail.

To fix this, we use a technique called Separate Chaining. Instead of storing the value directly in the array slot, we store a smaller array (a "bucket") at that slot. If multiple keys land there, we just push them all into that bucket as pairs.

Wiring Up Set and Get

Now that we have a way to handle collisions, we can implement the logic to actually store and retrieve data. When we set a value, we check if the key already exists in the bucket to update it; otherwise, we push a new pair. When we get, we find the bucket and loop through it until we find the matching key.

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

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash << 5) - hash + key.charCodeAt(i);
      hash |= 0;
    }
    return Math.abs(hash) % this.size;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    
    // Check if the key already exists in the bucket to update it
    for (let pair of this.buckets[index]) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (bucket) {
      for (let pair of bucket) {
        if (pair[0] === key) return pair[1];
      }
    }
    return undefined;
  }
}

It's a bit more work than using a plain JavaScript object, but understanding this is crucial. Objects and Map in JS are actually hash tables under the hood. When you write this from scratch, you realize that the "magic" of $O(1)$ lookup is really just a clever combination of math and array indexing.

📋 Practical Task

Implementing a High-Performance Word Frequency Tracker

Your task is to extend the HashTable class to create a word frequency counter. This is a common real-world use case for hash tables, such as in search engine indexing or basic natural language processing.

Requirements:

• Implement a method called increment(word). If the word doesn't exist in the table, it should be added with a value of 1. If it does exist, its current value should be incremented by 1.
• Implement a method called getFrequency(word) that returns the count of how many times that word has been seen.
• Create an instance of your HashTable and process the following string: "the quick brown fox jumps over the lazy dog the fox is quick".
• Log the frequency of the word "the" (should be 3) and "fox" (should be 2) to the console.