HashMap and HashSet in Java

A hash table stores values so that inserting, finding, and removing one takes O(1) time on average, no matter how many values it holds. Many brute-force solutions become optimal with one change: an inner loop that searches for something becomes a hash table lookup.

How a hash table works

A hash function turns a key into a number (its hash).
The hash, modulo the number of buckets, picks the bucket where the key is stored.
To find a key later, compute its hash again and look only in that bucket.

graph LR
    k1["key: 'apple'"] -->|"hash % 8 = 3"| b3["bucket 3: apple"]
    k2["key: 'grape'"] -->|"hash % 8 = 6"| b6["bucket 6: grape, lime"]
    k3["key: 'lime'"] -->|"hash % 8 = 6"| b6

Collisions. Two different keys can land in the same bucket (grape and lime above). The table then compares the keys themselves with equals to find the right one. Java's HashMap keeps the entries of one bucket in a chain, and converts a long chain into a balanced tree.
Resizing. When the number of entries passes the load factor (by default 0.75) times the number of buckets, the table doubles its buckets and moves every key. Like ArrayList.add, that makes inserts amortized O(1).
Worst case. If many keys collide, operations degrade toward O(n). String.hashCode is a fixed formula, so the same string has the same hash in every run.

That's why a key class needs both hashCode (to pick the bucket) and equals (to compare keys within it). Two keys that are equals must return the same hashCode.

`HashSet`: membership

A HashSet<E> stores unique values and answers "is this value present?"

Operation	Method	Time
add	`add(x)`: returns `false` if `x` was already present	`O(1)`
check	`contains(x)`	`O(1)`
remove	`remove(x)`: returns `true` if it was present	`O(1)`
size	`size()`	`O(1)`

A HashSet<Integer> holds boxed Integer objects: Java wraps each int in an Integer automatically. The return value of add is useful on its own. It detects duplicates without a separate contains call:

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();
        for (int x : new int[]{3, 1, 3, 2, 1}) {
            if (!seen.add(x)) {
                System.out.println("duplicate " + x);
            }
        }
        System.out.println("unique values: " + seen.size());
    }
}

Output

duplicate 3
duplicate 1
unique values: 3

Set operations

addAll is union, retainAll is intersection, and removeAll is difference. Each changes the set it is called on, so the example copies first. A HashSet prints in an unspecified order, so sorted copies a set into a TreeSet (a set that keeps its values in sorted order, with O(log n) operations) before printing.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    static List<Integer> sorted(Set<Integer> set) {
        return List.copyOf(new TreeSet<>(set)); // a TreeSet keeps its values in sorted order
    }

    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(List.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(List.of(3, 4, 5));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);
        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);
        Set<Integer> symmetric = new HashSet<>(union);
        symmetric.removeAll(intersection);

        System.out.println("union        " + sorted(union));
        System.out.println("intersection " + sorted(intersection));
        System.out.println("a - b        " + sorted(difference));
        System.out.println("symmetric    " + sorted(symmetric));
        System.out.println("subset: " + a.containsAll(List.of(3, 4)) + ", disjoint: " + java.util.Collections.disjoint(a, b));
    }
}

Output

union        [1, 2, 3, 4, 5]
intersection [3, 4]
a - b        [1, 2]
symmetric    [1, 2, 5]
subset: true, disjoint: false

`HashMap`: counting, grouping, and lookup tables

A HashMap<K, V> maps each unique key to a value. null is allowed as a key and as a value.

Operation	Method	Time
insert or overwrite	`put(k, v)`: returns the old value, or `null`	`O(1)`
read	`get(k)`: returns the value, or `null` if the key is absent	`O(1)`
read with a default	`getOrDefault(k, d)`	`O(1)`
change in place	`merge(k, v, f)`, `computeIfAbsent(k, f)`, `putIfAbsent(k, v)`	`O(1)`
remove	`remove(k)`: returns the old value, or `null`	`O(1)`
check	`containsKey(k)`	`O(1)`

Counting with `merge`

merge(key, 1, Integer::sum) stores 1 if the key is absent. Otherwise it replaces the value with Integer.sum(old, 1). The lookup and the update happen in one call:

Java

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : "mississippi".toCharArray()) {
            counts.merge(c, 1, Integer::sum);
        }
        System.out.println(new TreeMap<>(counts)); // a TreeMap prints its keys in sorted order
    }
}

Output

{i=4, m=1, p=2, s=4}

Grouping

computeIfAbsent(key, f) calls f to create the value only when the key is absent, and returns the value either way. Here it creates an empty list, so add can follow immediately:

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : words) {
            char[] letters = w.toCharArray();
            Arrays.sort(letters); // anagrams share the same sorted letters
            groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(w);
        }
        List<List<String>> result = new ArrayList<>(groups.values());
        result.sort(Comparator.comparing(group -> group.get(0)));
        System.out.println(result);
    }
}

