Hashing — Complete Study Guide

I. Notebook Summary (copy by hand)

Card-sized blocks, hand-copyable and deck-ready. Telegraphic — arrows over sentences.

II. Detailed Study Notes

Concepts first, then problems grouped by the technique they teach. Each opens with a one-line claim; [+] marks my additions. Code cross-links to Section III.

1 · The Principle of a Hash Table foundation

2 · Two Keys to Designing a Hash Table foundation

3 · Hash Set vs Hash Map foundation

4 · Making Bucket Removal O(1) foundation · [+] depth

5 · The Three Reusable Templates framework

6 · Contains Duplicate hash set · Template A

7 · Single Number XOR (beats hashing)

8 · Happy Number hash set · cycle detection

9 · Two Sum hash map (value→index) · Scenario I

10 · Isomorphic Strings map + set (bijection) · Scenario I

11 · First Unique Character frequency map · Scenario II

12 · Group Anagrams design the key · Template C

13 · Longest Substring Without Repeating Characters hash set + sliding window

14 · Top K Frequent Elements frequency map + heap / bucket sort

15 · Insert Delete GetRandom O(1) map + dynamic array · swap-with-last

Prefix-aggregate + hash-map family. The subarray problems — one pattern, two knobs. (These came up in my own practice; they're the natural extension of "aggregate by key" to running sums.)

16 · Longest Subarray with Sum K prefix sum + map (index)

17 · Count Subarrays with Sum K prefix sum + map (frequency)

18 · Count Subarrays with XOR K prefix XOR + map (frequency)

19 · Largest Subarray with Equal 0s and 1s transform → prefix sum

20 · Longest Consecutive Sequence hash set

More practice. Other problems worked through that use the same toolbox — kept here for quick reference.

21 · Common Elements in All Rows of a Matrix hash map (value→row reached)

22 · Symmetric Pairs hash map (first→second)

III. Code Samples (runnable, Java 17)

Self-contained classes with a main. Compile javac File.java, run java File. Standard library only.

PrincipleDemo.java — ↑ notes

public class PrincipleDemo {
    static int hash(int x) { return x % 5; }   // the example hash function y = x % 5

    public static void main(String[] a) {
        int[] keys = {1987, 24, 2};
        for (int k : keys) System.out.println(k + " → bucket " + hash(k));  // 1987 & 2 collide at 2
        System.out.println("search 23 → bucket " + hash(23) + " (scan only there)");
    }
}

1987 → bucket 2
24 → bucket 4
2 → bucket 2
search 23 → bucket 3 (scan only there)

Why: 1987 and 2 share bucket 2 — a collision the table must resolve. Search recomputes the same bucket, so you only scan one bucket, not the whole table.

MyHashSet.java — ↑ notes

import java.util.*;

// Hash set built from scratch: array of buckets, each a list (separate chaining).
public class MyHashSet {
    private final int MAX = 100000;            // number of buckets
    private List<Integer>[] set;

    private int idx(int key) { return key % MAX; }   // hash function

    private int pos(int key, int i) {          // find key within its bucket, -1 if absent
        List<Integer> b = set[i];
        if (b == null) return -1;
        for (int j = 0; j < b.size(); j++) if (b.get(j) == key) return j;
        return -1;
    }

    @SuppressWarnings("unchecked")
    public MyHashSet() { set = new ArrayList[MAX]; }

    public void add(int key) {
        int i = idx(key);
        if (pos(key, i) < 0) {                 // only add if not present (set = no dups)
            if (set[i] == null) set[i] = new ArrayList<>();
            set[i].add(key);
        }
    }

    public void remove(int key) {
        int i = idx(key), p = pos(key, i);
        if (p >= 0) set[i].remove(p);
    }

    public boolean contains(int key) { return pos(key, idx(key)) >= 0; }

    public static void main(String[] a) {
        MyHashSet s = new MyHashSet();
        s.add(1); s.add(100001);                  // 1 and 100001 collide (both % 100000 = 1)
        System.out.println(s.contains(100001));   // true (found by scanning bucket 1)
        s.remove(1);
        System.out.println(s.contains(1));        // false
    }
}

true
false

Why: 1 and 100001 hash to the same bucket; the in-bucket scan distinguishes them. This is separate chaining made explicit.

MyHashMap.java — ↑ notes

import java.util.*;

// Hash map from scratch. NOTE: the original card used javafx.util.Pair; [+]
// replaced with a plain int[]{key,value} so it compiles on a standard JDK.
public class MyHashMap {
    private final int MAX = 100000;
    private List<int[]>[] map;        // each entry: [key, value]

    private int idx(int key) { return key % MAX; }

    private int pos(int key, int i) {
        List<int[]> b = map[i];
        if (b == null) return -1;
        for (int j = 0; j < b.size(); j++) if (b.get(j)[0] == key) return j;
        return -1;
    }

    @SuppressWarnings("unchecked")
    public MyHashMap() { map = new ArrayList[MAX]; }

    public void put(int key, int value) {
        int i = idx(key), p = pos(key, i);
        if (p < 0) {
            if (map[i] == null) map[i] = new ArrayList<>();
            map[i].add(new int[]{key, value});      // new pair
        } else {
            map[i].set(p, new int[]{key, value});   // update existing
        }
    }

    public int get(int key) {
        int i = idx(key), p = pos(key, i);
        return p < 0 ? -1 : map[i].get(p)[1];  // -1 = absent
    }

    public void remove(int key) {
        int i = idx(key), p = pos(key, i);
        if (p >= 0) map[i].remove(p);
    }

    public static void main(String[] a) {
        MyHashMap m = new MyHashMap();
        m.put(1, 10); m.put(1, 20);     // update
        System.out.println(m.get(1));   // 20
        System.out.println(m.get(2));   // -1 (absent)
    }
}

20
-1

Why the change: the reference solution imported javafx.util.Pair, which isn't in a standard modern JDK. Using int[]{key,value} keeps it dependency-free and the logic identical.

HashUsageDemo.java — ↑ notes

import java.util.*;

public class HashUsageDemo {
    public static void main(String[] a) {
        // ---- Hash set: presence / uniqueness ----
        Set<Integer> s = new HashSet<>();
        s.add(3); s.add(2); s.add(1); s.remove(2);
        System.out.println(s.contains(2) + " size=" + s.size());  // false size=2

        // ---- Hash map: key → value ----
        Map<Integer,Integer> m = new HashMap<>();
        m.putIfAbsent(1, 1);   // inserts
        m.put(1, 2);           // overwrites → 2
        System.out.println(m.get(1) + " has2=" + m.containsKey(2));  // 2 has2=false
    }
}

false size=2
2 has2=false

Templates.java — ↑ notes

import java.util.*;

public class Templates {
    // Template A — find duplicates with a hash set.
    static <T> boolean hasDuplicate(List<T> keys) {
        Set<T> seen = new HashSet<>();
        for (T k : keys) if (!seen.add(k)) return true;   // add returns false if already present
        return false;
    }

    // Template B — aggregate by key (here: count occurrences).
    static <T> Map<T,Integer> counts(List<T> keys) {
        Map<T,Integer> m = new HashMap<>();
        for (T k : keys) m.merge(k, 1, Integer::sum);   // update strategy = sum
        return m;
    }

    public static void main(String[] a) {
        System.out.println(hasDuplicate(List.of(1,2,3,2)));  // true
        System.out.println(counts(List.of("a","b","a")));    // {a=2, b=1}
    }
}

true
{a=2, b=1}

ContainsDuplicate.java — ↑ notes

import java.util.*;

public class ContainsDuplicate {
    static boolean has(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) if (!seen.add(x)) return true;   // add fails → duplicate
        return false;
    }

    public static void main(String[] a) {
        System.out.println(has(new int[]{1,2,3,1}));  // true
        System.out.println(has(new int[]{1,2,3}));    // false
    }
}

