Hashing (HashMap & HashSet)

In simple words

A hash table stores key → value pairs and finds any key in O(1) on average. A hash function turns the key into a number, and that number picks a bucket.

HashSet is the same idea with keys only — perfect for "have I seen this before?"

Key ideas

• How Java's HashMap works (a favorite interview question): array of buckets → hashCode() picks a bucket → equals() finds the exact key inside.
• Collisions are chained in a linked list; since Java 8 a bucket with more than 8 entries turns into a red-black tree.
• Load factor 0.75: when 75% full, the table doubles and all entries are rehashed.
• If you override equals, you must override hashCode — otherwise lookups fail.
• Keys should be immutable. A mutated key can land in the wrong bucket and 'disappear'.
• HashMap has no order · LinkedHashMap keeps insertion order · TreeMap keeps sorted order (O(log n)).
• Classic patterns: frequency count, complement lookup (Two Sum), prefix sum + map, grouping by a signature.

Operations & cost

Java code

// Two Sum: find the complement in O(1)
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need), i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

// Group anagrams by a sorted-letters key
List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> map = new HashMap<>();
    for (String w : words) {
        char[] c = w.toCharArray();
        Arrays.sort(c);
        map.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(map.values());
}

// Longest consecutive sequence in O(n)
int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {
        if (set.contains(x - 1)) continue;          // only start at a run's beginning
        int len = 1;
        while (set.contains(x + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

Interview traps to remember

• equals & hashCode: override both. With only equals, set.contains(new P(1)) returns false.
• Mutable keys: changing a key after put() changes its hash, so get(key) returns null. Use immutable keys.
• Missing keys: map.get(missing) is null. Use getOrDefault.
• Integer values: compare with equals. map.get("a") == map.get("b") is false when both hold 1000.
• Subarray Sum Equals K: start the map with put(0, 1), or [1, 2, 3] with k = 3 gives 1 instead of 2.
• Nulls: HashMap allows one null key; TreeMap and ConcurrentHashMap throw NullPointerException.

How Java's HashMap works (checked with Java 21)

• An array of buckets, 16 by default. The bucket is hash & (n - 1), after mixing the bits of hashCode().
• Keys in the same bucket form a small list; equals() finds the exact key.
• A bucket with more than 8 keys becomes a red-black tree, once the table has at least 64 buckets.
• Load factor 0.75: adding the 13th key to 16 buckets doubles the table to 32 and rehashes everything.
• Order: HashMap none · LinkedHashMap insertion order (LRU cache) · TreeMap sorted, O(log n). Use ConcurrentHashMap across threads.

Spot it when

• 'Find a pair / duplicate / count occurrences'.
• You want to turn an O(n²) search into O(n).
• 'Group items that are the same in some way'.

Practice problems

Interview tip

★ For Java roles, be ready to explain HashMap internals (buckets, hashCode/equals, treeification, resize) and why ConcurrentHashMap is used in multi-threaded services.