Hash Maps & Sets

The idea: compute where things live

Arrays gave us O(1) access, but only by numeric index. Nums[42] is instant because the index is the location. A hash map extends that superpower to any key: strings, objects, anything. The trick is a hash function, a formula that converts a key into a number. Feed it "alice" and it might produce 2,347,988; take that number modulo the size of an internal array, and you get a slot index, say 4. So "alice" lives in slot 4.

That is the whole secret: instead of searching for where a key is stored, the map computes where it must be stored. Storing a key means hashing it and dropping the value in the resulting slot; looking it up means hashing it again and going straight there. Both are O(1) on average. The mental model is a wall of labeled filing cabinets where the label is derived from the name itself. You never wander the room looking, you compute the cabinet number and walk directly to it.

HashMap in Java: keys mapped to values

A HashMap<K, V> stores key-value pairs: each unique key maps to exactly one value. put(key, value) inserts or overwrites, get(key) retrieves (returning null if absent), containsKey checks membership, and remove deletes, all O(1) on average. Keys must be object types, so you write HashMap<String, Integer> rather than int; Java auto-converts between int and Integer for you.

The single most common interview pattern is frequency counting: walk a collection once and tally occurrences per key. The method getOrDefault(key, 0) makes this clean. It returns the current count, or 0 if the key has not been seen yet. One pass, O(n) time, and you have a complete census of the data. Anagram checks, majority-element problems, and "first unique character" all fall to this pattern.

String s = "mississippi";
Map<Character, Integer> freq = new HashMap<>();

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

System.out.println(freq.get('s'));
System.out.println(freq.containsKey('z'));

HashSet: membership without values

Sometimes you do not need a value attached to each key. You only need to remember which items you have seen. That is a HashSet: a collection of unique elements with O(1) add, contains, and remove. It is literally a hash map that keeps only the keys. Adding an element that is already present does nothing, which makes sets a natural duplicate detector.

Consider the classic: does this array contain a duplicate? The nested-loop answer compares every pair, O(n squared). With a set, you scan once, if the current element is already in the set, you found a duplicate; otherwise add it and move on. O(n) time, O(n) space: the textbook example of trading memory for speed that Big-O prepared you for.

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (seen.contains(x)) {
            return true;
        }
        seen.add(x);
    }
    return false;
}

Collisions, and why O(1) is "on average"

One question should be nagging you: what if two different keys hash to the same slot? This is called a collision, and it is unavoidable. Infinitely many possible keys are being squeezed into finitely many slots. Java handles it by letting each slot hold a small bucket of entries; on lookup, it hashes to the slot, then checks the few entries there using equals to find the exact key. If too many entries pile up in one bucket, Java reorganizes it, and when the whole table gets crowded it resizes to roughly double and re-distributes everything.

With a decent hash function, entries spread evenly, buckets stay tiny, and operations remain O(1) on average. The honest phrasing interviewers expect. Two practical footnotes: a HashMap keeps no particular order, so never rely on iteration order; and custom key classes must implement hashCode and equals consistently, though built-ins like String and Integer already do.

You now hold the two workhorses of interview prep: arrays for ordered, indexed data and hash maps for instant lookup by key. Next come the structures that impose discipline on order itself (stacks, queues, and linked lists) and the techniques that combine all of them.

Frequently asked