true
false

SingleNumber.java — ↑ notes

public class SingleNumber {
    static int single(int[] nums) {
        int x = 0;
        for (int n : nums) x ^= n;   // ⭐ pairs cancel (a^a=0); loner survives
        return x;
    }

    public static void main(String[] a) {
        System.out.println(single(new int[]{4,1,2,1,2}));  // 4
    }
}

4

Why O(1) space: XOR is commutative/associative, so order doesn't matter and no storage is needed — strictly better than the hash-set solution.

HappyNumber.java — ↑ notes

import java.util.*;

public class HappyNumber {
    static int next(int n) {
        int s = 0;
        while (n > 0) { int d = n % 10; s += d * d; n /= 10; }   // sum of squared digits
        return s;
    }

    static boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && seen.add(n)) n = next(n);   // stop at 1, or when a state repeats (cycle)
        return n == 1;
    }

    public static void main(String[] a) {
        System.out.println(isHappy(19));  // true
        System.out.println(isHappy(2));   // false (enters a cycle)
    }
}

true
false

TwoSum.java — ↑ notes

import java.util.*;

public class TwoSum {
    static 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 };  // check BEFORE insert
            seen.put(nums[i], i);
        }
        return new int[]{};
    }

    public static void main(String[] a) {
        System.out.println(Arrays.toString(twoSum(new int[]{3,2,4}, 6)));  // [1, 2]
    }
}

