Hashing

From searching to instant lookup

In Arrays and Strings, you learned single-pass thinking. In Sorting and Searching, you saw how order can make search faster. In Graph Algorithms, you used maps and sets behind the scenes to track distances, visited nodes, and adjacency lists.

Now we make that tool explicit: hashing.

Hashing is the idea behind Java's HashMap and HashSet. In interviews, it often turns a slow nested-loop solution into a clean linear-time solution.

By the end, you should recognize problems that ask:

• “Have I seen this before?”
• “How many times did this occur?”
• “Can I quickly map one value to another?”
• “Can I detect duplicates, pairs, or groups?”

The core mental model

A hash table stores data in an array-like structure called buckets.

When you insert a key:

1. Java calls the key's hashCode().
2. The hash code is converted into a bucket index.
3. The key-value pair is stored in that bucket.

key: "cat"
hashCode() -> 98262
bucket index -> 2

Buckets:
0: []
1: []
2: [("cat", 5)]
3: []
4: []

The magic is that lookup does not scan every item. It jumps directly toward the likely bucket.

That is why HashMap operations are average O(1) for insert, lookup, and delete.

Two interview workhorses

In Java, you will mainly use:

• HashMap<K, V> when you need a key → value relationship
• HashSet<T> when you only need to know whether something exists

Common operations:

Operation HashMap HashSet Add put(key, value) add(value) Check containsKey(key) contains(value) Get get(key) — Remove remove(key) remove(value)

Use HashSet for membership. Use HashMap when each key needs extra information.

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        HashSet<String> seen = new HashSet<>();
        seen.add("apple");
        seen.add("banana");
        seen.add("apple"); // duplicate ignored

        HashMap<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 88);
        scores.put("Alice", 97); // updates existing key

        System.out.println("Seen fruits: " + seen);
        System.out.println("Contains banana? " + seen.contains("banana"));
        System.out.println("Alice score: " + scores.get("Alice"));
        System.out.println("Has Charlie? " + scores.containsKey("Charlie"));
    }
}
```

For a well-distributed Java HashMap, what is the average time complexity of put, get, and remove?

What if two keys land together?

A collision happens when different keys map to the same bucket.

"cat" -> bucket 2
"dog" -> bucket 2

Java handles collisions internally. Modern Java HashMap stores collided entries in a bucket structure that can become more efficient when many entries pile up.

The key interview idea:

• Hashing is average fast, not magic.
• Performance depends on good hash distribution.
• More elements relative to buckets increases collision pressure.

That ratio is called the load factor.

load factor = number of entries / number of buckets

You usually do not tune this in beginner interview problems, but you should know why worst-case behavior exists.

Pattern: count what you see

One of the most common hashing patterns is frequency counting.

Instead of repeatedly scanning an array to count occurrences, keep a HashMap from item to count.

This fits problems like:

• first non-repeating character
• majority element variants
• anagram checks
• duplicate detection
• counting pairs with a condition

The habit is simple:

for each item:
    count[item] = count[item] + 1

In Java, getOrDefault keeps this clean.

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String word = "banana";
        HashMap<Character, Integer> freq = new HashMap<>();

        for (char c : word.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        System.out.println("Frequencies: " + freq);
        System.out.println("Count of 'a': " + freq.get('a'));
        System.out.println("Count of 'z': " + freq.getOrDefault('z', 0));
    }
}
```

HashMap keeps keys in sorted order, so iterating over a HashMap always visits keys from smallest to largest.

Pattern: remember complements

A classic hashing interview problem is Two Sum:

Given an array and a target, return indices of two numbers that add to the target.

The brute force approach checks every pair: O(n²).

Hashing makes it one pass:

For each number x, ask:

Have I already seen target - x?

If yes, you found the pair. If no, store x with its index.

This combines ideas you already practiced:

• arrays from Arrays and Strings
• search trade-offs from Sorting and Searching
• single-pass thinking from earlier lessons

```java
import java.util.*;

public class Main {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> indexByValue = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];

            if (indexByValue.containsKey(need)) {
                return new int[] { indexByValue.get(need), i };
            }

            indexByValue.put(nums[i], i);
        }

        return new int[] { -1, -1 };
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);

        System.out.println("Indices: " + Arrays.toString(result));
        System.out.println("Values: " + nums[result[0]] + " + " + nums[result[1]]);
    }
}
```

Fill in the blank: The average time complexity of checking whether a key exists in a well-distributed HashMap is ____.

Your interview checklist

When a problem involves repeated lookup, duplicates, counts, or relationships, pause and ask: Can hashing remove a loop?

Use this guide:

Problem clue Tool “Have I seen this value?” HashSet “How many times?” HashMap<T, Integer> “Map this thing to that thing” HashMap<K, V> “Find pair/complement” HashMap or HashSet “Group equivalent items” HashMap<Key, List<Value>>

Important cautions:

• HashMap does not preserve sorted order.
• Average O(1) is not the same as guaranteed O(1).
• For custom Java objects as keys, correct equals() and hashCode() matter.
• Hashing often trades extra memory for faster time.

That last point is classic DSA thinking: same as earlier lessons, you are choosing the right trade-off for the problem.

Next, you will be ready to see how more specialized structures build on these same trade-off ideas.