I've used a hash with around 26 million key/value pairs in the past.
The keys were incrementing digits, so there would have been many cases similar to your 123, 213, 312 scenario, but it didn't appear to cause any problems.

That was Perl-5.6.1 on Solaris.