Skip to content
Ameen Abozaid
Englishالعربية
PublishedBEG-041-L04

Inside HashMap and HashSet

  • Lesson 4 of 5
  • 11 min read
  • Beginner
On This Lesson 11 topics

Lesson Overview

You already use HashMap and HashSet from the collections module. Now you know what is inside them: an array of buckets, chains of entries, a load factor, and resizing. This lesson connects that picture to the real JDK classes, and to the three rules that decide whether they work well for your own keys.

The rules: write equals and hashCode together, never change a key after you have stored it, and never rely on iteration order. Each rule follows directly from the mailbox picture. A key whose hash code changes is a letter filed in one box and then searched for in another.

Why this matters: nearly every Java backend service has maps and sets keyed by ids, names, or small value objects. The most painful bugs here are silent: a lookup returns null, a set holds duplicates, and nothing throws.

This lesson builds on the previous three, on the equals/hashCode contract (BEG-026), on Map and Set from the collections module (BEG-030), and on generics.

Learning Objectives

By the end of this lesson you will be able to:

  • State HashMap's default capacity and load factor, and when its first resize happens.
  • Explain that a HashSet is backed by a HashMap.
  • Explain what Java 8 changed for long chains.
  • Demonstrate what happens when a class overrides equals but not hashCode.
  • Demonstrate and explain why changing a key after insertion makes the entry unreachable.
  • Explain why you cannot rely on iteration order, and name a map that does keep one.

Written Explanation

What HashMap is

HashMap<K,V> is the hash table from the last lessons. According to the Java SE 21 documentation:

  • the default capacity (number of buckets) is 16 and the default load factor is 0.75;
  • when the number of entries exceeds load factor times capacity, the table is rehashed to about twice as many buckets, so the first resize with defaults is when the 13th entry arrives;
  • get and put take constant time, assuming the hash function disperses the elements properly among the buckets;
  • it allows a null key and null values.

The implementation uses chaining, as you learned in the last lesson. Two details in the OpenJDK source for JDK 21 are worth knowing, although you should treat them as implementation details that may change:

  • The table length is always a power of two, and the bucket index is (n - 1) & hash, a mask instead of a remainder. Before that, HashMap mixes the upper 16 bits of the hash code into the lower 16 (h ^ (h >>> 16)), so hash codes that differ only in their high bits still spread.
  • Because the mask uses only the low bits, it never yields a negative index, and that is why HashMap has none of the negative-number problems from lesson 2.

Long chains become trees

Chains can get long when many keys share a bucket, whether by bad luck or by a poor hashCode. JEP 180, delivered in Java 8, changed HashMap so that when a bucket holds too many entries, it stops using a linked list and uses a balanced tree, which lowers the worst case for that bucket from O(n) to O(log n). In the JDK 21 source, the switch happens at 8 entries in a bucket, and only when the table has at least 64 buckets (otherwise the table resizes instead). The HashMap documentation adds that when keys are Comparable, comparing them can help break ties.

This is a safety net, not a licence for bad hash codes. The documentation still warns that using many keys with the same hashCode() is a sure way to slow down any hash table. Tree buckets depend on keys being Comparable to work well; keys that cannot be compared stay slow. You will see this in the lab.

HashSet is a HashMap in disguise

The Java documentation says HashSet is backed by a hash table, actually a HashMap instance. Your elements are the keys; every key has the same dummy value. So set.add(x) is essentially map.put(x, dummy), and it returns false if an equal element is already present. Everything in this lesson about keys applies to set elements too.

Rule 1: override equals and hashCode together

HashMap computes hashCode() to choose the bucket and then uses equals inside it. If two equal keys have different hash codes, they go to different buckets. The map never compares them, so get misses and a set accepts duplicates. The default hashCode is identity-based, so a class that overrides only equals fits this trap exactly.

Rule 2: never change a key after you insert it

If the hash code of a key depends on a field and you change that field after put, the entry stays in its old bucket, but get(key) now computes a new hash code and looks in a different bucket. The entry is still in the map, using memory, but unreachable by normal means. The Map documentation says to take great care with mutable keys: a map's behavior is not specified if an object's value changes in a way that affects equals while it is a key.

How to avoid it: use immutable keys such as String, Integer, Long, enums, and records whose components are immutable. If a key class must have mutable fields, do not use those fields in equals or hashCode.

Rule 3: never rely on iteration order

The documentation for HashMap and HashSet says they make no guarantee about order, and not even that the order stays the same over time. The order depends on bucket positions, and on the capacity, which changes when the table resizes. If you need a predictable order, use LinkedHashMap, whose documented order is normally insertion order, or sort the keys (the comparators module).

Examples

Example 1: basic HashMap use (simple)

java
Map<String, Integer> ages = new HashMap<>();
ages.put("Ana", 30);
ages.put("Omar", 25);
ages.put("Ana", 31);
System.out.println(ages.get("Ana") + " " + ages.size() + " " + ages.get("Zed"));

