Hash Table Patterns

Hash Table Patterns: Your Magic Dictionary 📚

Imagine you have a magic box where you can toss in any toy with a special label, and instantly find it again later—no digging through piles! That’s what a Hash Table does for your data.

The Big Picture: Lockers at School 🎒

Think of a row of lockers. Each locker has a number. You put your lunchbox in locker #7, and whenever you need it, you go straight to #7—no searching every locker!

A Hash Table works the same way:

1. Key = The label you give (like “lunchbox”)
2. Hash Function = A magic formula that turns the key into a locker number
3. Value = What you store inside (your actual lunchbox)

1. Hash Map Fundamentals

What Is a HashMap?

A HashMap stores key-value pairs. You give it a key, it gives you the value—super fast!

Simple Example:

HashMap<String, Integer> ages =
  new HashMap<>();
ages.put("Alice", 10);
ages.put("Bob", 12);

int aliceAge = ages.get("Alice");
// Returns 10

Real Life:

• Phone contacts: Name → Phone number
• Dictionary: Word → Definition
• Student grades: Student ID → Score

How It Works (Behind the Scenes)

graph TD
    A["Key: Alice"] --> B["Hash Function"]
    B --> C["Index: 3"]
    C --> D["Bucket 3: Alice=10"]

The hash function turns “Alice” into a number (index). That number tells us exactly where to store or find Alice’s data!

2. Hash Set Fundamentals

What Is a HashSet?

A HashSet is like a HashMap but it only stores keys—no values attached. It answers one question: “Is this item in the set?”

Simple Example:

HashSet<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("apple"); // Ignored! Already there

System.out.println(fruits.size());
// Prints 2 (no duplicates!)

Real Life:

• Guest list: Check if a name is invited
• Visited websites: Track which pages you’ve seen
• Unique words: Count distinct words in a book

HashMap vs HashSet

3. Hash Collision Resolution

What’s a Collision?

Imagine two kids—Alice and Adam—both get assigned locker #7 by the magic formula! That’s a collision: two different keys hashing to the same spot.

The Problem:

graph TD
    A["Alice"] --> B["Hash = 7"]
    C["Adam"] --> D["Hash = 7"]
    B --> E["Bucket 7: COLLISION!"]
    D --> E

Solution 1: Chaining (Linked List)

Put multiple items in the same bucket using a list.

Bucket 7: Alice → Adam → null

Each bucket becomes a tiny list. When searching, we check each item in that bucket.

Solution 2: Open Addressing

If bucket 7 is taken, try bucket 8, then 9, and so on until you find an empty spot.

Bucket 7: Alice
Bucket 8: Adam (moved here)

Java’s HashMap uses Chaining! When a bucket gets too crowded, it even upgrades the list to a tree for speed.

4. Two Sum Pattern 🎯

The Classic Problem

Given an array of numbers and a target, find two numbers that add up to the target.

Story Time: You’re at a candy store with $10. You want to buy exactly two candies that cost $10 together. How do you find them quickly?

The Slow Way (Check Every Pair)

// Too slow! O(n²)
for (int i = 0; i < nums.length; i++) {
  for (int j = i+1; j < nums.length; j++) {
    if (nums[i] + nums[j] == target) {
      return new int[]{i, j};
    }
  }
}

The Fast Way (HashMap Magic!)

HashMap<Integer, Integer> seen =
  new HashMap<>();

for (int i = 0; i < nums.length; i++) {
  int need = target - nums[i];
  if (seen.containsKey(need)) {
    return new int[]{seen.get(need), i};
  }
  seen.put(nums[i], i);
}

How It Works:

graph TD
    A["See number 3"] --> B["Need 7 to make 10"]
    B --> C{Is 7 in map?}
    C -->|No| D["Store 3 in map"]
    C -->|Yes| E["Found pair!"]

Time Complexity: O(n) — Just one pass through the array!

5. Frequency Counting 📊

The Pattern

Count how many times each item appears.

Story Time: You have a bag of colorful marbles. How many red? How many blue? A HashMap makes this easy!

The Code

String[] colors =
  {"red", "blue", "red", "green", "red"};

HashMap<String, Integer> count =
  new HashMap<>();

for (String color : colors) {
  count.put(color,
    count.getOrDefault(color, 0) + 1);
}

// Result: {red=3, blue=1, green=1}

Real Uses

• Most common word in a document
• Character frequency for anagrams
• Vote counting in elections
• Find duplicates (count > 1)

Pro Tip: getOrDefault

// Without getOrDefault (messy):
if (map.containsKey(key)) {
  map.put(key, map.get(key) + 1);
} else {
  map.put(key, 1);
}

// With getOrDefault (clean):
map.put(key,
  map.getOrDefault(key, 0) + 1);

6. Grouping by Key 🗂️

The Pattern

Organize items into groups based on a shared property.

Story Time: Imagine sorting your toys into boxes: all cars in one box, all dolls in another. That’s grouping!

The Code

String[] words =
  {"eat", "tea", "tan", "ate", "nat", "bat"};

HashMap<String, List<String>> groups =
  new HashMap<>();

for (String word : words) {
  char[] chars = word.toCharArray();
  Arrays.sort(chars);
  String key = new String(chars);

  groups.computeIfAbsent(key,
    k -> new ArrayList<>()).add(word);
}

// Result:
// "aet" -> [eat, tea, ate]
// "ant" -> [tan, nat]
// "abt" -> [bat]

Real Uses

• Group anagrams (words with same letters)
• Students by grade level
• Products by category
• Files by extension

Pro Tip: computeIfAbsent

// Old way (verbose):
if (!map.containsKey(key)) {
  map.put(key, new ArrayList<>());
}
map.get(key).add(item);

// New way (elegant):
map.computeIfAbsent(key,
  k -> new ArrayList<>()).add(item);

7. Subarray Sum Equals K 🧮

The Problem

Find how many subarrays (continuous chunks) add up to a target sum K.

Story Time: You have a row of piggy banks with different coins. How many ways can you pick a continuous group that totals exactly $10?

The Insight: Prefix Sums + HashMap

Instead of checking every possible subarray (slow!), we use prefix sums.

Key Idea: If prefixSum[j] - prefixSum[i] = K, then the subarray from i+1 to j sums to K!

graph TD
    A["Array: 1,2,3"] --> B["Prefix: 0,1,3,6"]
    B --> C["If prefix j minus prefix i equals K"]
    C --> D["Subarray i+1 to j equals K"]

The Code

int subarraySum(int[] nums, int k) {
  HashMap<Integer, Integer> prefixCount =
    new HashMap<>();
  prefixCount.put(0, 1);

  int sum = 0, count = 0;

  for (int num : nums) {
    sum += num;
    int need = sum - k;
    count += prefixCount
      .getOrDefault(need, 0);
    prefixCount.put(sum,
      prefixCount.getOrDefault(sum, 0) + 1);
  }

  return count;
}

Walk Through Example

Array: [1, 2, 3], K = 3

Answer: 2 subarrays sum to 3: [1,2] and [3]

Quick Reference Table

Your Confidence Boost 💪

You just learned 7 powerful patterns that solve countless real-world problems!

Remember:

• HashMap = Your magic dictionary (key → value)
• HashSet = Your membership checker
• These patterns appear in 70%+ of coding interviews

The secret? Hash tables give you O(1) average time for lookups. That’s like finding your lunchbox instantly in a school of 1000 lockers!

Now go build something amazing! 🚀