If the keys are in random order, and the hash table is larger than L3, I bet you can make the hash version faster by looking ahead N items and issuing __builtin_prefetch() on the hash table array. (There are papers on this for hash joins in databases.)