Output

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

Remembering positions

Storing each value's index lets you answer "where did I see this value?" in O(1). This is the technique behind Two Sum. putIfAbsent stores a value only when the key is absent. get returns null for a missing key, and string concatenation prints null as the text null:

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int[] nums = {10, 20, 10, 30, 20};
        Map<Integer, Integer> firstSeen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            firstSeen.putIfAbsent(nums[i], i); // keeps the first index only
        }
        System.out.println(firstSeen.get(20) + " " + firstSeen.get(99));
    }
}

Output

1 null

What can be a key

A key class must have consistent hashCode and equals methods:

Works as a key	Needs care
`Integer`, `Long`, `Character`, `Boolean`	arrays (`int[]`): `equals` and `hashCode` use identity, so two arrays with the same contents are different keys
`String`	`Double`: `equals` treats `NaN` as equal to itself and `0.0` as different from `-0.0`
`List<T>` of hashable `T` (compared by contents)	a class that does not override `equals` and `hashCode`: it uses identity
a `record`: `equals` and `hashCode` use all its components	an object that changes after it is stored as a key: the entry can no longer be found

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    record Point(int x, int y) {}

    public static void main(String[] args) {
        List<Point> path = List.of(new Point(0, 0), new Point(1, 0), new Point(0, 0));
        Set<Point> visited = new HashSet<>();
        for (Point p : path) {
            if (!visited.add(p)) {
                System.out.println("revisited " + p);
            }
        }

        // A List of the coordinates also works as a key, with no extra class:
        Set<List<Integer>> cells = new HashSet<>();
        cells.add(List.of(0, 1));
        cells.add(List.of(2, 3));
        System.out.println(cells.contains(List.of(2, 3)));
    }
}

Output

revisited Point[x=0, y=0]
true

Arrays are the usual surprise. Two arrays with the same contents are different keys, while two lists with the same contents are the same key:

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        int[] first = {1, 2};
        int[] second = {1, 2};
        Set<int[]> arrays = new HashSet<>();
        arrays.add(first);
        System.out.println(arrays.contains(second)); // arrays compare by identity

        Set<List<Integer>> lists = new HashSet<>();
        lists.add(List.of(1, 2));
        System.out.println(lists.contains(List.of(1, 2))); // lists compare by contents
    }
}

Output

false
true

Things to watch for

Iteration order is unspecified. Iterating a HashMap or HashSet can give a different order on a different Java version or with a different insertion history. When order matters, sort the results, or walk the original input and use the map only for lookups. LinkedHashMap iterates in insertion order. TreeMap and TreeSet iterate in sorted key order and cost O(log n) per operation.
get returns null if the key is missing. Assigning that to an int (int c = map.get(k)) throws NullPointerException while unboxing. Use getOrDefault or containsKey when the key might be absent.
Compare boxed values with equals. == on two Integer objects compares references, so it is unreliable for values outside a small cached range.
Do not modify a map or set while iterating it. Adding or removing entries inside a for loop over it throws ConcurrentModificationException. Use an Iterator and its remove, or removeIf.
Pre-size when you know the count. new HashMap<>(capacity) sets the initial number of buckets. To hold n entries without a resize, the capacity must be larger than n / 0.75.
Small integer keys. If keys are in a small known range, such as lowercase letters or values 0 to 999, a plain int[26] is faster and uses no boxing.

Java

public class Main {
    public static void main(String[] args) {
        int[] counts = new int[26];
        for (char c : "hello".toCharArray()) {
            counts[c - 'a']++;
        }
        System.out.println("l appears " + counts['l' - 'a'] + " times");
    }
}

Output

l appears 2 times

Hashing patterns in this section

Pattern	Idea	Lessons
membership	put one collection in a set, then check the other against it	subset, disjoint arrays, word formation
pairs	look up the partner of each element	two numbers that add up to k, symmetric pairs, a + b = c + d
lookup table	map each key to the thing it leads to	trace a journey
prefix sums	a repeated running total means a zero-sum range	subarray with sum 0
counting	count occurrences, then scan the input again	first non-repeating integer
seen nodes	store node identities to detect repeats	linked list cycle, removing duplicates

The last five lessons in this section revisit earlier problems and solve them with hashing.

How a hash table works

HashSet: membership

Set operations

HashMap: counting, grouping, and lookup tables

Counting with merge

Grouping

Remembering positions

What can be a key

Things to watch for

Hashing patterns in this section

`HashSet`: membership

`HashMap`: counting, grouping, and lookup tables

Counting with `merge`