What they're testing
Whether you're curious about what you use daily. It's also the natural bridge to ConcurrentHashMap.
The short answer~30 seconds
Internally it's a Node[] array. The key's hash is spread (h ^ (h >>> 16)) to mix high bits down, then hash & (n-1) gives the bucket index. Collisions chain into a list; since Java 8 a bucket exceeding 8 entries (with the table at least 64 wide) converts to a red-black tree, taking the worst case from O(n) to O(log n). The table doubles when size passes capacity × 0.75.
The long answer
The spreading step exists because the bucket index uses only the LOW bits of the hash. If your hashCode() differs only in high bits — common with address-based hashes or incrementing ids multiplied by a large constant — every key lands in one bucket. XORing with a 16-bit right shift is the cheapest way to let high bits influence the index.
The tree conversion has a security motive, not only a performance one: before Java 8 an attacker could send thousands of keys deliberately colliding into one bucket, turning every lookup into O(n) — a hash-collision denial of service that hit several web frameworks. The red-black tree closes that, provided the keys are Comparable.
On resizing: it isn't cheap, since every entry must be replaced. If you know the size in advance, constructing with an appropriate capacity (new HashMap<>(expected / 0.75f + 1)) avoids several resizes. It's one of the few micro-tunings whose benefit is actually measurable on large maps.
What they'll ask next
?What happens if you use HashMap from multiple threads?
It breaks unpredictably: lost entries, and in Java 7 a concurrent resize could form a cycle in the linked list, pinning a CPU at 100% forever. Java 8 changed the resize so the cycle is gone, but entries are still lost. Use ConcurrentHashMap.
?How does ConcurrentHashMap lock?
Since Java 8 it dropped segments: reads are lock-free (Node.val is volatile), writes into an empty bucket use CAS, and writes into an occupied bucket synchronise on that bucket's first node. So contention scales with the bucket count rather than a fixed segment count.
These lose points
- Saying
HashMapis always O(1). It's amortised average O(1); worst case is O(log n) since Java 8 and O(n) before. - Describing Java 7's segment locking as how
ConcurrentHashMapworks now.