HashMap in Java: How It Works Internally - Quiz

A HashMap is backed by an array Node<K,V>[] table of buckets. Each slot is either empty (null) or holds the first node of a chain. A Node stores the key hash, the key, the value and a next link to the following node of the same bucket; it also implements Map.Entry, so entry.setValue() changes the value right inside the map.

The table length is always a power of two, 16 by default, and the array is allocated lazily on the first put(). The hash is computed once and stored in the node: a lookup compares the hash numbers first and calls equals() only when they match. Since Java 8 a chain that grows too long becomes a red-black tree of TreeNode objects.

First, hash() spreads the bits: h ^ (h >>> 16), where h = key.hashCode(). Then the index takes the low bits: index = (n - 1) & hash, where n is the table length. A null key has hash 0, so it always lives in bucket 0.

The spreading matters because in a small table the index depends only on a few low bits: without it the Integer keys 0, 65536 and 131072 would all land in bucket 0, while after hash() they go to buckets 0, 1 and 2.

When n is a power of two, n - 1 is all ones in binary (15 = 0b1111), so hash & (n - 1) gives the same result as the remainder, without a division and without trouble from negative hashes. That is why HashMap rounds the capacity up to a power of two and grows only by doubling.

put(key, value) computes hash(key), creates the table through resize() if needed and finds the bucket (n - 1) & hash. If the bucket is empty, a new node goes there. Otherwise the method walks the chain and checks p.hash == hash && (p.key == key || key.equals(p.key)) for every node: if an equal key is found, the value is replaced, the old one is returned and the size stays the same.

If there is no equal key, the new node is appended to the end of the chain (Java 7 inserted it at the head), size grows, and resize() runs when size > threshold. The method returns null.

A collision means different keys land in the same bucket; for example, the strings "Aa" and "BB" share the hash code 2112. Collisions are normal: keys are told apart with equals(), but the more collisions there are, the slower the lookup.

The load factor (0.75 by default) defines the threshold threshold = capacity * loadFactor. As soon as the number of pairs exceeds the threshold, HashMap allocates an array twice as long and moves the nodes into it: for a default map (capacity 16, threshold 12) this happens on the 13th element.

hashCode() is not called again because the hash is stored in each node. The new index depends on a single bit, hash & oldCap: if it is 0, the node stays in bucket j; if it is 1, it moves to j + oldCap.

If the size is known in advance, use HashMap.newHashMap(n) (Java 19) or new HashMap<>((int) Math.ceil(n / 0.75)); new HashMap<>(n) grows before it holds n pairs. The table never shrinks: after remove() and clear() the array keeps its length.

Since Java 8 (JEP 180), a chain that grows too long becomes a red-black tree: when a bucket holds more than 8 nodes (TREEIFY_THRESHOLD = 8) and the table has at least 64 buckets (MIN_TREEIFY_CAPACITY = 64). With a smaller table, HashMap runs resize() instead. If a tree has 6 nodes or fewer after a resize (UNTREEIFY_THRESHOLD = 6), it turns back into a list.

Thanks to tree bins, the worst case of get() and put() is O(log n) instead of O(n) before Java 8; on average the operations are still O(1). Tree nodes are ordered by hash and, for equal hashes, by compareTo() if the keys implement Comparable. Another Java 8 change: new nodes are appended to the tail of the chain and resize keeps their order, whereas in Java 7 a concurrent resize from two threads could turn the list into a cycle.