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

Scenario	Cause	Result
NullPointerException	null key and key-based operations	Runtime crash
ConcurrentModificationException	Modifying map while iterating	Runtime crash
Performance degradation	Many hash collisions (poor hashCode)	O(n) instead of O(1) per operation
OutOfMemoryError	Unbounded growth with collisions	HashMap never shrinks

Trade-Off Table

Aspect	HashMap	TreeMap	LinkedHashMap
Ordering	None	Sorted by key (Red-Black)	Insertion or access order
Get/Put complexity	O(1) avg, O(n) worst	O(log n)	O(1) avg
null key allowed	Yes (one)	No	Yes (one)
Thread safety	None	None	None
Memory overhead	Lower	Higher (tree structure)	Higher (linked list)

Code Snippets

Basic Operations

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

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

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

::: info The following .qa-card components contain typical interview questions you may encounter. Reviewing these will help reinforce key concepts. :::

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

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.