How HashMap works

Q: What are the most common mistakes with How HashMap works?

Using mutable objects as keys. Overriding equals without hashCode. Sharing a HashMap between threads. Relying on iteration order.

A HashMap stores each entry in a bucket chosen by the key's hashCode().

🔎 Unravel this example Prerequisites (2)

Learn these first

Collections: List, Set, Map equals() and hashCode()

At a glance

Mental model

A filing cabinet with numbered drawers.

What happens, in order

1put(k, v) computes k.hashCode(), spreads the bits, picks a bucket (hash & (n - 1)), and either adds a new entry or replaces the value of an equal key (decided by equals)
2The default capacity is 16 and the load factor 0.75: when the map is three-quarters full it doubles the table and redistributes all entries (a "rehash")new HashMap<>(expected / 0.75 + 1) avoids that.
3Iteration order of HashMap is arbitrary and may change when the map growsLinkedHashMap keeps insertion order (or access order, which makes an LRU cache with removeEldestEntry); TreeMap keeps sorted order.
4HashMap allows one null key and null values; Hashtable and ConcurrentHashMap do not

Remember

Keys must be effectively immutable
A hashCode that returns the same value for many keys degrades a bucket into a long chain
The table is an array of Node<K,V> (hash, key, value, next)

Watch out

Using mutable objects as keysOverriding equals without hashCodeSharing a HashMap between threadsRelying on iteration order

Example (highlighted lines explain it)

import java.util.*;public class Cache<K, V> extends LinkedHashMap<K, V> {  private final int max;  public Cache(int max) { super(16, 0.75f, true); this.max = max; }  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > max; }  static Map<String, Integer> counts(List<String> words) {    Map<String, Integer> m = new HashMap<>();    for (String w : words) m.put(w, m.getOrDefault(w, 0) + 1);    return m;  }}

line 2 uses LinkedHashMap, the core of How HashMap works
line 7 uses HashMap, the core of How HashMap works

Read the full explanation (about 2 min)

A HashMap stores each entry in a bucket chosen by the key's hashCode(). Lookup is O(1) on average because it jumps straight to one bucket and compares only the few keys inside it.

A mental model

A filing cabinet with numbered drawers. The key is turned into a drawer number (hash), you open that drawer and look through the handful of folders in it, instead of searching the whole office.

How it works

put(k, v) computes k.hashCode(), spreads the bits, picks a bucket (hash & (n - 1)), and either adds a new entry or replaces the value of an equal key (decided by equals).

The default capacity is 16 and the load factor 0.75: when the map is three-quarters full it doubles the table and redistributes all entries (a "rehash"). new HashMap<>(expected / 0.75 + 1) avoids that.

Iteration order of HashMap is arbitrary and may change when the map grows. LinkedHashMap keeps insertion order (or access order, which makes an LRU cache with removeEldestEntry); TreeMap keeps sorted order.

HashMap allows one null key and null values; Hashtable and ConcurrentHashMap do not.

Going deeper

Keys must be effectively immutable. If a key's fields change after insertion its hash changes and the entry is lost in the wrong bucket, still counted in size() but never found.

A hashCode that returns the same value for many keys degrades a bucket into a long chain. Since Java 8 a long chain (8 or more entries, table at least 64) becomes a balanced tree, giving O(log n) instead of O(n), but you still want a good hash.

HashMap is not thread safe: concurrent writes can lose entries or, in old versions, loop forever. Use ConcurrentHashMap.

Under the hood

The table is an array of Node<K,V> (hash, key, value, next). The hash is h ^ (h >>> 16) so the high bits take part in choosing the bucket. HashSet is just a HashMap whose values are a dummy object.

Common mistakes

Using mutable objects as keys.
Overriding equals without hashCode.
Sharing a HashMap between threads.
Relying on iteration order.

How Unravel recognises it

When you paste code, Unravel looks for these signs of how hashmap works. Spotting them yourself is a good habit when you read unfamiliar code:

Types: Hashtable IdentityHashMap
Created with new: HashMap LinkedHashMap Hashtable IdentityHashMap

Part of a learning path

Collections in depth · previous: ArrayList vs LinkedList · next: Map idioms: merge, compute, entrySet

Related concepts

equals() and hashCode()Java language Map idioms: merge, compute, entrySetJava language TreeMap, TreeSet and sorted collectionsJava language Concurrent collectionsConcurrency

Frequently asked questions

What is How HashMap works?

A HashMap stores each entry in a bucket chosen by the key's hashCode(). Lookup is O(1) on average because it jumps straight to one bucket and compares only the few keys inside it.

What are the most common mistakes with How HashMap works?

Using mutable objects as keys. Overriding equals without hashCode. Sharing a HashMap between threads. Relying on iteration order.

How can I see How HashMap works in real code?

Paste your own Java into Unravel and it will point out where how hashmap works appears, explain how it works at the detail level you choose, and draw the flow of the code around it.