Hashes are OK for any number of keys until you run out of memory

That's not actually universally true--large numbers of hash keys trigger pathological behaviour on many versions of glibc. The bug's been fixed, but a lot of those systems are still out there because people are understandably loathe to update such a fundamental part of their system.