tenshu

While the analysis in your [1] above is plainly wrong, the algorithm started a long work of (traditional) research. The Ph.d. thesis [1] has a great summary on the impact of your [1].

For Cuckoo hashing, the original publication might be difficult to digest, but the journal version [2] improved it already quite a bit. There is a great explanation with an actual analysis by one of its original inventors available at [3]. It usually takes a long time to find the best way of describing an algorithm and showing why it works.

1. http://wild-inter.net/publications/wild-2016.pdf

2. http://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf

3. http://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf