Hashing: HashMap, HashSet, and Frequency Patterns

Suppose your phone had 5,000 contacts stored in no particular order. To find "Priya" you would scan from the top. Now imagine a phone that, given a name, could calculate exactly which slot the contact lives in, and jump straight there. No scanning.

That is the promise of hashing, and it is probably the single most useful trick for turning slow solutions into fast ones. Many problems that look like they need two nested loops become one loop when you add a hash table. In Start Here you already saw HashSet turn the duplicate check from quadratic into linear. In this article we find out why it works.

• How a hash table works, at the level of ideas.
• What a collision is, and how it is handled.
• How to use HashMap and HashSet in Java.
• The standard patterns: membership, counting, complements, grouping.
• Why equals and hashCode must agree, and the traps with mutable keys.
• What to say about hash table complexity.

A hash table stores data in an array. To decide where a key goes, it applies a hash function that turns the key into a number, and then reduces that number to a valid array index, often with the remainder operator:

index = hash(key) mod arraySize

Each array slot is called a bucket. To look up a key later, compute the same index and look in that bucket. The cost does not depend on how many items are stored, because computing a hash and jumping to an index takes constant time. That is why we say lookups are O(1) on average.

A good hash function spreads keys evenly across the buckets, and gives the same result every time for the same key.

There are far more possible keys than buckets, so sometimes two different keys map to the same bucket. That is a collision, and it is normal and expected. The most common fix is chaining: each bucket holds a small list, and the keys that landed there sit side by side. To look up a key, go to its bucket and scan the (hopefully short) list using equals.

The following toy shows the mechanism with integer keys and 10 buckets. We use Math.floorMod so negative keys still produce a valid index.

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static class ToyHashSet {        private final List<List<Integer>> buckets = new ArrayList<>();        private final int capacity;        ToyHashSet(int capacity) {            this.capacity = capacity;            for (int i = 0; i < capacity; i++) {                buckets.add(new ArrayList<>());            }        }        private int bucketOf(int key) {            return Math.floorMod(key, capacity);       // always in the range 0 to capacity - 1        }        boolean add(int key) {            List<Integer> bucket = buckets.get(bucketOf(key));            if (bucket.contains(key)) {                return false;                          // already present            }            bucket.add(key);            return true;        }        boolean contains(int key) {            return buckets.get(bucketOf(key)).contains(key);        }        void print() {            for (int i = 0; i < capacity; i++) {                if (!buckets.get(i).isEmpty()) {                    System.out.println("bucket " + i + ": " + buckets.get(i));                }            }        }    }    public static void main(String[] args) {        ToyHashSet set = new ToyHashSet(10);        int[] keys = {15, 25, 7, 42, 100, -3, 15};        for (int key : keys) {            System.out.println("add " + key + " -> " + set.add(key));        }        set.print();        System.out.println(set.contains(25) + " " + set.contains(35));    }}

add 15 -> trueadd 25 -> trueadd 7 -> trueadd 42 -> trueadd 100 -> trueadd -3 -> trueadd 15 -> falsebucket 0: [100]bucket 2: [42]bucket 5: [15, 25]bucket 7: [7, -3]true false

Notice that 15 and 25 share bucket 5, and 7 and -3 share bucket 7: those are collisions. Looking up 35 goes to bucket 5, compares it with 15 and 25, and finds nothing. As long as buckets stay short, this is fast.

Real tables keep buckets short by resizing: when the table becomes too full (Java's HashMap uses a default load factor of 0.75), it creates a bigger array and moves every entry into its new bucket. This costs O(n) occasionally, but like the dynamic array in the complexity article, it averages out to O(1) per insertion.

A HashSet<T> stores unique values. A HashMap<K, V> stores key-value pairs with unique keys. Here are the methods you will use daily:

The merge method is a compact way to count: "if there is no value for this key, store 1, otherwise add 1 to the existing value". And computeIfAbsent(key, k -> new ArrayList<>()) creates a list the first time a key appears, which makes grouping easy.

// File: Main.javaimport java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.TreeMap;public class Main {    public static void main(String[] args) {        String text = "to be or not to be that is the question to be";        Map<String, Integer> freq = new HashMap<>();        for (String word : text.split(" ")) {            freq.merge(word, 1, Integer::sum);        }        System.out.println(new TreeMap<>(freq));        // sorted copy, so the output is predictable        String best = null;        for (Map.Entry<String, Integer> entry : freq.entrySet()) {            boolean higher = best == null || entry.getValue() > freq.get(best);            boolean tieButEarlier = best != null && entry.getValue().equals(freq.get(best)) && entry.getKey().compareTo(best) < 0;            if (higher || tieButEarlier) {                best = entry.getKey();            }        }        System.out.println("most frequent: " + best + " (" + freq.get(best) + ")");        System.out.println(freq.getOrDefault("hamlet", 0) + " " + freq.containsKey("be"));        Map<Integer, List<String>> byLength = new TreeMap<>();        for (String word : freq.keySet()) {            byLength.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);        }        for (List<String> group : byLength.values()) {            java.util.Collections.sort(group);        }        System.out.println(byLength);    }}

{be=3, is=1, not=1, or=1, question=1, that=1, the=1, to=3}most frequent: be (3)0 true{2=[be, is, or, to], 3=[not, the], 4=[that], 8=[question]}

A few things to notice:

• We never print the raw HashMap, because its iteration order is not defined. Two different Java versions may print the same map in different orders. We copy it into a TreeMap (sorted by key) when we need a predictable order. Use LinkedHashMap to keep insertion order.
• Finding the most frequent word needed a tie-break rule (alphabetical), because "to" and "be" both appear three times. A problem should tell you what to do on ties, and if it does not, ask.
• getOrDefault("hamlet", 0) avoids the null that get would return for a missing key. A very common crash is int count = map.get(key); for an absent key, which tries to unbox null.

Use a HashSet when you only care whether something has appeared. The duplicate check from the first article is the template: for each value, if it is already in the set, you found a duplicate. Otherwise add it. O(n) time, O(n) space.

Use a HashMap<Key, Integer> when the keys can be anything: words, large numbers, mixed characters. You saw array-based counting in Arrays and Strings. The map version works for any key, and merge(key, 1, Integer::sum) keeps it short. This is O(n) overall.

Problem. Given an array of integers and a target, return the indexes of two different elements that add up to the target. Assume exactly one solution exists, or return an empty array if none does.

Brute force. Check every pair: O(n^2) time, O(1) space.

Optimization. For each x, the number you need is target - x, the complement. So, walking through the array, ask: "have I already seen target - x?" If yes, you are done. If not, remember x (and its index) for the future. A HashMap from value to index answers each question in O(1).

Dry run on [2, 7, 11, 15] with target 9:

Two details matter. First, we look up before we store. If we stored first, an element could pair with itself: for [3, 4] with target 6, 3 would "find" itself. Looking up first means an element can only pair with an earlier one, which still finds every pair, because the later partner will see the earlier one. For [3, 3] with target 6, the first 3 is stored, and the second 3 finds it.

Second, overflow: computing target - x in int arithmetic can wrap around for extreme values and create a false match. The code below computes the complement as a long, and skips it if it cannot be an int.

// File: Main.javaimport java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main {    // Brute force: O(n^2).    static int[] twoSumBrute(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            for (int j = i + 1; j < nums.length; j++) {                if ((long) nums[i] + nums[j] == target) {                    return new int[] {i, j};                }            }        }        return new int[0];    }    // Hash map: O(n) time on average, O(n) space.    static int[] twoSum(int[] nums, int target) {        Map<Integer, Integer> seen = new HashMap<>();      // value -> index where we saw it        for (int i = 0; i < nums.length; i++) {            long need = (long) target - nums[i];            if (need >= Integer.MIN_VALUE && need <= Integer.MAX_VALUE) {                Integer j = seen.get((int) need);                if (j != null) {                    return new int[] {j, i};                }            }            seen.put(nums[i], i);        }        return new int[0];    }    // The same idea with int arithmetic. Wrong for extreme values.    static int[] twoSumOverflowBug(int[] nums, int target) {        Map<Integer, Integer> seen = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            Integer j = seen.get(target - nums[i]);        // may overflow            if (j != null) {                return new int[] {j, i};            }            seen.put(nums[i], i);        }        return new int[0];    }    public static void main(String[] args) {        int[][] inputs = {{2, 7, 11, 15}, {3, 2, 4}, {3, 3}, {1, 2, 3}, {}};        int[] targets = {9, 6, 6, 100, 5};        for (int t = 0; t < inputs.length; t++) {            System.out.println(Arrays.toString(twoSumBrute(inputs[t], targets[t])) + " " + Arrays.toString(twoSum(inputs[t], targets[t])));        }        int[] extreme = {Integer.MAX_VALUE, Integer.MAX_VALUE};        System.out.println(Arrays.toString(twoSum(extreme, -2)) + " " + Arrays.toString(twoSumOverflowBug(extreme, -2)));    }}

[0, 1] [0, 1][1, 2] [1, 2][0, 1] [0, 1][] [][] [][] [0, 1]

The last line shows the overflow bug: the true answer is "no pair", but with int arithmetic, -2 - Integer.MAX_VALUE wraps around to Integer.MAX_VALUE, so the buggy version reports a pair that does not add up to -2. Most test sets will not include such a case, but a careful candidate mentions it.

Problem. Group words that are anagrams of each other: ["eat", "tea", "tan", "ate", "nat", "bat"].

Anagrams share the same letters, so if you sort the letters of each word, anagrams produce the same string. Use that sorted string as the key of a map from key to list of words. The key is a canonical form: a single representative for everything that should be treated as the same.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Map;import java.util.TreeMap;public class Main {    static Map<String, List<String>> groupAnagrams(String[] words) {        Map<String, List<String>> groups = new TreeMap<>();     // TreeMap only to print in a stable order        for (String word : words) {            char[] letters = word.toCharArray();            Arrays.sort(letters);            String key = new String(letters);                    // "eat", "tea" and "ate" all become "aet"            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);        }        return groups;    }    public static void main(String[] args) {        System.out.println(groupAnagrams(new String[] {"eat", "tea", "tan", "ate", "nat", "bat"}));        System.out.println(groupAnagrams(new String[] {""}));        System.out.println(groupAnagrams(new String[] {}));    }}

{abt=[bat], aet=[eat, tea, ate], ant=[tan, nat]}{=[]}{}

Complexity: for n words of length up to k, sorting each word is O(k log k), so the total is O(n × k log k). You can bring the key computation down to O(k) per word with a 26-slot count array turned into a string, if the words use only lowercase letters. Space is O(n × k) for the groups.

A hash table needs two operations from its keys: hashCode() to find the bucket, and equals() to confirm a match inside the bucket. Java's contract says:

If two objects are equal (a.equals(b) is true), they must return the same hashCode().

The reverse is not required: two different objects may share a hash code (that is a collision, and it is fine).

If you override equals but not hashCode, equal objects will have different hash codes (the default one is based on the object's identity), so they will probably land in different buckets, and the table will never discover they are equal. The lookup fails even though an equal key is inside.

// File: Main.javaimport java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Objects;import java.util.Set;public class Main {    static class BrokenPoint {        final int x;        final int y;        BrokenPoint(int x, int y) {            this.x = x;            this.y = y;        }        @Override        public boolean equals(Object other) {            if (!(other instanceof BrokenPoint)) {                return false;            }            BrokenPoint p = (BrokenPoint) other;            return x == p.x && y == p.y;        }        // hashCode is not overridden. This breaks the contract.    }    static class Point {        final int x;        final int y;        Point(int x, int y) {            this.x = x;            this.y = y;        }        @Override        public boolean equals(Object other) {            if (!(other instanceof Point)) {                return false;            }            Point p = (Point) other;            return x == p.x && y == p.y;        }        @Override        public int hashCode() {            return Objects.hash(x, y);              // uses the same fields as equals        }    }    public static void main(String[] args) {        Set<BrokenPoint> broken = new HashSet<>();        broken.add(new BrokenPoint(1, 2));        System.out.println(broken.contains(new BrokenPoint(1, 2)));    // almost certainly false        Set<Point> good = new HashSet<>();        good.add(new Point(1, 2));        System.out.println(good.contains(new Point(1, 2)));            // true        List<Integer> key = new ArrayList<>();                          // a mutable key        Map<List<Integer>, String> map = new HashMap<>();        map.put(key, "stored");        key.add(1);                                                     // changes the key's hash code        System.out.println(map.get(key) + " " + map.get(new ArrayList<Integer>()));    }}

falsetruenull null

The first line is "almost certainly" false: it depends on the two objects' identity hash codes being different, which they are with overwhelming probability, but it is not something to build on. The point is that we cannot count on a match. If you compile this program with javac -Xlint:all, the compiler warns that BrokenPoint overrides equals without hashCode, which is a good reason to turn warnings on.

The last line shows the second hazard: never mutate an object that you used as a key in a way that changes its hashCode. The entry was stored in the bucket for the empty list's hash code. After the change, neither the changed list nor a fresh empty list finds it: the entry is still in the map and takes up space, but nothing can reach it.

Practical rules:

• If you override equals, override hashCode, using the same fields.
• Use immutable keys: String, Integer, Long, Character, and your own classes with final fields.
• Do not use arrays as keys: two arrays with the same contents are different keys (arrays use identity). Convert to a List, a String, or build a string key such as x + "," + y.
• Java's record types (available from Java 16) generate equals and hashCode for you from their fields.

Hashing trades memory for speed. If a problem forbids extra memory, you might sort instead (O(n log n)), as we do in Two Pointers.

• Unboxing null. int c = map.get(key) crashes if the key is absent. Use getOrDefault, containsKey or merge.
• Storing before looking up in a complement search, so an element pairs with itself.
• Overflow in complements. target - x can overflow int. Use long when values may be extreme.
• Relying on iteration order. HashMap and HashSet do not guarantee any order.
• Mutating keys. Never change an object used as a key.
• Missing hashCode. Overriding equals alone breaks lookups.
• Arrays as keys. They compare by identity, not by contents.
• Modifying a map while iterating over it. Adding or removing during a for-each over the map throws ConcurrentModificationException. Collect changes and apply them afterwards, or use an iterator's remove.
• Using a hash map when an array would do. For lowercase letters, int[26] is simpler and faster.
• Forgetting that null keys exist. HashMap allows one null key, but Map.of and ArrayDeque do not allow null. Avoid null keys unless you must.

static Map<String, Integer> countWords(String[] words) {    Map<String, Integer> counts = new HashMap<>();    for (String w : words) {        counts.put(w, counts.get(w) + 1);    }    return counts;}

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    public static void main(String[] args) {        List<List<Integer>> buckets = new ArrayList<>();        for (int i = 0; i < 10; i++) {            buckets.add(new ArrayList<>());        }        for (int key : new int[] {13, 23, 33, 14, 5}) {            buckets.get(Math.floorMod(key, 10)).add(key);        }        for (int i = 0; i < 10; i++) {            if (!buckets.get(i).isEmpty()) {                System.out.println("bucket " + i + ": " + buckets.get(i));            }        }        System.out.println("comparisons for 43: " + buckets.get(Math.floorMod(43, 10)).size());    }}

bucket 3: [13, 23, 33]bucket 4: [14]bucket 5: [5]comparisons for 43: 3

// File: Main.javaimport java.util.HashMap;import java.util.Map;public class Main {    static boolean containsNearbyDuplicate(int[] nums, int k) {        Map<Integer, Integer> lastIndex = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            Integer last = lastIndex.get(nums[i]);            if (last != null && i - last <= k) {                return true;            }            lastIndex.put(nums[i], i);        }        return false;    }    public static void main(String[] args) {        System.out.println(containsNearbyDuplicate(new int[] {1, 2, 3, 1}, 3));        System.out.println(containsNearbyDuplicate(new int[] {1, 0, 1, 1}, 1));        System.out.println(containsNearbyDuplicate(new int[] {1, 2, 3, 1, 2, 3}, 2));        System.out.println(containsNearbyDuplicate(new int[] {}, 5));        System.out.println(containsNearbyDuplicate(new int[] {7, 7}, 0));    }}

truetruefalsefalsefalse

// File: Main.javaimport java.util.Arrays;import java.util.HashSet;import java.util.Set;import java.util.TreeSet;public class Main {    static int[] intersection(int[] a, int[] b) {        Set<Integer> inA = new HashSet<>();        for (int x : a) {            inA.add(x);        }        Set<Integer> common = new TreeSet<>();        for (int y : b) {            if (inA.contains(y)) {                common.add(y);            }        }        int[] result = new int[common.size()];        int i = 0;        for (int value : common) {            result[i++] = value;        }        return result;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(intersection(new int[] {1, 2, 2, 1}, new int[] {2, 2})));        System.out.println(Arrays.toString(intersection(new int[] {4, 9, 5}, new int[] {9, 4, 9, 8, 4})));        System.out.println(Arrays.toString(intersection(new int[] {}, new int[] {1})));        System.out.println(Arrays.toString(intersection(new int[] {1, 2}, new int[] {3, 4})));    }}

[2][4, 9][][]

// File: Main.javaimport java.util.HashMap;import java.util.Map;import java.util.TreeMap;public class Main {    static Map<String, Integer> countWordsBuggy(String[] words) {        Map<String, Integer> counts = new HashMap<>();        for (String w : words) {            counts.put(w, counts.get(w) + 1);        }        return counts;    }    static Map<String, Integer> countWordsOne(String[] words) {        Map<String, Integer> counts = new HashMap<>();        for (String w : words) {            counts.put(w, counts.getOrDefault(w, 0) + 1);        }        return counts;    }    static Map<String, Integer> countWordsTwo(String[] words) {        Map<String, Integer> counts = new HashMap<>();        for (String w : words) {            counts.merge(w, 1, Integer::sum);        }        return counts;    }    public static void main(String[] args) {        String[] words = {"b", "a", "b"};        try {            countWordsBuggy(words);        } catch (NullPointerException e) {            System.out.println("buggy version throws NullPointerException");        }        System.out.println(new TreeMap<>(countWordsOne(words)));        System.out.println(new TreeMap<>(countWordsTwo(words)));    }}

buggy version throws NullPointerException{a=1, b=2}{a=1, b=2}

// File: Main.javaimport java.util.HashSet;import java.util.Set;public class Main {    static int longestConsecutive(int[] nums) {        Set<Long> set = new HashSet<>();        for (int x : nums) {            set.add((long) x);        }        int best = 0;        for (long x : set) {            if (!set.contains(x - 1)) {            // x starts a run                long current = x;                int length = 1;                while (set.contains(current + 1)) {                    current++;                    length++;                }                best = Math.max(best, length);            }        }        return best;    }    public static void main(String[] args) {        System.out.println(longestConsecutive(new int[] {100, 4, 200, 1, 3, 2}));        System.out.println(longestConsecutive(new int[] {}));        System.out.println(longestConsecutive(new int[] {0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));        System.out.println(longestConsecutive(new int[] {1, 1, 1}));        System.out.println(longestConsecutive(new int[] {-1, -2, -3, 10}));        System.out.println(longestConsecutive(new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE}));    }}

409131

• Next: Recursion and Backtracking teaches the thinking behind trees, divide and conquer, and search.
• Soon: Prefix Sums and Difference Arrays combine prefix sums with a hash map to count subarrays with a given sum, and Sliding Window uses frequency maps for substring problems.
• Practice habit: whenever you write a nested loop whose inner loop only asks "is there a value such that ...?", ask whether a hash set or map could answer it in O(1).