The idea: an array of bins, indexed by the hash

A java.util.HashMap is an array called table. Each slot of the array is a bin (or bucket). To store a key, the map turns the key into a number, picks a bin from that number, and puts the entry there. To find the key again, it computes the same number, goes to the same bin, and looks only there. When the keys spread out well, each bin holds zero or one entry, so get and put take constant time on average.

The canvas follows the real JDK code (JDK 8 and later). The top panel shows the hash maths in binary. The strip in the middle is the table, with one small chip per entry. The bottom panel shows the bin that the current call works on.

Add Random picks n different random Integer keys from 0 to 999 and puts them one after another, each with the full step-by-step animation (hash, index, walk, insert, resize). Use the playback bar to skip ahead. Press it a few times and you can watch the table double at 13, 25 and 49 entries.

hashCode(), the spread, and the index

Finding the bin takes three steps:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// in putVal / getNode:
int i = (n - 1) & hash;          // n = table.length, always a power of two
  • hashCode() comes from the key's class. For an Integer it is the value. For a String it is s[0]·31^(n−1) + s[1]·31^(n−2) + … + s[n−1], computed in 32-bit arithmetic, so it can be negative.
  • The spread h ^ (h >>> 16) XORs the top 16 bits into the bottom 16. The index only uses the low bits, so without this step keys that differ only in their high bits would all collide. Demo 5: why h ^ (h >>> 16) puts 65536, 131072, 196608 and 262144. All four have the low 16 bits at zero, so h & 15 is 0 for each of them. After the spread they go to bins 1, 2, 3 and 4.
  • The index is (n − 1) & hash. Because n is a power of two, n − 1 is a mask of ones (15 = 1111), and the AND keeps the low bits. That gives the same result as hash mod n for non-negative numbers, but it is faster and also works for negative hashes.

A null key gets hash 0, so it always lives in bin 0. HashMap allows one null key; Hashtable and ConcurrentHashMap do not (Demo 1).

Bins: a linked list of Node

Each entry is a Node(hash, key, value, next). Keys that land in the same bin form a singly linked list, and a new node is linked at the tail (before JDK 8 it went at the head). A lookup walks the list and, for each node, checks:

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    return e;

The stored hash is compared first. Comparing two ints is cheap, and different hashes prove the keys are different, so equals() is only called when the hashes match. In Demo 2 keys 1, 17 and 33 all have index 1 (17 = 1 0001, 33 = 10 0001). get(33) looks at three nodes but calls equals only once.

A put with a key that is already in the map does not add a node. It replaces the value and returns the old one, and size does not change (Demo 3). remove unlinks the node: the bin's head becomes node.next, or the previous node skips over it (Demo 8).

Load factor, threshold and resize

new HashMap<>() does not allocate the array. The first put calls resize(), which creates 16 bins and sets threshold = 16 × 0.75 = 12. After every new node, if (++size > threshold) resize();. So the 13th entry doubles the table to 32 bins, with threshold 24.

Resizing does not recompute any hash. When n doubles, the mask gains one bit, the bit worth oldCap. So each node of old bin i goes to one of two places:

hash & oldCapnew binname in the JDK code
0i (stays)lo list
1i + oldCaphi list

Both lists keep the old order of the nodes. In Demo 4: resize 16 → 32, key 16 (1 0000) leaves bin 0 for bin 16 and key 17 leaves bin 1 for bin 17. Keys 0 and 1 stay where they are.

The load factor 0.75 is a trade-off: a lower value wastes memory on empty bins, and a higher one makes longer chains. If you know you will store about m entries, new HashMap<>(m * 4 / 3 + 1) (or HashMap.newHashMap(m) since Java 19) avoids all the resizes on the way.

Treeify: when a bin gets too long

A long chain makes lookups in that bin O(k). When a put links the 9th node into a list bin (the list already had TREEIFY_THRESHOLD = 8), putVal calls treeifyBin. That method first checks the table size:

  • If table.length < MIN_TREEIFY_CAPACITY = 64, it calls resize() instead. With a small table, a long bin usually means the table is too small, not that the hash function is bad.
  • Otherwise it turns the bin into a red-black tree of TreeNodes. Nodes are ordered by hash, then by compareTo when both keys are the same Comparable class, and as a last resort by class name and System.identityHashCode (tieBreakOrder). A lookup then costs O(log k).

Demo 6 puts 64, 128, …, 704. All of them have the low six bits at zero, so they stay in bin 0 even at n = 64. The 9th node makes the map resize to 32, the 10th makes it resize to 64, and the 11th finally builds a tree. Afterwards get(640) visits 4 nodes instead of 10.

A tree bin also keeps the next links, in insertion order with the root moved to the front, so iteration and resizing still work like a list. When a resize split or a removal leaves the tree small (UNTREEIFY_THRESHOLD = 6 for a split), the bin goes back to being a plain list. A TreeNode is about twice the size of a Node, so trees are kept for the rare bad case. With a decent hashCode and random keys, a bin with 8 entries has a probability of about 0.00000006 (the JDK source comment works this out).

Writing hashCode and equals for your own keys

HashMap only works if the key class keeps the contract:

  • If a.equals(b), then a.hashCode() == b.hashCode(). Break this rule and two equal keys end up in different bins, so the map can hold "duplicates" and get misses.
  • Equal hash codes for different keys are allowed, but they cost time. "Aa" and "BB" both have hash code 2112, so any strings built from those two blocks collide: "AaAa", "AaBB", "BBAa" and "BBBB" all have the same hash. In Demo 7 the hash check passes for every node, so only equals can tell them apart. Attackers have used this trick to slow down servers that put request parameters into hash maps; tree bins limit the damage to O(log k).
  • Don't change a key after you put it in the map. Its bin was chosen from the old hash code, so with a new hash code get looks in the wrong bin and the entry is lost until it is removed by iteration. Immutable keys such as String, Integer and records avoid this.

Cost of each operation

caseget / put / remove
Keys spread well (the usual case)O(1) on average
Many keys in one list bin (before JDK 8, or table < 64)O(k), with k nodes in the bin
Many keys in one tree bin, keys ComparableO(log k)
A put that triggers a resizeO(n) for that one call, O(1) amortized

What the page leaves out

  • Removing from a tree bin. The JDK's removeTreeNode deletes the node and rebalances the tree in place. When the tree is "too small" (no root.left, no root.right or no root.left.left), it turns the bin back into a list, and the page does the same. Otherwise the page draws the result as a tree rebuilt from the remaining nodes, which can have a different shape.
  • Tables bigger than 64 bins are possible but never needed by the demos. The maximum is 1 << 30.
  • modCount and fail-fast iterators (ConcurrentModificationException), and the keySet/values/entrySet views.
  • putIfAbsent, compute, merge, getOrDefault: the same lookup with different rules for what to write.
  • LinkedHashMap, which adds a doubly linked list through all entries for insertion or access order (the basis of an LRU cache), and ConcurrentHashMap, which locks single bins and resizes in parallel (see How Java's ConcurrentHashMap Works).
  • Integer objects and boxing: the page treats keys as values. In real Java, e.key == key compares references first, and equals handles the rest.

See also Open Hash Tables (chaining in general), Closed Hash Tables (open addressing), Red-Black Trees, LRU Cache and Stack vs Heap in Java.