[1, 2]

Isomorphic.java — ↑ notes

import java.util.*;

public class Isomorphic {
    static boolean iso(String x, String y) {
        if (x == null || y == null || x.length() != y.length()) return false;
        Map<Character,Character> map = new HashMap<>();   // x → y
        Set<Character> used = new HashSet<>();             // y's already taken
        for (int i = 0; i < x.length(); i++) {
            char cx = x.charAt(i), cy = y.charAt(i);
            if (map.containsKey(cx)) {
                if (map.get(cx) != cy) return false;   // inconsistent
            } else {
                if (used.contains(cy)) return false;   // ⭐ two x's → one y forbidden
                map.put(cx, cy); used.add(cy);
            }
        }
        return true;
    }

    public static void main(String[] a) {
        System.out.println(iso("ACAB", "XCXY"));  // true
        System.out.println(iso("foo",  "bar"));   // false
    }
}

true
false

FirstUnique.java — ↑ notes

public class FirstUnique {
    static int firstUniq(String s) {
        int[] freq = new int[26];                    // aggregate-by-key: count each char
        for (char c : s.toCharArray()) freq[c - 'a']++;
        for (int i = 0; i < s.length(); i++)         // first char with count 1
        if (freq[s.charAt(i) - 'a'] == 1) return i;
        return -1;
    }

    public static void main(String[] a) {
        System.out.println(firstUniq("leetcode"));     // 0
        System.out.println(firstUniq("loveleetcode")); // 2
        System.out.println(firstUniq("aabb"));         // -1
    }
}

0
2
-1

GroupAnagrams.java — ↑ notes

import java.util.*;

public class GroupAnagrams {
    static List<List<String>> group(String[] words) {
        Map<String, List<String>> buckets = new HashMap<>();
        for (String w : words) {
            char[] c = w.toCharArray();
            Arrays.sort(c);                            // ⭐ designed key: sorted letters
            String key = new String(c);                // "eat","ate" → "aet"
            buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(buckets.values());
    }

    public static void main(String[] a) {
        System.out.println(group(new String[]{"eat","tea","tan","ate","nat","bat"}));
    }
}

[[eat, tea, ate], [bat], [tan, nat]]

Why: group order isn't guaranteed (it follows hash iteration), but each group's contents are correct. computeIfAbsent is the idiomatic "create bucket if missing, then add."

LongestSubstr.java — ↑ notes

import java.util.*;

public class LongestSubstr {
    static int lengthOfLongest(String s) {
        Map<Character,Integer> last = new HashMap<>();   // char → last index seen
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c))                     // ⭐ jump left past the prior occurrence
            left = Math.max(left, last.get(c) + 1);
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] a) {
        System.out.println(lengthOfLongest("abcabcbb"));  // 3
        System.out.println(lengthOfLongest("bbbbb"));     // 1
        System.out.println(lengthOfLongest("pwwkew"));    // 3
    }
}

