HashMap Internal Working

Problem Explain how a HashMap works internally.

Be ready to discuss

• The backing structure: an array of buckets, where each bucket holds a linked list of entries and, past a threshold, a balanced tree.
• Hashing: hashCode() is computed on the key and then spread/mixed (XOR with the high bits) so that poor hash functions don't cluster in the low bits.
• Index computation: hash & (capacity - 1), which is a cheap modulo substitute and works precisely because capacity is always a power of two.
• Collision handling: entries landing in the same bucket are chained, and equals() distinguishes keys that share a bucket index.
• Treeification: in Java 8+, a bucket with 8 or more entries converts to a red-black tree, capping worst-case lookup at O(log n) - requires Comparable keys to be effective.
• Load factor: the default 0.75 balances space against collisions; exceeding it doubles capacity and rehashes every entry.
• Complexity: O(1) average for get/put/remove, O(log n) inside a treeified bucket, degrading to O(n) when every key collides and treeification doesn't apply.
• The hashCode/equals contract: equal objects must have equal hash codes, and mutating a key after insertion makes the entry unreachable.
• Thread safety: HashMap is not synchronised (a concurrent resize could historically spin forever); use ConcurrentHashMap, which locks per bin rather than the whole table.