Table of contents
- Why does Map exist?
- What would life be without it?
- HashMap: the street analogy
- hashCode() and equals() explained
- Collisions: when two people share a house
- Load factor and resizing
- The other Map types
- The one rule you must never break
- Interview problems where Map is the answer
SECTION 1.
Why does Map even exist?
Before touching any internals, let's nail the real problem Map was built to solve because if you understand the problem, everything else makes sense automatically.
Imagine you work at a hotel front desk. 1,000 guests are checked in. Your boss walks over and asks:
The scenario
"Is John Smith in room 847?"
You have two choices for how to answer that.
The hook label is the key. The room key hanging on it is the value. You provide a key, you get the value back instantly.
One sentence summary: A Map lets you associate any key with any value and look that value up in O(1) time without scanning through everything.
SECTION 2.
What would life be like without it?
Without Map, you'd simulate it with parallel arrays or a list of pairs:
// Simulating a Map with parallel arrays, don't do this
String[] keys = {"alice", "bob", "carol"};
int[] values = {42, 17, 99};
// Finding "bob" = O(n) linear scan, disaster at scale
for (int i = 0; i < keys.length; i++) {
if (keys[i].equals("bob")) return values[i];
}
This works for 3 entries. With 1 million entries it's a disaster every lookup, every duplicate check, every deletion is O(n). Map eliminates all of that.
SECTION 3.
HashMap: the street analogy
HashMap is the most common Map implementation. Picture a street with 16 houses, that's Java's default starting size.
When you call map.put("alice", 42), Java asks: which house does Alice live in? It runs Alice's name through a math formula called hashCode(), say it produces 3. Alice goes into house #3 with her value. Later, map.get("alice") runs the same formula, gets 3, and jumps directly there. No loop. No scanning.
How put() works step by step:
SECTION 4.
hashCode() and equals() explained
These two methods are the core of how HashMap works. Understanding them removes 90% of the bugs juniors hit with Maps.
hashCode(): the address formula
Think of hashCode() as a fingerprint machine. Feed in any object, it spits out a number. The same object always gets the same number:
Java then shrinks that number to fit: 93029210 % 16 = house #10.
equals(): the ID check at the door
Once Java arrives at the right house, it needs to confirm it found the right person. Two different keys can land in the same house (collision). So Java checks each occupant with equals():
It checks the hash first (fast integer comparison), then equals() only if the hashes match. Smart optimization — avoids expensive object comparison most of the time.
SECTION 5.
Collisions: when two people share a house
The formula isn't perfect. Sometimes two keys land in the same bucket. Java's solution: form a linked chain inside that bucket like stacked mailboxes.
Usually chains are 1–2 entries long, so lookup is still very fast. But what if 20 keys pile up in one bucket? That's O(n) again.
Java 8 solved this: when a chain exceeds 8 nodes, it converts to a Red-Black Tree like reorganizing a pile of folders into a sorted filing cabinet. Worst case drops from O(n) to O(log n).
SECTION 6.
Load factor and resizing
Java watches a ratio called the load factor. By default it's 0.75, when 75% of buckets are occupied, it doubles the street and moves everyone.
If you know how many entries you'll add, pre-size the map to avoid expensive resizes:
SECTION 7.
The other Map types simply
SECTION 8.
The one rule you must never break
If you ever use a custom class as a Map key, you must override both hashCode() and equals(). Always. Together. Never just one.
public class User {
private final String id;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof User u)) return false;
return id.equals(u.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
SECTION 9.
Where Map is the answer in interviews
When you see these patterns in a problem, your first instinct should be to reach for a Map. Recognizing the pattern is half the interview.
RECAP
Everything in one place
Found this useful? Drop a comment below with the weirdest HashMap bug you've ever hit, I guarantee someone else has been burned by the exact same thing. If you're studying for interviews and want more posts like this covering Java internals, ArrayList, LinkedList, or system design, follow me here on dev.to or connect on LinkedIn . More coming soon.
About me:
Senior Java Software Engineer with 6+ years building backend systems, Kafka pipelines, distributed APIs, and cloud infrastructure. Writing to make the hard stuff simple. 🔗Connect on LinkedIn
Sources: java docs
Research and structure for this article were developed with the assistance of Claude by Anthropic. All code examples, analogies, and explanations were reviewed and validated by the author.