Collisions

A hash function turns a key into a slot. A collision is two keys that land in the same slot. The map then has to keep more than one entry there, often as a small chain, and a lookup may look at more than one value before it finds the right key.

That is why "O(1) get" is an average, not a promise about every call. One unlucky key can take longer. For the sizes and the hash functions you meet in these exercises, the occasional collision does not change the decision. The map is still the right tool when the alternative is a scan.

You do not implement the hash function in this course. You do need the sentence: average constant time, extra memory, and a collision is the reason the constant is not a guarantee.