How does HashMap work internally in Java?
Quick answer
A HashMap stores entries in an array of buckets; it computes the key's hash code to choose a bucket, resolves collisions with a linked list that becomes a red-black tree when a bucket grows large, and resizes when the load factor of 0.75 is exceeded.
On put(key, value), HashMap calls key.hashCode(), spreads the bits, and uses hash & (capacity - 1) to pick a bucket index. If the bucket is empty, the entry is stored there. If not, it walks the bucket comparing keys with equals(): a matching key has its value replaced, otherwise the new entry is added to the end. That is why correct hashCode() and equals() implementations are essential for keys.
The default capacity is 16 and the load factor is 0.75, so when more than 12 entries are stored, the table doubles and entries are redistributed. Since Java 8, a bucket with 8 or more entries (when the table has at least 64 buckets) is converted from a linked list to a red-black tree, which keeps worst-case lookup at O(log n) instead of O(n). Average get and put are O(1). HashMap allows one null key, does not guarantee ordering and is not thread-safe.
Key points
- Index = hash of key mapped onto the bucket array
- Collisions: linked list, treeified at 8 entries
- Resizes at load factor 0.75; not thread-safe
Questions interviewers ask next
- What happens if two keys have the same hashCode?
- Why should HashMap keys be immutable?