Why HashMap?
To find a key in an array you check the elements one by one. With 1 million elements that can mean 1 million checks: O(n).
HashMap computes an index straight from the key and goes to that bucket. As the map grows, the number of checks usually stays the same: O(1) on average.
On the right is the path of get("Leyla"): key, hashCode(), hash, index, bucket.
hashCode: from key to number
String.hashCode() adds up every character with this formula: h = 31 * h + c, where c is the code of the character.
The same String always gives the same number. The result is an int, so overflow can make it negative.
Type another key on the left and watch the calculation change.
spread: mixing in the high bits
index only uses the low bits: the last 4 bits when n = 16. Without spread, keys that differ only in their high bits would land in the same bucket.
So HashMap computes hash = h ^ (h >>> 16): the high 16 bits are mixed into the low 16 bits.
You can see the difference with these Integer keys:
index: the place of the bucket
index = (n - 1) & hash, where n is the capacity, always a power of 2: 16, 32, 64. Even new HashMap<>(20) gets capacity 32.
That makes all the low bits of n - 1 equal to 1 (15 = 1111), so & keeps only the last bits of the hash.
The result is always between 0 and n - 1, even when the hash is negative.
Collision
Different keys can land in the same bucket. "Aa" and "BB" have the same hashCode: 2112.
If the bucket already has a Node, the new Node is linked to the end of the chain through next. Nothing is removed and the array does not change.
Type AaAa and BBBB on the left: they share a hash too.
get and equals
get finds the bucket the same way, then walks the chain. For each Node it checks hash first, then == or equals.
On the right, each Node shows the result of its check.
That is why your own key class needs equals and hashCode together. Without both, a key with the same content may not be found.
put on an existing key
If the key already exists, no new Node is created: the value of the existing Node changes and size stays the same.
put returns the old value. The key itself does not change.
resize
The table is created on the first put. The default capacity is 16 and the load factor is 0.75, so threshold is 12.
When size passes the threshold, on the 13th element, capacity doubles. A new array is created and the Nodes move into it.
hash is not recalculated, because the Node stores it. One new bit is checked: if hash & oldCap is 0 the index stays, otherwise it becomes index + oldCap. Nodes that moved are marked on the right.
When a chain grows: tree
A long chain slows the search. When a chain passes 8 Nodes and capacity is below 64, the table resizes first. At capacity 64 or more, the bucket becomes a red-black tree and search becomes O(log n).
These 11 keys share one hash: capacity became 32 on the 9th key and 64 on the 10th, and the bucket becomes a tree on the 11th.
During a resize, a bucket left with 6 Nodes or fewer goes back to a list. This tool draws the tree as a list and marks the bucket with a TreeNode label.
Traps to know
Order is not guaranteed: elements are visited in bucket order. See the output on the right. If you need insertion order, use LinkedHashMap.
A null key is allowed: its hash is 0 and it lands in bucket 0.
It is not thread-safe: for several threads use ConcurrentHashMap.
Do not change a key: if its hashCode changes after it enters the map, the Node stays in the old bucket and the key cannot be found. That is why immutable keys like String work well.