3
1
3

Why max on left: a stale earlier index could be behind the current window — guarding with max prevents the left pointer from moving backwards.

TopKFrequent.java — ↑ notes

import java.util.*;

public class TopKFrequent {
    static int[] topK(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        for (int n : nums) freq.merge(n, 1, Integer::sum);

        // ⭐ bucket sort: bucket[f] = values that occur f times
        List<Integer>[] bucket = new List[nums.length + 1];
        for (var e : freq.entrySet()) {
            int f = e.getValue();
            if (bucket[f] == null) bucket[f] = new ArrayList<>();
            bucket[f].add(e.getKey());
        }

        int[] res = new int[k];
        int idx = 0;
        for (int f = bucket.length - 1; f >= 1 && idx < k; f--)   // high freq → low
        if (bucket[f] != null) for (int v : bucket[f]) if (idx < k) res[idx++] = v;
        return res;
    }

    public static void main(String[] a) {
        System.out.println(Arrays.toString(topK(new int[]{1,1,1,2,2,3}, 2)));  // [1, 2]
    }
}

[1, 2]

Why O(n): frequencies are bounded by n, so indexing by frequency and scanning top-down avoids any sort or heap.

RandomizedSet.java — ↑ notes

import java.util.*;

public class RandomizedSet {
    private List<Integer> list = new ArrayList<>();      // O(1) random access
    private Map<Integer,Integer> idx = new HashMap<>();  // value → its index in list
    private Random rnd = new Random();

    public boolean insert(int v) {
        if (idx.containsKey(v)) return false;
        idx.put(v, list.size()); list.add(v); return true;
    }

    public boolean remove(int v) {
        Integer i = idx.get(v);
        if (i == null) return false;
        int last = list.size() - 1, lastVal = list.get(last);
        list.set(i, lastVal); idx.put(lastVal, i);   // ⭐ swap target with last…
        list.remove(last); idx.remove(v);            // …then pop last → O(1)
        return true;
    }

    public int getRandom() { return list.get(rnd.nextInt(list.size())); }

    public static void main(String[] a) {
        RandomizedSet r = new RandomizedSet();
        System.out.println(r.insert(1));   // true
        System.out.println(r.remove(2));   // false (absent)
        r.insert(2);
        System.out.println(r.remove(1));   // true
        System.out.println(r.getRandom()); // 2 (only element left)
    }
}

true
false
true
2

LongestSubarraySumK.java — ↑ notes

import java.util.*;

public class LongestSubarraySumK {
    static int longest(int[] nums, int k) {
        Map<Integer,Integer> first = new HashMap<>();
        first.put(0, -1);            // ⭐ prefix 0 at index -1
        int sum = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (first.containsKey(sum - k)) best = Math.max(best, i - first.get(sum - k));
            first.putIfAbsent(sum, i);   // ⚠ earliest index only
        }
        return best;
    }

    public static void main(String[] a) {
        System.out.println(longest(new int[]{5,6,-5,5,3,5,3,-2,0}, 8));  // 4
    }
}

4

CountSubarraySumK.java — ↑ notes

import java.util.*;

public class CountSubarraySumK {
    static int count(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        freq.put(0, 1);                // ⭐ empty prefix once; value = FREQUENCY
        int sum = 0, cnt = 0;
        for (int x : nums) {
            sum += x;
            cnt += freq.getOrDefault(sum - k, 0);   // ⚠ read first…
            freq.merge(sum, 1, Integer::sum);       // …then write
        }
        return cnt;
    }

    public static void main(String[] a) {
        System.out.println(count(new int[]{1,2,1,2}, 3));  // 3
        System.out.println(count(new int[]{1,-1,0}, 0));   // 3
    }
}

