If you use a fast hash function you still have to look up a hash table, so the memory access is still there. If you use some clever probing strategy you might b

If you use a fast hash function you still have to look up a hash table, so the memory access is still there. If you use some clever probing strategy you might be able to have only 1 cache line access per lookup on average, while most perfect hashing functions, which use the MWHC scheme, do 3 random accesses. However, these 3 random accesses are independent, so the CPU can mostly pipeline them, and the perceived latency is that of a single random access.