Hash Table Patterns

Hash Table Patterns: Your Magic Dictionary 🗄️

The Story of the Super-Fast Library

Imagine you walk into the world’s biggest library. There are millions of books everywhere! If you had to find one specific book by checking every single shelf, it would take forever, right?

But this library has a magic trick.

When a book arrives, a librarian uses a special formula with the book’s title. This formula instantly tells them: “Put this book on shelf #42, slot #7.”

When you want that book later? Same formula, same answer: “Shelf #42, slot #7.” You walk straight there. No searching at all!

That magic formula? That’s called a hash function.

That organized library? That’s a hash table.

Let’s learn all the patterns to use this magic!

1. Hash Map Fundamentals

What is a Hash Map?

A hash map is like having a personal assistant with perfect memory.

You tell them: “Remember that ‘apple’ means ‘red fruit’.”

Later you ask: “What was ‘apple’ again?”

They instantly answer: “Red fruit!”

In code terms:

• You store key-value pairs (like word-definition pairs in a dictionary)
• You can find any value instantly using its key

// Create your magic dictionary
const fruitColors = new Map();

// Store key-value pairs
fruitColors.set('apple', 'red');
fruitColors.set('banana', 'yellow');
fruitColors.set('grape', 'purple');

// Get values instantly!
console.log(fruitColors.get('apple'));
// Output: 'red'

Why is it SO FAST?

Real Life Example:

Your phone’s contact list is like a hash map:

• Key = Person’s name (“Mom”)
• Value = Phone number (“555-1234”)

You don’t scroll through 500 contacts. You type “Mom” and BOOM - there’s the number!

2. Hash Set Fundamentals

What is a Hash Set?

A Hash Set is like a VIP guest list at a party.

The bouncer has one job: “Is this person on the list?”

• ✅ “Is ‘Taylor’ on the list?” → “YES, let them in!”
• ❌ “Is ‘Random Person’ on the list?” → “NOPE, not here!”

Key difference from Hash Map:

• Hash Map stores pairs (name + phone number)
• Hash Set stores single items (just names)

// Create a VIP guest list
const vipGuests = new Set();

// Add guests
vipGuests.add('Taylor');
vipGuests.add('Beyonce');
vipGuests.add('Drake');

// Check the list
console.log(vipGuests.has('Taylor'));
// Output: true ✅

console.log(vipGuests.has('Me'));
// Output: false ❌

// No duplicates allowed!
vipGuests.add('Taylor');  // ignored
console.log(vipGuests.size);
// Still 3, not 4!

When to Use a Set?

• Finding duplicates in a list
• Checking if something exists
• Removing duplicates from data

3. Hash Collision Resolution

The Problem: Two Keys, One Locker

Imagine your school has 100 lockers numbered 0-99.

The “magic formula” for your locker? Take the last two digits of your student ID.

• Student ID 12345 → Locker 45
• Student ID 98745 → Locker 45

Uh oh! Two students, same locker number!

This is called a collision.

Solution 1: Chaining (Share the Space)

Make each locker hold a list of items instead of just one.

Locker 45: [ (12345, "Alex's stuff"),
             (98745, "Jordan's stuff") ]

When you search:

1. Go to locker 45
2. Check each item until you find your ID

// Behind the scenes, this is what happens
class HashTableWithChaining {
  constructor() {
    this.buckets = new Array(10)
      .fill(null).map(() => []);
  }

  hash(key) {
    return key % 10; // Simple hash
  }

  set(key, value) {
    const index = this.hash(key);
    // Add to the chain (array) at this bucket
    this.buckets[index].push([key, value]);
  }
}

Solution 2: Open Addressing (Find Another Spot)

If locker 45 is taken, try locker 46. If that’s taken, try 47…

Keep looking until you find an empty one!

Student 12345 → Locker 45 ✅ (empty, take it!)
Student 98745 → Locker 45 ❌ → 46 ✅ (take it!)

4. Two Sum Pattern

The Challenge

You have a list of numbers. Find two numbers that add up to a target.

Example: Numbers: [2, 7, 11, 15], Target: 9

Answer: 2 + 7 = 9! Return positions [0, 1].

The Slow Way (What NOT to do)

Check every possible pair:

• 2+7=9? ✅ Found it!

But with 1000 numbers, you’d check almost 500,000 pairs!

The Smart Way: Hash Map Magic!

Key Insight: If you need 9, and you have 2, you NEED 7.

So instead of looking for pairs, look for the complement!

function twoSum(nums, target) {
  const seen = new Map();  // number → its position

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];  // What do I need?

    if (seen.has(need)) {
      // Found it! Return both positions
      return [seen.get(need), i];
    }

    // Remember this number for later
    seen.set(nums[i], i);
  }

  return [];  // No solution found
}

