HashMap & HashSet

The last lesson ended with Red-Black trees giving O(log n) lookups no matter the insertion order. Hashing does better still for pure key lookups — O(1) on average — by giving up ordering entirely. This lesson covers how hashing works, what's actually going on inside Java's HashMap, and a classic interview problem (two-sum) that hashing solves far better than brute force.

The Hashing Concept

A hash function takes a key and converts it into an integer (the hash code), which is then reduced to an index within a fixed-size internal array — commonly via index = hash(key) % arraySize. That index is called a bucket. To look up a key, you don't scan anything — you compute its hash, jump straight to that bucket, and (ideally) find your value right there.

key "apple"  -> hashCode() -> 93029210 -> % 16 buckets -> bucket 10
key "banana" -> hashCode() -> 93020956 -> % 16 buckets -> bucket  4
key "cherry" -> hashCode() -> 93006589 -> % 16 buckets -> bucket 13

In Java, every object has a hashCode() method, and HashMap further "spreads" that hash to reduce clustering before taking the modulo. This is why any key type you put in a HashMap must have a correct, consistent hashCode() — and an equals() that agrees with it.

Java's HashMap Internals

A HashMap is backed by an array of buckets (default capacity 16, doubling as it fills up past a load factor of 0.75). When two different keys hash to the same bucket — a collision — Java has to store both in that one slot:

• Historically, each bucket held a simple linked list of entries; a collision just appended to that list.
• Since Java 8, if a single bucket's list grows past 8 entries (and the table is large enough), that bucket is converted — "treeified" — into a small red-black tree instead, so worst-case lookup within a badly-collided bucket drops from O(n) to O(log n).

bucket 4:  [ "banana" -> 3 ] -> [ "grape" -> 7 ]   (collision chain, linked list)
bucket 10: [ "apple"  -> 5 ]                        (no collision)
bucket 13: [ "cherry" -> 9 ]                        (no collision)

Map<String, Integer> prices = new HashMap<>();
prices.put("apple", 5);
prices.put("banana", 3);
prices.put("grape", 7);   // might collide into banana's bucket

// get() computes the hash, jumps to the bucket, then scans
// just that bucket's (usually short) chain for a matching key.
System.out.println(prices.get("grape"));  // 7

Time complexity: O(1) average for get/put — a good hash spreads keys evenly so each bucket holds very few entries. Worst case is O(n) if every key collides into the same bucket (or O(log n) once Java 8 treeifies a large bucket) — but with a well-distributed hash function this is rare. Space complexity: O(n) to store n entries plus the bucket array.

HashSet: A HashMap in Disguise

HashSet<E> is literally implemented as a HashMap<E, Object> internally — every element you add becomes a key, mapped to a single shared dummy placeholder value. That's why a HashSet gives you the exact same O(1)-average add/contains/remove behavior as a HashMap's key operations, just without a value to retrieve.

Set<String> seen = new HashSet<>();
seen.add("apple");
seen.add("banana");

System.out.println(seen.contains("apple"));  // true — one hash lookup, no scanning
System.out.println(seen.contains("cherry")); // false

Time complexity: O(1) average for add/contains/remove — same reasoning as HashMap, since a HashSet's contains() is just a HashMap get() under the hood. Space complexity: O(n) for n stored elements.

Worked Problem: Two-Sum

Given an array of integers and a target, find the indices of two numbers that add up to the target. The brute-force approach checks every pair:

// Brute force: check every pair
int[] twoSumBrute(int[] nums, int target) {
    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};
            }
        }
    }
    throw new IllegalArgumentException("No solution");
}

Time complexity: O(n²) — every element is compared against every other element. Space complexity: O(1) — no extra data structure beyond the result array.

A HashMap gets this down to a single pass. For each number, first check if its complement (target - num) was already seen; if not, record the current number and its index for future lookups:

// One pass with a HashMap: value -> index
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seenAt = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seenAt.containsKey(complement)) {
            return new int[]{seenAt.get(complement), i};
        }
        seenAt.put(nums[i], i);  // remember this value for later lookups
    }
    throw new IllegalArgumentException("No solution");
}

// nums = [2, 7, 11, 15], target = 9
// i=0: complement=7, not seen yet -> remember 2 at index 0
// i=1: complement=2, seen at index 0 -> return [0, 1]

Time complexity: O(n) — a single pass through the array, with each HashMap containsKey/get/put being O(1) average. Space complexity: O(n) — in the worst case (solution found at the last element) the map holds almost every value seen so far.