Hash Tables

🎯 Explain Like I'm 5...

Imagine you have a big wall of lockers at school! Each locker has a special number on it, and you can put your stuff inside.

🔐 Hash Tables - Magic Lockers:

• You want to store your lunchbox with the key 'lunch' 🍱
• The magic lock (hash function) turns 'lunch' into locker number 42
• Your lunchbox goes in locker 42!
• Later, you say 'lunch' and instantly find locker 42! ⚡

✨ The Magic Lock (Hash Function):

The hash function is like a magical calculator that turns any word into a locker number! It always gives you the same number for the same word.

• 'apple' → Always becomes locker 7
• 'banana' → Always becomes locker 23
• Same key = Same locker number, every time!

🚀 Why Are Hash Tables Super Useful?

• Finding things is SUPER fast - O(1) on average!
• Perfect for storing key-value pairs (like a dictionary!)
• Great for counting things and finding duplicates!
• Used everywhere: databases, caches, password storage!

🔧 Basic Operations

HashMap Operations (Key-Value Pairs)

HashMapBasics.java

java

import java.util.HashMap;
public class HashMapBasics {
    public static void main(String[] args) {
        // Creating a HashMap - like creating lockers!
        HashMap<String, Integer> ages = new HashMap<>();
        // put() - Add key-value pairs (O(1) average time)
        ages.put("Alice", 25);      // Store Alice's age in a locker
        ages.put("Bob", 30);        // Store Bob's age
        ages.put("Charlie", 28);    // Store Charlie's age
        System.out.println("Ages map: " + ages);
        // Output: {Alice=25, Bob=30, Charlie=33}
        // get() - Retrieve value by key (O(1) average time)
        int aliceAge = ages.get("Alice");
        System.out.println("Alice's age: " + aliceAge);  // 25
        // containsKey() - Check if key exists (O(1) average time)
        if (ages.containsKey("Bob")) {
            System.out.println("Bob is in the map!");
        }
        // containsValue() - Check if value exists (O(n) time)
        if (ages.containsValue(30)) {
            System.out.println("Someone is 30 years old!");
        }
        // remove() - Remove a key-value pair (O(1) average time)
        ages.remove("Charlie");
        System.out.println("After removing Charlie: " + ages);
        // size() - Get number of entries
        System.out.println("Size: " + ages.size());  // 2
        // Update existing key
        ages.put("Alice", 26);  // Alice had a birthday!
        System.out.println("Alice's new age: " + ages.get("Alice"));  // 26
        // getOrDefault() - Safe retrieval with default value
        int davidAge = ages.getOrDefault("David", 0);
        System.out.println("David's age: " + davidAge);  // 0 (not found)
        // Loop through all entries
        System.out.println("\nAll entries:");
        for (String name : ages.keySet()) {
            System.out.println(name + " is " + ages.get(name) + " years old");
        }
        // Better way to loop with entries
        System.out.println("\nUsing entrySet:");
        for (var entry : ages.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

HashSet Operations (Unique Values Only)

HashSetBasics.java

java

import java.util.HashSet;
public class HashSetBasics {
    public static void main(String[] args) {
        // HashSet stores unique values only - no duplicates!
        HashSet<String> fruits = new HashSet<>();
        // add() - Add elements (O(1) average time)
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");
        fruits.add("apple");   // Duplicate! Won't be added
        System.out.println("Fruits: " + fruits);
        // Output: [apple, banana, orange] - only unique values!
        // contains() - Check if element exists (O(1) average time)
        if (fruits.contains("apple")) {
            System.out.println("We have apples!");
        }
        // remove() - Remove element (O(1) average time)
        fruits.remove("banana");
        System.out.println("After removing banana: " + fruits);
        // size() - Get number of elements
        System.out.println("Size: " + fruits.size());  // 2
        // Loop through elements
        System.out.println("\nAll fruits:");
        for (String fruit : fruits) {
            System.out.println("- " + fruit);
        }
        // isEmpty() - Check if set is empty
        System.out.println("Is empty? " + fruits.isEmpty());  // false
        // clear() - Remove all elements
        fruits.clear();
        System.out.println("After clear, size: " + fruits.size());  // 0
        // Practical example: Remove duplicates from array
        int[] numbers = {1, 2, 3, 2, 4, 1, 5, 3};
        HashSet<Integer> uniqueNumbers = new HashSet<>();
        for (int num : numbers) {
            uniqueNumbers.add(num);
        }
        System.out.println("\nOriginal array has duplicates");
        System.out.println("Unique numbers: " + uniqueNumbers);
        // Output: [1, 2, 3, 4, 5]
    }
}

💥 Collisions - When Two Keys Want Same Locker

Sometimes two different keys might get the same locker number! Hash tables handle this with 'chaining' - putting multiple items in the same locker using a list.

CollisionExample.java

java

import java.util.HashMap;
public class CollisionExample {
    public static void main(String[] args) {
        // Behind the scenes: HashMap uses chaining for collisions
        // If two keys hash to the same bucket, they're stored in a linked list
        HashMap<String, String> map = new HashMap<>();
        // These might hash to the same bucket (hypothetically)
        // But HashMap handles it automatically!
        map.put("cat", "meow");
        map.put("dog", "woof");
        map.put("cow", "moo");
        // Java's HashMap automatically:
        // 1. Calculates hash code for each key
        // 2. Converts hash code to bucket index
        // 3. If bucket is empty, stores key-value pair
        // 4. If bucket has collision, chains them using linked list
        // 5. When retrieving, uses equals() to find correct entry
        // All operations still O(1) average time!
        System.out.println("Cat says: " + map.get("cat"));  // meow
        System.out.println("Dog says: " + map.get("dog"));  // woof
        // Load Factor: When map is 75% full (default), it resizes
        // This keeps operations fast by reducing collisions
        System.out.println("\nHashMap handles collisions automatically!");
        System.out.println("You don't need to worry about it in interviews!");
        System.out.println("Just know: collisions exist, but O(1) average still holds");
    }
}

💡 Common Problems & Solutions

Problem 1: Two Sum (Hash Table Solution)

Find two numbers that add up to a target - using a hash table makes it O(n) instead of O(n²)!

💡 How it works (Hash Table Lookup Technique):

The Challenge: Find two numbers that add up to target - brute force is O(n²)

The Solution (Use HashMap for O(1) Lookup):

1. Create a HashMap to store numbers we've seen

2. For each number in array:

• Calculate complement = target - current number

• Check if complement exists in map (O(1) lookup!)

• If yes: return indices

• If no: store current number and index in map

Visual Example:

Array: [2, 7, 11, 15], Target: 9

Step 1: i=0, num=2
complement = 9 - 2 = 7
7 not in map yet
Add to map: {2: 0}

Step 2: i=1, num=7
complement = 9 - 7 = 2
2 IS in map! (at index 0)
Found: indices [0, 1] → 2 + 7 = 9 ✓

Why this is O(n) not O(n²):
• Brute force: Check every pair (nested loops)
• HashMap: Check complement in O(1) time!

⏱️ Time Complexity: O(n) - single pass through array

💾 Space Complexity: O(n) - storing numbers in map

TwoSumHash.java

java

import java.util.HashMap;
import java.util.Arrays;
public class TwoSumHash {
    /**
     * Find two numbers that add up to target using HashMap
     * Time Complexity: O(n) - single pass through array
     * Space Complexity: O(n) - storing numbers in map
     *
     * This is MUCH better than brute force O(n²) solution!
     */
    public static int[] twoSum(int[] nums, int target) {
        // HashMap to store: number -> index
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // Check if complement exists in map (O(1) lookup!)
            if (map.containsKey(complement)) {
                // Found it! Return both indices
                return new int[]{map.get(complement), i};
            }
            // Store current number and its index for future lookups
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};  // Not found
    }
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println("Input: " + Arrays.toString(numbers));
        System.out.println("Target: " + target);
        System.out.println("Indices: " + Arrays.toString(result));
        System.out.println("Numbers: " + numbers[result[0]] + " + " +
                         numbers[result[1]] + " = " + target);
        // Output: 2 + 7 = 9
        // Test with another example
        int[] nums2 = {3, 2, 4};
        int[] result2 = twoSum(nums2, 6);
        System.out.println("\nAnother test: " + Arrays.toString(result2));
        // Output: [1, 2] (indices of 2 and 4)
    }
}

Problem 2: First Non-Repeating Character

Find the first character that appears only once in a string. Use a hash map to count frequencies!

💡 How it works (Two-Pass Frequency Count):

The Challenge: Find the first character that appears only once in the string

The Solution (Count then Find):

1. First pass: Count frequency of each character

→ Use HashMap<Character, Integer> to store counts

2. Second pass: Iterate through string again

→ Return first character with count = 1

Key Point: LinkedHashMap maintains insertion order for predictable iteration

Visual Example:

String: "leetcode"

Pass 1: Count frequencies
l: 1
e: 3
t: 1
c: 1
o: 1
d: 1

Pass 2: Find first with count=1
Check 'l' → count=1 ✓ Return 'l'!

Another example: "loveleetcode"
l: 2, o: 2, v: 1, e: 4, t: 1, c: 1, d: 1
First with count=1 → 'v' ✓

⏱️ Time Complexity: O(n) - two passes through string

💾 Space Complexity: O(k) - k unique characters

FirstNonRepeating.java

java

import java.util.HashMap;
import java.util.LinkedHashMap;
public class FirstNonRepeating {
    /**
     * Find first non-repeating character in string
     * Time Complexity: O(n) - two passes through string
     * Space Complexity: O(k) - where k is number of unique characters
     */
    public static char firstNonRepeating(String str) {
        // LinkedHashMap maintains insertion order!
        LinkedHashMap<Character, Integer> charCount = new LinkedHashMap<>();
        // First pass: Count frequency of each character
        for (char c : str.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        // Second pass: Find first character with count = 1
        for (char c : str.toCharArray()) {
            if (charCount.get(c) == 1) {
                return c;  // Found it!
            }
        }
        return '_';  // No non-repeating character found
    }
    /**
     * Alternative: Two pass solution with regular HashMap
     */
    public static char firstNonRepeatingV2(String str) {
        HashMap<Character, Integer> freq = new HashMap<>();
        // Count frequencies
        for (char c : str.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        // Find first with frequency 1
        for (char c : str.toCharArray()) {
            if (freq.get(c) == 1) {
                return c;
            }
        }
        return '_';
    }
    public static void main(String[] args) {
        String test1 = "leetcode";
        System.out.println("String: " + test1);
        System.out.println("First non-repeating: " + firstNonRepeating(test1));
        // Output: 'l'
        String test2 = "loveleetcode";
        System.out.println("\nString: " + test2);
        System.out.println("First non-repeating: " + firstNonRepeating(test2));
        // Output: 'v'
        String test3 = "aabb";
        System.out.println("\nString: " + test3);
        System.out.println("First non-repeating: " + firstNonRepeating(test3));
        // Output: '_' (none found)
    }
}

Problem 3: Group Anagrams

Group words that are anagrams (same letters, different order). Hash tables make this easy!

💡 How it works (Sorted Key Grouping):

The Challenge: Group words that are anagrams (same letters, different order)

The Solution (Sort and Group):

1. For each word:

• • Sort the characters (anagrams become identical when sorted)

• • Use sorted string as HashMap key

2. Add word to the list at that key

3. All anagrams end up in same list!

Alternative (Better): Use character count array as key - O(n*k) instead of O(n*k log k)

Visual Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

Process each word:
"eat" → sort → "aet" → map["aet"] = ["eat"]
"tea" → sort → "aet" → map["aet"] = ["eat", "tea"]
"tan" → sort → "ant" → map["ant"] = ["tan"]
"ate" → sort → "aet" → map["aet"] = ["eat", "tea", "ate"]
"nat" → sort → "ant" → map["ant"] = ["tan", "nat"]
"bat" → sort → "abt" → map["abt"] = ["bat"]

Result: HashMap groups:
"aet" → ["eat", "tea", "ate"]
"ant" → ["tan", "nat"]
"abt" → ["bat"]

Key insight: Anagrams have identical sorted form!

⏱️ Time Complexity: O(n * k log k) with sorting, O(n * k) with counting

💾 Space Complexity: O(n * k) - storing all strings

GroupAnagrams.java

java

import java.util.*;
public class GroupAnagrams {
    /**
     * Group anagrams together using HashMap
     * Time Complexity: O(n * k log k) - n strings, k avg length, sorting each
     * Space Complexity: O(n * k) - storing all strings
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        // Map: sorted string -> list of anagrams
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // Sort characters to create key
            // Anagrams will have same sorted form!
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            // Add string to its anagram group
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        // Return all groups as list
        return new ArrayList<>(map.values());
    }
    /**
     * Alternative: Use character count as key (faster!)
     * Time Complexity: O(n * k) - no sorting needed
     */
    public static List<List<String>> groupAnagramsOptimized(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // Count each character (a-z)
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            // Convert count array to string as key
            // Example: "aab" -> "2,1,0,0,...,0"
            String key = Arrays.toString(count);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("Input: " + Arrays.toString(words));
        List<List<String>> groups = groupAnagrams(words);
        System.out.println("\nGrouped anagrams:");
        for (List<String> group : groups) {
            System.out.println(group);
        }
        // Output:
        // [eat, tea, ate]  - all anagrams of each other
        // [tan, nat]       - anagrams
        // [bat]            - no anagrams
    }
}

Problem 4: Frequency Counter

Count how many times each element appears. Hash maps are perfect for this!

💡 How it works (HashMap Counter Pattern):

The Challenge: Count how many times each element appears in the array

The Solution (HashMap Counting):

1. Create HashMap<Element, Count>

2. For each element:

→ map.put(element, map.getOrDefault(element, 0) + 1)

3. Result: HashMap with all frequencies!

Common Applications:

• Find most frequent element

• Find majority element (appears > n/2 times)

• Check if two arrays have same frequencies

Visual Example:

Array: [1, 2, 3, 2, 4, 2, 5, 2, 6]

Build frequency map:
Process 1: map = {1: 1}
Process 2: map = {1: 1, 2: 1}
Process 3: map = {1: 1, 2: 1, 3: 1}
Process 2: map = {1: 1, 2: 2, 3: 1}
Process 4: map = {1: 1, 2: 2, 3: 1, 4: 1}
Process 2: map = {1: 1, 2: 3, 3: 1, 4: 1}
Process 5: map = {1: 1, 2: 3, 3: 1, 4: 1, 5: 1}
Process 2: map = {1: 1, 2: 4, 3: 1, 4: 1, 5: 1}
Process 6: map = {1: 1, 2: 4, 3: 1, 4: 1, 5: 1, 6: 1}

Final frequency map:
1 → 1 time
2 → 4 times (most frequent!)
3 → 1 time
4 → 1 time
5 → 1 time
6 → 1 time

⏱️ Time Complexity: O(n) - single pass through array

💾 Space Complexity: O(k) - k unique elements

FrequencyCounter.java

java

100

import java.util.*;
public class FrequencyCounter {
    /**
     * Count frequency of each element in array
     * Time Complexity: O(n)
     * Space Complexity: O(k) where k is number of unique elements
     */
    public static HashMap<Integer, Integer> countFrequency(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            // Increment count, or set to 1 if first occurrence
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        return freq;
    }
    /**
     * Find element with highest frequency
     */
    public static int mostFrequent(int[] arr) {
        HashMap<Integer, Integer> freq = countFrequency(arr);
        int maxCount = 0;
        int result = arr[0];
        for (var entry : freq.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                result = entry.getKey();
            }
        }
        return result;
    }
    /**
     * Check if two arrays have same frequency of elements
     * (not necessarily same order)
     */
    public static boolean sameFrequency(int[] arr1, int[] arr2) {
        if (arr1.length != arr2.length) {
            return false;
        }
        HashMap<Integer, Integer> freq1 = countFrequency(arr1);
        HashMap<Integer, Integer> freq2 = countFrequency(arr2);
        return freq1.equals(freq2);
    }
    /**
     * Find all elements that appear more than n/2 times
     * (Majority element problem)
     */
    public static List<Integer> findMajorityElements(int[] arr) {
        HashMap<Integer, Integer> freq = countFrequency(arr);
        List<Integer> result = new ArrayList<>();
        int threshold = arr.length / 2;
        for (var entry : freq.entrySet()) {
            if (entry.getValue() > threshold) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 2, 4, 2, 5, 2, 6};
        System.out.println("Array: " + Arrays.toString(numbers));
        // Count frequencies
        HashMap<Integer, Integer> freq = countFrequency(numbers);
        System.out.println("\nFrequencies:");
        for (var entry : freq.entrySet()) {
            System.out.println(entry.getKey() + " appears " +
                             entry.getValue() + " times");
        }
        // Most frequent
        System.out.println("\nMost frequent: " + mostFrequent(numbers));
        // Output: 2 (appears 4 times)
        // Check same frequency
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {3, 1, 2};
        System.out.println("\nSame frequency? " + sameFrequency(arr1, arr2));
        // Output: true
        // Find majority elements
        int[] arr3 = {2, 2, 2, 3, 3, 4};
        System.out.println("\nMajority elements: " + findMajorityElements(arr3));
        // Output: [2] (appears more than 6/2 = 3 times)
    }
}

🔑 Key Points to Remember

1️⃣Average O(1) lookup time - super fast! (worst case O(n) with many collisions)
2️⃣HashMap stores key-value pairs, HashSet stores unique values only
3️⃣Hash function quality matters - good hash = fewer collisions
4️⃣Keys must be immutable and have proper hashCode() and equals() methods
5️⃣Load factor and capacity affect performance - Java default: 0.75 load factor

💪 Practice Problems

• Contains Duplicate - check if array has duplicates
• Valid Anagram - check if two strings are anagrams
• Intersection of Two Arrays - find common elements
• Longest Substring Without Repeating Characters
• Top K Frequent Elements - find k most frequent numbers
• Isomorphic Strings - check if two strings are isomorphic