// Example walkthrough:
// i=0: have 2, need 7, seen={} → nope
//      seen={2:0}
// i=1: have 7, need 2, seen={2:0} → YES!
//      Return [0, 1]

Why This Works

graph TD
    A["See number 2"] --> B{Is 7 in our map?}
    B -->|No| C["Store 2 → position 0"]
    C --> D["See number 7"]
    D --> E{Is 2 in our map?}
    E -->|YES!| F["Return positions!"]

5. Frequency Counting

The Mission

Count how many times each item appears!

Example: “How many of each fruit do we have?”

Basket: ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']

The Pattern

function countFruits(basket) {
  const count = new Map();

  for (const fruit of basket) {
    // Get current count (0 if first time)
    const current = count.get(fruit) || 0;
    // Add one more
    count.set(fruit, current + 1);
  }

  return count;
}

const result = countFruits(
  ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
);

// result:
// apple → 3
// banana → 2
// cherry → 1

Real-World Uses

Anagram Example

Two words are anagrams if they have the same letter counts.

“listen” and “silent” both have: e=1, i=1, l=1, n=1, s=1, t=1

function areAnagrams(word1, word2) {
  if (word1.length !== word2.length) return false;

  const count = new Map();

  // Count letters in word1
  for (const char of word1) {
    count.set(char, (count.get(char) || 0) + 1);
  }

  // Subtract letters in word2
  for (const char of word2) {
    const current = count.get(char);
    if (!current) return false;  // Letter not in word1!
    count.set(char, current - 1);
  }

  // All counts should be 0
  for (const value of count.values()) {
    if (value !== 0) return false;
  }

  return true;
}

6. Grouping by Key

The Mission

Organize items into groups based on something they share!

Example: Group students by their first letter of name.

const students = ['Alice', 'Adam', 'Bob', 'Charlie', 'Cindy'];

The Pattern

function groupByFirstLetter(names) {
  const groups = new Map();

  for (const name of names) {
    const key = name[0];  // First letter

    if (!groups.has(key)) {
      groups.set(key, []);  // Create empty group
    }

    groups.get(key).push(name);  // Add to group
  }

  return groups;
}

// Result:
// 'A' → ['Alice', 'Adam']
// 'B' → ['Bob']
// 'C' → ['Charlie', 'Cindy']

Group Anagrams Example

Put words that are anagrams together!

“eat”, “tea”, “ate” → all anagrams → same group!

function groupAnagrams(words) {
  const groups = new Map();

  for (const word of words) {
    // Sort letters to create a "signature"
    const key = word.split('')
                    .sort()
                    .join('');

    if (!groups.has(key)) {
      groups.set(key, []);
    }

    groups.get(key).push(word);
  }

  return [...groups.values()];
}

// Input: ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
// Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

7. Subarray Sum Equals K

The Challenge

Find how many continuous chunks of an array add up to a target!

Example: Array: [1, 2, 3], Target K: 3

• [1, 2] = 3 ✅
• [3] = 3 ✅

Answer: 2 subarrays!

The Magic: Prefix Sums + Hash Map

Key Insight: If the sum from start to position j is 10, and the sum from start to position i is 7, then the sum from i+1 to j is 10-7 = 3!

graph LR
    A["Start"] -->|sum=7| B["Position i"]
    B -->|this chunk=3| C["Position j"]
    A -->|sum=10| C

If you need a subarray summing to K=3:

• Current prefix sum = 10
• Look for an earlier prefix sum = 10 - 3 = 7
• If it exists, you found a valid subarray!

The Code

function subarraySum(nums, k) {
  let count = 0;
  let prefixSum = 0;
  const prefixCounts = new Map();

  // Important: empty prefix (sum 0) appears once
  prefixCounts.set(0, 1);

  for (const num of nums) {
    prefixSum += num;

    // Need to find: prefixSum - k
    const need = prefixSum - k;

    if (prefixCounts.has(need)) {
      count += prefixCounts.get(need);
    }

    // Record this prefix sum
    prefixCounts.set(
      prefixSum,
      (prefixCounts.get(prefixSum) || 0) + 1
    );
  }

  return count;
}

// Example: [1, 1, 1], k = 2
// Prefix sums: 1, 2, 3
// Subarrays summing to 2: [1,1] and [1,1] = 2

Step-by-Step Walkthrough

Summary: Your Hash Table Toolkit 🧰

Your Journey Forward 🚀

You now have the keys to the magic library! Hash tables transform slow, painful searches into instant lookups. Every pattern you learned today is used in real apps, from social networks to search engines.

Remember: The hash function is your magic formula. The hash table is your organized kingdom.

Now go practice, and make your code lightning fast!