How does a HashMap find a value in O(1) on average instead of scanning every entry?

It runs the key through hashCode() to get a number, then maps that number to a bucket index (roughly hash modulo capacity, implemented as hash & (capacity - 1)).

It goes straight to that one bucket and only checks the few keys living there, comparing with equals(). Because it jumps directly to a bucket instead of scanning all n entries, average lookup is O(1). It degrades toward O(n) only if most keys pile into the same bucket.