3
3

CountSubarrayXorK.java — ↑ notes

import java.util.*;

public class CountSubarrayXorK {
    static int count(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        freq.put(0, 1);
        int xr = 0, cnt = 0;
        for (int x : nums) {
            xr ^= x;
            cnt += freq.getOrDefault(xr ^ k, 0);   // ⭐ need earlier prefix = xr ^ k
            freq.merge(xr, 1, Integer::sum);        // ⚠ insert xr, not xr^k
        }
        return cnt;
    }

    public static void main(String[] a) {
        System.out.println(count(new int[]{4,2,2,6,4}, 6));  // 4
    }
}

4

EqualZeroOne.java — ↑ notes

import java.util.*;

public class EqualZeroOne {
    static int maxLen(int[] arr) {
        Map<Integer,Integer> first = new HashMap<>();
        first.put(0, -1);
        int sum = 0, best = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += (arr[i] == 0) ? -1 : 1;   // ⭐ 0 → -1 ⇒ "equal" == "sum 0"
            if (first.containsKey(sum)) best = Math.max(best, i - first.get(sum));
            else first.put(sum, i);
        }
        return best;
    }

    public static void main(String[] a) {
        System.out.println(maxLen(new int[]{1,0,1,1,1,0,0}));  // 6
    }
}

6

LongestConsecutive.java — ↑ notes

import java.util.*;

public class LongestConsecutive {
    static int longest(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)) {       // ⭐ only start at a run's beginning
                int y = x, len = 1;
                while (set.contains(y + 1)) { y++; len++; }
                best = Math.max(best, len);
            }
        }
        return best;
    }

    public static void main(String[] a) {
        System.out.println(longest(new int[]{100,4,200,1,3,2}));  // 4
    }
}

4

CommonInRows.java — ↑ notes

import java.util.*;

public class CommonInRows {
    static void common(int[][] mat) {
        if (mat == null || mat.length == 0) return;
        Map<Integer,Integer> row = new HashMap<>();   // value → highest row reached (1-based)
        for (int i = 0; i < mat.length; i++) for (int j = 0; j < mat[0].length; j++) {
            int v = mat[i][j];
            if (i == 0) row.put(v, 1);
            else if (row.getOrDefault(v, 0) == i) {   // ⚠ reached previous row?
                row.put(v, i + 1);
                if (i == mat.length - 1) System.out.print(v + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] a) {
        int[][] mat = {{2,4,3,8,7},{4,7,1,3,6},{3,5,2,1,3},{4,5,0,2,3}};
        common(mat);  // 3
    }
}

3 

SymmetricPairs.java — ↑ notes

import java.util.*;

public class SymmetricPairs {
    static void find(int[][] arr) {
        Map<Integer,Integer> map = new HashMap<>();   // first → second
        for (int[] p : arr) {
            int first = p[0], second = p[1];
            Integer val = map.get(second);            // ⭐ mirror would have keyed on 'second'
            if (val != null && val == first)          // ⚠ null-guard (Java returns null)
            System.out.println("(" + second + ", " + first + ")");
            else map.put(first, second);
        }
    }

    public static void main(String[] a) {
        find(new int[][]{{11,20},{30,40},{5,10},{40,30},{10,5}});
    }
}

(30, 40)
(5, 10)

IV. Hands-On Lab (practice)

Six graded exercises, Warm-up → Challenge. Predict the output before running, then verify. Solutions collapsed.

Self-check rubric — how to know you've got it

V. More Practice

The rest of the hash-table problem set — name, pattern, the one insight, and a verified link. Drill these to round out coverage.

Hash-table classics

Design the key

Prefix-aggregate extras

★ Patterns Recap

Every detailed problem mapped to technique, the unlocking insight, and complexity.

*Happy Number iterations are bounded by how fast the digit-square-sum shrinks; effectively near-constant for ints.

End of guide · Hashing · Java 17