"Tens of millions of keys" sounds like a big problem, but it's not a problem that's unique to hashes. If there's the potential of having tens of millions of units of anything (stored in arrays, hashes, whatever), then there's the potential for even more. And suddenly we're talking about a solution that just won't scale well.

It seems that you're getting deep into the database domain. The data set is growing (or will grow) to a point where holding it all in memory at once becomes a bad design decision.

How did we get from 1000 elements in the original post to tens of millions of elements? Just because some article points out the obvious; that holding tens of millions of items in memory at once isn't a good solution, doesn't mean that holding thousands is a problem.