BrewlearnHow HashMap works
hashCode → bucket, equals within bucket, load factor, resize, tree bins.
Numbered hooks
A HashMap is an array of buckets, like a coat check with numbered hooks. It calls **key.hashCode(), mixes the bits, and turns the result into a bucket index**. Lookups jump straight to that one bucket.
// put("cat", 1):
int h = "cat".hashCode(); // 98262
// mix bits, keep the low ones:
// → bucket 7 of 16equals() settles it
Different keys can land in the same bucket (a collision). Inside the bucket, HashMap uses **equals() to find the exact key. So: hashCode picks the bucket, equals confirms the key. That's why equal objects must** have equal hash codes.
Your turn
Every Tag has the same hash code. What does this print?
record Tag(String s) {
public int hashCode() { return 7; }
}
void main() {
var m = new HashMap<Tag, Integer>();
m.put(new Tag("x"), 10);
m.put(new Tag("y"), 20);
var v = m.get(new Tag("y"));
System.out.println(m.size() + " " + v);
}1 202 202 null
Show the answer
Both keys share one bucket, but the record's generated **equals() tells them apart. The map is still correct**: size 2, and get finds 20. It's just slower, because every lookup searches one crowded bucket.
Load factor and resizing
Default capacity 16, load factor 0.75. When size exceeds 16 × 0.75 = 12, the 13th entry triggers a resize: the table doubles to 32 and every entry is redistributed (rehashed). Shorter buckets keep lookups near O(1).
var m = new HashMap<Integer, String>();
for (int i = 1; i <= 13; i++) {
m.put(i, "v"); // 13th put: 16 → 32
}Tree bins (Java 8+)
If one bucket gets crowded (more than 8 entries) and the table has at least 64 buckets, HashMap turns that bucket into a red-black tree: O(log n) instead of a slow list walk. If the table is still smaller than 64, it resizes instead.
Writing hashCode
public int hashCode() {
return 42;
}Equal objects do get equal hashes, so it's correct, but every key collides into one bucket.
public int hashCode() {
return Objects.hash(name, age);
}Mixes all fields used by equals. Records generate this for you.
Why it matters
In 2011, researchers showed that attackers could send web requests full of colliding keys and freeze servers ("hash flooding"). Java 8's tree bins (JEP 180) cap the damage. Also handy: since Java 19, HashMap.newHashMap(n) sizes a map for n entries without any resize.
Key takeaways
- hashCode() picks the bucket; equals() confirms the key
- Default capacity 16, load factor 0.75 → resize after 12 entries
- Resizing doubles the table and rehashes entries
- Since Java 8, crowded buckets (more than 8 entries) become red-black trees
💡 Like a library: the hash is the shelf number, and equals() is reading the spines on that shelf to find your exact book.
"Aa" and "BB" have the same String hash code: 2112. Run it yourself! Strings built from these blocks, like "AaBB" and "BBAa", collide too, which is how hash-flooding attacks build endless colliding keys.
Practice questions
With default settings, when does a new HashMap first resize?
- When the 16th entry is added
- When it holds more than 12 entries (16 × 0.75)
- When any bucket has 2 entries
- Never — HashMap has a fixed size
Check your answer
When it holds more than 12 entries (16 × 0.75). The default capacity is 16 and the load factor 0.75, so the threshold is 12. Adding the 13th entry doubles the table to 32 buckets.
In Java 8+, what does HashMap do when many keys land in the same bucket?
- Throws an exception because collisions are illegal
- Discards the colliding keys
- Once a bucket holds more than 8 entries (and the table has at least 64 buckets), it converts that bucket into a balanced red-black tree
- Switches the whole map to a TreeMap
Check your answer
Once a bucket holds more than 8 entries (and the table has at least 64 buckets), it converts that bucket into a balanced red-black tree. Treeifying a crowded bucket makes lookups there O(log n) instead of O(n). If the table is still small, HashMap resizes instead of treeifying.