NOTE: Nates post below was lost due to the attack. However i still get email notifications.

Leaving out the h^ didn't result in different results. Tuning the primes allows the above input to succeed, but fails with other input. If your math is right for the 3 way collision probability it seems difficult to have efficient memory usage for small maps without a stash. Even with larger maps, getting unlucky means you'll waste huge amount of memory (and time rehashing) without a stash.

Here is a paper about cuckoo hash functions:

http://www.siam.org/proceedings/soda/2009/SODA09_087_dietzfelbingerm.pdfUnfortunately my greek isn't that good.

Could someone translate the essence of this to layman terms? Does this help us choose better hash functions?

This recent paper is neat, it talks about both queuing cuckoo moves and using the queue as a stash:

http://www.wisdom.weizmann.ac.il/~naor/PAPERS/deamortized_cuckoo.pdfIt does not matter how perfect your hash function. If you want high load factors (ie 90%) then you need large table sizes for the statistics. There is no way around it. Its roughly called the birthday paradox, which is that the probability of any 2 people having the same birthday in a room is much higher than people intuitively think.

Example: A table of size 1000 with 100 entries. For just one hash function the probability of at least one collision is 1-P{no collision} equals .99436.

But now lets consider just two entries. The probability that all 3 hash functions all distinct values is 0.997. The probability that all 100 entries all have 3 distinct values for all 3 hash functions however is just 0.741. In other words without even considering pairwise collisions there is a 25% chance that at least one entry returns the same value for 2 of its 3 hash functions.

We could continue. However I implemented, a "perfect hash function" (ie true random, well SecureRandom) and the results for my tests were the same the hash function I used above. I still typically leave the load factor at about 0.75 since puts a bit quicker here.