3 ms·
Cuckoo Hashing
- bdr 18y agoIf this interests you, be sure to read Parts II and III, and the most recent post his blog.
- jws 18y agoMake sure you read the performance results of Pagh and Rodler's 2001 paper before you get too excited. Cuckoo Hashing is good, and it either lends itself to formal reasoning about performance bounds or has attracted extremely capable provers, but it isn't winning in real world performance. Linear hashing probably wins because it makes better use of cache lines in the current architectures where a cache miss equals hundreds of instruction executions.