Comment by utopcell

If we were talking about the worst lookups, then even in the RAM model they would become slower as the map grows.

To be more specific, if you place n balls into n bins, on average each bin will contain 1 ball, but the largest one, with high probability, will contain O(log(n)/log(log(n))) of them.