Actually, we don’t have unlimited memory in the real world. If a rehash triggers memory allocation and it fails, unexpected behavior occurs—boom! The validator gets punished, which is unacceptable. If hash maps were truly safe with just a simple check (even at the cost of performance), everyone would use them instead of tree maps. But it’s not just about collisions or rehashing—you have to consider all aspects!

For cases where you’re dealing with an NP-hard problem and the choice of method doesn’t impact correctness—only performance—hash maps can be useful. But in critical systems, where failure comes at a high cost, relying on them is a bad idea. The risks outweigh the benefits when stability and predictability are paramount.

I know if we talk about this we should have some assumptions that was not available in the problem description, they also said it should be consistent with original solution and ...

Thanks for the points.