Hashing & HashMaps

1. Introduction: The Ultimate Shortcut

Imagine you are a librarian in a massive library with millions of books. A student asks for "The Great Gatsby". If the books are unsorted, you have to look at every single book ($O(N)$). If they are sorted alphabetically, you can use Binary Search ($O(\log N)$).

But what if you had a magic formula? You plug the title "The Great Gatsby" into the formula, and it instantly spits out: "Aisle 4, Shelf B, Position 12". You walk straight there and grab the book. Time taken: $O(1)$.

This is Hashing. It is the process of converting a key (like a String or Object) into an array index using a Hash Function. The data structure that implements this is the HashMap (or Dictionary/Hash Table). It is arguably the most important data structure in software engineering, heavily tested in almost every FAANG interview because of its $O(1)$ lookup capability.

2. Core Concept: Under the Hood of a HashMap

A HashMap is essentially just a standard Array under the hood. When you write map.put("Apple", 5), three things happen:

1. The Hash Function: Java calls "Apple".hashCode(). This scrambles the characters into a massive integer (e.g., 63315352).
2. The Compression Function (Modulo): The array inside the HashMap is small (default size is usually 16). So we take 63315352 % 16 to get an index between 0 and 15. (Let's say it evaluates to 4).
3. Storage: The Key-Value pair ("Apple", 5) is stored in the array at index 4.

Hash Collisions

What happens if we hash "Banana" and it ALSO evaluates to index 4? This is a Collision. There are two primary ways to resolve collisions:

1. Separate Chaining (Used in Java): The array doesn't hold the elements directly; it holds a pointer to a Linked List. Both "Apple" and "Banana" are stored in the Linked List at index 4. When searching, we go to index 4 and traverse the list to find the correct key.
2. Open Addressing (Linear Probing): If index 4 is full, simply look at index 5. If 5 is full, look at 6. Store it in the first empty slot.

3. Beginner Code Example: Using Java's HashMap

While implementing a HashMap from scratch is a common system design question, 99% of algorithmic problems simply require you to use the built-in java.util.HashMap.

Problem Statement: (LeetCode 1) Two Sum. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

The Insight: Instead of nested loops ($O(N^2)$), we can iterate the array once. At each number, we calculate the complement = target - current. We check if the complement is in our HashMap. If it is, we found the pair! If not, we store the current number in the map.

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        // Map stores: <Number, Index>
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            int complement = target - current;
            
            // O(1) Lookup!
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            
            // O(1) Insertion!
            map.put(current, i);
        }
        
        return new int[]{}; // No pair found
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ average time.
• Space Complexity: $O(N)$ to store the HashMap.

4. Intermediate Code Example: Frequency Maps

The most common use of HashMaps in interviews is counting the frequencies of elements. Java provides a fantastic helper method called getOrDefault().

Problem Statement: (LeetCode 387) First Unique Character in a String. Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

import java.util.HashMap;
import java.util.Map;

public class FirstUnique {
    public static int firstUniqChar(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        
        // Pass 1: Build the Frequency Map
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If the character is not in the map, default to 0, then add 1.
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        
        // Pass 2: Find the first character with a count of 1
        for (int i = 0; i < s.length(); i++) {
            if (counts.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

5. Advanced Code Example: The Array as a HashMap (Direct Hashing)

The Insight: If the keys in your problem are strictly lowercase English letters ('a' to 'z'), do not use a HashMap! A HashMap requires creating Integer objects (autoboxing) and computing hash codes, which has a massive constant-time overhead. Instead, use an int[26] array! The character itself IS the hash! char - 'a' perfectly maps 'a' to 0 and 'z' to 25.

Optimization of First Unique Character:

public class FirstUniqueOptimized {
    public static int firstUniqChar(String s) {
        // Direct Hash Table! 
        int[] counts = new int[26];
        
        // Pass 1: Count frequencies
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts[c - 'a']++; // O(1) native array access
        }
        
        // Pass 2: Find unique
        for (int i = 0; i < s.length(); i++) {
            if (counts[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Why this matters: In an interview, writing this shows the interviewer that you understand how hashing fundamentally works and that you care about memory optimization (this drops memory usage from dynamically allocated objects to 26 bytes of raw memory).

6. Common Mistakes Beginners Make

1. Using .equals() vs == for Keys

   • The Mistake: Relying on == when comparing keys retrieved from a Map.
   • Why it's wrong: == checks memory addresses. map.get("A") == map.get("B") might return false even if both values are 1000, because they are different Integer objects in memory.
   • The Fix: The .equals() method is strictly enforced for HashMap key comparison.

2. Using Mutable Objects as Keys

   • The Mistake: Using a List or a custom User object as a key in a HashMap, and then changing its properties later.
   • Why it's wrong: The object's hashCode() depends on its properties. If you change a property, the hash code changes. If you try to get() the object from the map, the map will look in the new hash bucket, find nothing, and return null, effectively losing your data! Keys must be immutable (like String or Integer).

3. Assuming HashMap Iteration is Ordered

   • The Mistake: Using a for loop over map.keySet() and assuming the items will come out in the order you inserted them, or in sorted order.
   • Why it's wrong: Standard HashMaps are completely chaotic due to the modulo compression logic. If you need insertion order, use LinkedHashMap. If you need sorted order, use TreeMap (which is backed by a Red-Black Tree, making operations $O(\log N)$).

7. Interview Q&A

Q1: What is the "Load Factor" in a HashMap? Answer: The Load Factor determines when the HashMap needs to resize its internal array. In Java, the default is 0.75. This means when the array is 75% full, the HashMap will allocate a brand new array twice the size, and "rehash" every single element into the new array. This prevents heavy collisions but takes an occasional $O(N)$ hit.

Q2: What is the worst-case time complexity of a HashMap? Answer: The worst-case is $O(N)$. If you have a terrible hash function that hashes every single key to the exact same bucket (e.g., return 1;), all $N$ elements form a single Linked List. Searching that bucket takes $O(N)$ time. (Note: Java 8 mitigates this by turning the Linked List into a BST if it gets too long, dropping worst-case to $O(\log N)$).

Q3: Can a HashMap have a null key? Answer: In Java, HashMap allows exactly one null key (it artificially maps it to bucket 0). However, a HashTable or ConcurrentHashMap throws a NullPointerException if you try to insert null, because nulls break concurrency checks.

8. Practice Problems

1. Two Sum (LeetCode 1)
   • Goal: Master the 1-pass complement lookup.
2. Valid Anagram (LeetCode 242)
   • Hint: Use the int[26] frequency array optimization.
3. Group Anagrams (LeetCode 49)
   • Hint: You need to store a List of Strings in the Map. What should the Key be? (The sorted version of the string!).

9. Summary

• The Tradeoff: Hashing sacrifices Space ($O(N)$) to achieve blazing fast Time ($O(1)$).
• The Core Operations: put(), get(), containsKey(), and getOrDefault().
• Direct Hashing: For strings of small, fixed alphabets, completely bypass the HashMap class and use an integer array (like int[26]) for massive speedups.
• Collisions: Realize that HashMaps handle collisions silently via Linked Lists (Separate Chaining), but heavy collisions degrade performance to $O(N)$.