HashMap in Java

HashMap is Java’s primary key-value mapping implementation. It stores entries in an internal array of buckets, using each key’s hashCode() to determine the bucket and equals() to distinguish between keys in the same bucket. This combination provides O(1) average-case put and get operations.

Introduction

HashMap is the go-to data structure when you need to store and retrieve values by a key — fast. Under the hood, it turns each key into a bucket index using hashCode(), then uses equals() to tell apart the different keys that land in the same bucket. Done correctly, this gives you O(1) average-case insertion and lookup, regardless of how many entries you store. Done wrong — a broken hashCode() or a mutable key — and you get O(n) performance that degrades silently as the map grows.

The critical trap with HashMap is treating it as a simple dictionary when it is actually a carefully tuned data structure with real constraints. Keys must not change their hashCode() after insertion (or the entry becomes permanently unfindable). The map is not thread-safe — concurrent modification from multiple threads can corrupt internal state or throw ConcurrentModificationException. And because the backing array resizes when the load factor threshold is crossed, a burst of insertions can trigger an O(n) rehashing operation at the worst possible moment.

This post covers HashMap internals — bucket arrays, collision handling via chaining and treeification, the hash() spreading function — along with the failure scenarios that cause real production incidents: hash flooding attacks, unbounded growth, and the subtle difference between get() returning null because the key is absent versus because the value was null.

When to Use HashMap

Use HashMap when:

• You need to store and retrieve values by a unique key
• O(1) lookup performance is critical
• Keys are not ordered (if ordering matters, use TreeMap or LinkedHashMap)
• You need a mutable map; for immutable snapshots, consider Map.of() or Collections.unmodifiableMap()

Do not use HashMap when:

• You need sorted or insertion-order iteration (use TreeMap or LinkedHashMap)
• You need thread-safe operations (use ConcurrentHashMap)
• Keys may be null in a concurrent context (single null key is allowed but not thread-safe)
• You need primitive-key maps without boxing (use Trove or other specialized libraries)

Internal Structure

HashMap uses an array of Node<K,V> buckets. Each Node stores the key, value, hash, and a pointer to the next node in the bucket (for collision handling via chaining):

transient Node<K,V>[] table;
transient int size;

// When a bucket has > 8 entries, it converts to a TreeNode (Red-Black tree)
static final int TREEIFY_THRESHOLD = 8;

Mermaid Diagram: HashMap Structure

graph TD
    A["HashMap<K,V>"] --> B["table: Node[16]"]
    B --> C["bucket[0] → Node<K,V> → null"]
    B --> D["bucket[1] → Node → Node → null"]
    B --> E["bucket[2] null"]
    B --> F["bucket[3] → TreeNode (8+ entries)"]
    D --> D1["hash: 17<br/>key<br/>value<br/>next: Node"]
    D1 --> D2["hash: 17<br/>key<br/>value<br/>next: null"]
    F --> F1["TreeNode<br/>Red-Black tree"]

Hash Collisions

When two different keys produce the same hash code (or their hashes map to the same bucket index), a collision occurs. HashMap handles this via chaining — multiple nodes in the same bucket form a linked list (or tree if the chain gets long).

// Simplified collision handling
if (node.next == null) {
    node.next = new Node(hash, key, value, null);
} else {
    // Treeify if chain exceeds TREEIFY_THRESHOLD
}

Failure Scenarios

Trade-Off Table

Code Snippets

Basic Operations

HashMap’s everyday API boils down to four operations: put(), get(), remove(), and containsKey(). put() inserts or overwrites a value and returns whatever was previously mapped to that key — useful when you need to know whether you just clobbered something. get() retrieves by key, remove() deletes, and containsKey() checks existence.

getOrDefault() exists because get() cannot tell you whether a key was absent or whether it mapped to null — both return null. If you call getOrDefault("Eve", 0) and get 0, you know the key was missing; any other value means it was found. This makes it well-suited for counting and accumulator patterns without null-checking boilerplate.

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
System.out.println(ages.get("Alice"));    // 30
System.out.println(ages.getOrDefault("Eve", 0));  // 0
ages.remove("Bob");
System.out.println(ages.containsKey("Bob")); // false
System.out.println(ages.size());            // 1

Custom Key with Proper HashCode