Real output:

text
31 2 null

The second put("Ana", ...) finds the existing key through the same bucket and equals, and replaces the value. The map still has two entries, and a missing key gives null.

Example 2: equals without hashCode (practical)

java
static class BadPoint {
    final int x, y;
    BadPoint(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        return o instanceof BadPoint p && x == p.x && y == p.y;
    }
}
Set<BadPoint> set = new HashSet<>();
set.add(new BadPoint(1, 2));
set.add(new BadPoint(1, 2));
System.out.println(set.size() + " " + set.contains(new BadPoint(1, 2)));

Real output:

text
2 false

The two points are equals, yet the set holds both and says it does not contain a third equal one. Each object got its own identity-based hash code and probably a different bucket. (This is the likely outcome, not a promise: two identity hash codes could happen to land in the same bucket, so the result can vary between runs. The bug is that nothing guarantees the right result.) Adding hashCode() { return Objects.hash(x, y); } fixes it.

Example 3: a mutable key goes missing (realistic)

java
static class MutableKey {
    String name;
    MutableKey(String name) { this.name = name; }
    @Override public boolean equals(Object o) { return o instanceof MutableKey k && name.equals(k.name); }
    @Override public int hashCode() { return name.hashCode(); }
}
Map<MutableKey, String> m = new HashMap<>();
MutableKey k = new MutableKey("Ana");
m.put(k, "first");
k.name = "Ana2";
System.out.println(m.get(k) + " " + m.size() + " " + m.containsKey(new MutableKey("Ana")));

Real output:

text
null 1 false

The entry was stored in the bucket for "Ana". After the rename, get(k) looks in the bucket for "Ana2" and finds nothing. A fresh MutableKey("Ana") goes to the right bucket, but the stored key now says "Ana2", so equals fails. The map says size 1 yet cannot find the entry either way. Nothing throws an exception. The same happens with a List used as a key if you add to it after put, because a list's hash code depends on its contents.

Backend Insight

Map keys in real services are usually ids and small value objects: a user id, an order id, a pair of both. Records are an excellent fit, since they write equals and hashCode from their components, and their fields are final. For example, record OrderKey(long userId, long orderId) {} works as a key right away (a quick check: orders.get(new OrderKey(7, 99)) finds the value stored under an equal key, and a swapped key finds nothing).

Two habits from this lesson matter in production. First, if you know how many entries are coming, size the map for it: since Java 19, HashMap.newHashMap(expectedEntries) chooses the capacity so that no resize is needed. Second, never let a response order depend on HashMap iteration order: a test may pass today and fail after a resize or a JDK upgrade, and two servers may produce different orders for the same data.

Common Mistakes

Mistake 1: Overriding only equals (or only hashCode)

  • Incorrect: a key class with equals only, or hashCode only.
  • Correct: override both, using the same fields, or use a record.

Mistake 2: Mutating a key (or a set element) after inserting it

  • Incorrect: key.setName("new") while key is in a map.
  • Correct: remove the entry first, change the key, insert again, or better, make the key immutable.

Mistake 3: Relying on iteration order

Printed order from a HashMap looks stable on your machine, so people assume it is. The documentation promises nothing. Use LinkedHashMap or sorting when order matters.

Mistake 4: Assuming tree buckets make a bad hash code harmless

The tree switch limits damage only for comparable keys, and still costs more than good spread. Write a proper hashCode.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. State HashMap's default capacity and load factor, and the entry count at which the first resize happens.

Show solution A1

A1. Capacity 16, load factor 0.75. The first resize happens when the entry count exceeds 16 * 0.75 = 12, so with the 13th entry, and the table doubles to about 32 buckets.

A2. What class is behind a HashSet, and what do the set's elements become inside it?

Show solution A2

A2. A HashMap. The set's elements are used as the keys, and every key is paired with the same dummy value.

A3. Can you rely on the order in which a HashMap prints its keys? What can you use instead?

Show solution A3

A3. No, the documentation gives no guarantee, and the order can change when the table resizes. Use LinkedHashMap for insertion order, or sort the keys when you need a specific order.

Level B: Application

B1. A class Product(String sku, String name) overrides equals to compare sku only and does not override hashCode. Predict what happens when two Product objects with the same sku are added to a HashSet, and write the fix.

Show solution B1

B1. Two products with equal sku get different identity-based hash codes, so they probably go to different buckets and the set will most likely keep both and fail contains for an equal one. Fix:

java
@Override public int hashCode() { return Objects.hash(sku); }

It uses exactly the field that equals uses.

B2. A List<String> is used as a key in a HashMap, then a string is added to the list. Predict map.get(list) before and after the change.

Show solution B2

B2. Before: get(list) returns the stored value (here 1). After: null, because a list's hash code depends on its contents, so the lookup goes to another bucket. Run result: 1, then null, with m.size() still 1. A fresh List.of("a") also gives null, since the stored key has changed.

