Walk through how HashMap stores and finds an entry, and why a bad hashCode degrades it to O(n).

HashMap computes the key's hashCode, spreads the bits to reduce clustering, and maps it to a bucket index; lookup then scans that bucket comparing keys with equals.

If many keys collide into one bucket, that bucket becomes a long chain and operations degrade toward O(n) because you're doing linear search. Java 8 mitigates pathological collisions by converting a bucket to a balanced tree once it exceeds a threshold, giving O(log n) per bucket, but this only helps if keys are at least Comparable; the real fix is a well-distributed hashCode.