If you use a custom object as a HashMap key, you must override both hashCode() and equals(), and both must depend on the same fields. The rule: objects that are equals() must have the same hashCode(). The reverse is not required, but violating the forward direction is the most common cause of “where did my entry go?” bugs.

hashCode() must only reference immutable fields. If a field used in the hash changes after the object is in the map, the hash changes too, and the entry becomes unfindable — it stays in its original bucket, but the map cannot reach it. Objects.hash() on a stable set of fields is the usual approach; it produces a reasonable distribution without requiring you to write the arithmetic by hand.

A minimal correct implementation looks like this:

class Employee {
    private final int id;
    private final String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee that = (Employee) o;
        return id == that.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);  // Use only immutable field(s)
    }
}

Iterating

HashMap gives you three iteration views. Use entrySet() when you need both the key and value — it avoids a separate hash lookup for each key. Use keySet() when you only need the keys, though for bulk access entrySet() is faster. Use values() when you only need the values.

Do not modify the map while iterating with a for-each loop; calling map.remove(key) from inside the loop throws ConcurrentModificationException because the iterator and the map track modifications independently. Use the iterator’s own remove() method instead, or use a ListIterator.

for (Map.Entry<String, Integer> entry : ages.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

// KeySet iteration
for (String key : ages.keySet()) { }

// Value iteration
for (Integer val : ages.values()) { }

Observability Checklist

• Monitor hashCode() distribution — poor hash functions cause bucket clustering
• Track collision counts via Map.Entry traversal on keys with similar hashes
• Log size() over time to detect unbounded map growth
• Profile for ConcurrentModificationException in high-write scenarios
• Monitor TREEIFY_THRESHOLD conversions — tree nodes are slower than linked-list nodes

Security Notes

• HashMap is not thread-safe; use ConcurrentHashMap for concurrent access
• When using user-supplied keys, a malicious hashCode() implementation could trigger DoS attacks (hash flooding)
• Avoid serializing maps containing sensitive data; use encrypted serialization or secure alternatives
• Map.of() and Collections.unmodifiableMap() create immutable views that prevent accidental mutation

Common Pitfalls / Anti-Patterns

1. Mutable keys: If a key’s hashCode() changes after insertion, the entry becomes unretrievable — the map cannot find it
2. Poor hashCode(): Returning a constant (e.g., return 42) from hashCode() degrades all operations to O(n)
3. Confusing put() return value: put() returns the previous value for the key, or null if none existed — this is indistinguishable from an actual null value; use putIfAbsent() when distinction matters
4. null key: Only one null key is allowed; subsequent put(null, value) overwrites the first
5. Ignoring rehashing: Resizing doubles the bucket count and rehashes every entry — O(n) operation; avoid by estimating capacity upfront

Quick Recap

• HashMap provides O(1) average-case put/get by hashing keys to bucket indices
• Collisions are handled via chaining (linked list or tree for long chains)
• Keys must have stable hashCode() and correct equals() implementations
• null key and null values are supported (single null key)
• Thread-unsafe; use ConcurrentHashMap or Collections.synchronizedMap() for thread safety

Interview Questions

Further Reading

• Oracle HashMap Documentation — Official API specification
• Baeldung: HashMap Internals — Deep dive into hash function, collisions, and treeification
• How HashMap Works in Java — Step-by-step explanation of put/get operations and bucket handling
• Java HashMap: Performance Optimization — Capacity, load factor, and sizing strategies
• HashSet — HashMap’s set counterpart for unique element storage
• TreeMap and TreeSet — sorted key-value pairs using Red-Black trees
• ArrayList — comparing list implementations for different use cases

Conclusion

HashMap is the go-to key-value store in Java, delivering O(1) average-case get and put through hash-based bucketing. The critical contract is that keys provide stable hashCode() and correct equals() implementations — violating either degrades performance unpredictably.

HashMap works best when keys are simple, immutable types (String, Integer, etc.). When using custom objects as keys, treat hashCode() and equals() as a permanent commitment tied to the object’s identity. HashMap is unordered; if insertion order or sorted-key iteration matters, look at TreeMap or LinkedHashMap.

HashSet is the set equivalent of HashMap — it uses the same internal mechanics with a dummy value. For unique-element collections with O(1) lookups, HashSet is the direct counterpart to explore after HashMap.