B3. You expect 1,000 entries. Give a call that creates a map that never needs to resize, and say why one a bit smaller would resize.

Show solution B3

B3. HashMap.newHashMap(1000) (Java 19 or later). A smaller capacity, such as 500 buckets, resizes once the entries pass 500 times 0.75, which is 375, since the limit is capacity times load factor. The documentation says that no rehash occurs if the initial capacity exceeds the maximum number of entries divided by the load factor.

Level C: Challenge

C1. A colleague says: "Since Java 8 buckets turn into trees, so a constant hashCode is fine." Reply in three or four sentences.

Show solution C1

C1. The tree switch only limits the worst case within a bucket from O(n) to O(log n), and it works best for keys that are Comparable. A constant hash code still puts every key into one bucket, so there is no O(1) lookup. The documentation still says that many keys with the same hashCode() slow down any hash table. A tree is a safety net, not a substitute for a good hash function.

C2. Design a key for a map from (country code, city name) to population. Show it as a record and explain why it is safe as a key. Then explain one way it could still become unsafe.

Show solution C2

C2.

java
record CityKey(String countryCode, String city) {}
Map<CityKey, Integer> population = new HashMap<>();
population.put(new CityKey("SA", "Riyadh"), 7_000_000);

(The number is an example value, not a real statistic.) A record generates equals and hashCode from both components, and its fields are final, so the hash cannot change after insertion. It could become unsafe if a component were a mutable object, such as a List or a StringBuilder field, which someone could modify later.

Mini Challenge

Write a short program that (1) puts three OrderKey(long userId, long orderId) records into a HashMap and looks one up, (2) builds a HashSet of a class with only equals and shows the duplicate problem, and (3) fixes it by adding hashCode. Print the set size before and after the fix.

Check your work: the record version needs no extra code; the broken set most likely prints a size of 2 for two equal objects; the fixed set prints 1; and you used the same fields in equals and hashCode.

Summary & Next Lesson

Key takeaways

  • HashMap is a chained hash table with default capacity 16 and load factor 0.75. It roughly doubles its buckets when entries exceed load factor times capacity.
  • Since Java 8, an overlong bucket can become a balanced tree, which limits the damage of poor hash codes but does not remove it.
  • HashSet is a HashMap that uses your elements as keys.
  • Override equals and hashCode together, never mutate a key after inserting it (prefer immutable keys and records), and never rely on iteration order.
  • Lookups are O(1) on average only if the hash codes are well spread.

Next lesson

Next, "Demo: MyHashMap and the constant-hashCode slowdown" is a hands-on build. You will write your own chained hash map with resizing, then time it with a key whose hashCode always returns the same number, and see the slowdown with real numbers.

Self-check

  1. What are HashMap's default capacity and load factor?
  2. What is inside a HashSet?
  3. What goes wrong if a class overrides equals but not hashCode?
  4. Why is a key lost if you change a field that feeds its hashCode after put?
  5. Why must you not depend on the order in which a HashMap returns its keys?
Show answers
  1. Capacity 16 and load factor 0.75.
  2. A HashMap; the set's elements are its keys.
  3. Equal objects can get different hash codes, so they land in different buckets: a set can hold duplicates and contains or get can miss.
  4. The entry stays in the bucket chosen by the old hash code, but get now looks in the bucket for the new one.
  5. The documentation gives no order guarantee, and the order can change when the table resizes or the JDK changes.

References

  • Oracle, HashMap (Java SE 21). It states the default capacity 16 and load factor 0.75, the rehash to about twice the buckets, constant-time get/put when hashes disperse well, no order guarantee, the tie-breaking by comparison for Comparable keys, the warning about many keys sharing a hashCode(), and newHashMap.
  • Oracle, HashSet (Java SE 21). It says a HashSet is backed by a HashMap instance and makes no iteration order guarantee.
  • Oracle, Map (Java SE 21). It warns that a map's behavior is unspecified if a mutable key changes in a way that affects equals.
  • Oracle, LinkedHashMap (Java SE 21). It says the encounter order is normally insertion order.
  • OpenJDK, JEP 180: Handle Frequent HashMap Collisions with Balanced Trees. It describes the switch from a linked list to a balanced tree in a crowded bucket (Java 8) and the worst case improving from O(n) to O(log n).
  • OpenJDK, HashMap.java in JDK 21. It shows the power-of-two table, the (n - 1) & hash index, the h ^ (h >>> 16) spreading, and the thresholds 8 and 64. These are implementation details and may change between versions.
  • Examples 1 to 3 and exercise results were compiled and run on JDK 21. The exact printing order of HashMap keys varies with the JDK and is deliberately not shown.

Practice

Apply this lesson with the module's lab, exercises and quiz.

Lab and exercises Quiz

Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.

Continue to next lesson

Type to search levels, phases, modules and lessons.