Hash Map Internals
Overview
Knowing how to use a HashMap is easy; knowing *how it actually works* is the most frequently asked systems design and senior Java interview question. A HashMap is an array of Linked Lists (called Buckets). When you put a Key-Value pair in, it runs the Key through a Math function (a Hash Function) to generate an integer index. It drops the value into that specific array index. This math-based routing is why HashMaps achieve O(1) instant lookups.
Syntax
By hashing the Key, we instantly know exactly which array bucket to look inside without having to search through the others.
// This is a simplified version of what happens when you do map.put(Key, Value)
public void put(String key, String value) {
// 1. Generate the hash code (a giant integer)
int hash = key.hashCode();
// 2. Compress the hash code to fit inside our array size (e.g., size 16)
int index = Math.abs(hash % 16);
// 3. Place the data in the array at that exact index
buckets[index] = new Node(key, value);
}If too many collisions happen, the Linked List gets long, degrading performance to O(N). To fix this, Java 8 automatically upgrades long Linked Lists into Red-Black Trees (O(log N)).
// What happens if "Apple" and "Banana" both hash to Index 5?
// This is a COLLISION.
// Java handles this by turning Index 5 into a Linked List!
// buckets[5] -> [Apple Node] -> [Banana Node] -> null
// When you call map.get("Banana"):
// 1. Math routing instantly jumps to Index 5
// 2. It traverses the tiny Linked List until node.key.equals("Banana")Common Pitfalls
- Assuming a 'good' Hash Function prevents all collisions. Because the array is finite, collisions are mathematically guaranteed (Pigeonhole Principle).
- Using a mutable object as a HashMap key. If you change a field that is used in `hashCode()` after inserting it, the map will never be able to find the object again.
Interview Tips
- This is a guaranteed senior-level question. Explain the process: Hash the Key, Modulo the array size, place in the bucket.
Real-World Example
Any time you build a custom Java Object (like a User class) and intend to use it as a Key in a HashMap or a value in a HashSet, you absolutely must override these internals.
public class Coordinate {
int x, y;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Coordinate)) return false;
Coordinate c = (Coordinate) o;
return x == c.x && y == c.y;
}
@Override
public int hashCode() {
// High quality hash function prevents collisions
return Objects.hash(x, y);
}
}