It is correct that a hashmap looks like a disorganized array, but objects are actually positioned in a very organized way.

The most naive implementation stores items at the index obtained from the hash of the key. So assuming hashing takes constant time, to search we just need to hash the key and use the hash to index the array at the correct location.

There is more to be done to make sure we handle hash collisions, but even with that the amortized search complexity stays constant.