doh! I got it backwards. You are right that hashes are more efficient: http://redis.io/topics/memory-optimization

However, for this particular problem, the docs do say:

Don't use KEYS in your regular application code. If you're looking for a way to find keys in a subset of your keyspace, consider using sets.

I wonder why they don't suggest hashes?