HashMap Internal Working

Q: Explain how a HashMap works internally.

A: A HashMap stores key-value pairs in an array of buckets. Each bucket is (in Java) typically a linked list or, once a bucket grows beyond a threshold, a balanced tree (red-black tree since Java 8 for buckets with 8+ entries).

Key points to cover:

• hashCode() on the key is computed and then spread/mixed (e.g., XOR with higher bits) to reduce collisions before indexing into the bucket array.
• The bucket index is computed as hash & (capacity - 1), which works because capacity is always a power of two.
• On collision, entries in the same bucket are chained (linked list), and equals() is used to distinguish keys with the same bucket index.
• Load factor (default 0.75) determines when the table resizes (doubles capacity) and rehashes all entries.
• get/put/remove are O(1) average case, O(log n) worst case within a treeified bucket, O(n) worst case if all keys collide and treeification is not applicable (e.g., non-Comparable keys).
• Not thread-safe; ConcurrentHashMap or synchronized wrappers are needed for concurrent access.