Re:Robin Hood Hashing should be the default hash table imple...
by jaswilder on Wednesday August 31, 2016 @04:49PM
(#12401354)
The author's thesis has some comparisons to Brent's method. See P51-53 https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf for conclusions.
Re:Robin Hood Hashing should be the default hash table imple...
by kmill on Wednesday August 31, 2016 @05:39PM
(#12401704)
If I remember correctly, Brent's variation considers both the chain of the element being inserted, and the chains for the elements being swapped, and then does a dynamic program to decide exactly what to swap. It sacrifices some insertion efficiency for fewer expected probes for lookups.
* https://books.google.com/books?id=e3wLBAAAQBAJ&pg=PA532#v=on...
* http://maths-people.anu.edu.au/~brent/pd/rpb013.pdf