Why does the get method of HashMap have a FOR loop?

table[indexFor(hash, table.length)] is the bucket of the HashMap that may contain the key we are looking for (if it is present in the Map).

However, each bucket may contain multiple entries (either different keys having the same hashCode(), or different keys with different hashCode() that still got mapped to the same bucket), so you must iterate over these entries until you find the key you are looking for.

Since the expected number of entries in each bucket should be very small, this loop is still executed in expected O(1) time.

Leave a Comment