It takes time and effort to do a writeup. And it is easy to procrastinate. That reminds me...
A bit of a plug here. I have a cute nearly-minimal perfect hashing algorithm designed to have good cache-friendly properties. Briefly, it is somewhat similar to hopscotch hashing, only you pre-calculate the positions of the elements to put them into the 'best' spots by solving the assignment problem. Works for up to about 50k elements. It feels like it might have good theoretical properties too, might be even optimal, but it was a while since I've taken the algorithms class.
If anyone is interested to do a writeup and publish clean source code - you'd be welcome.
Yes, it is similar to robin hood. Only you actually place items into optimal positions (by solving the assignment problem on your memory/cache access costs & access probabilities), rather than stochastically swapping items.
I'll put up sample code if somebody would be willing to do a writeup ;)
A bit of a plug here. I have a cute nearly-minimal perfect hashing algorithm designed to have good cache-friendly properties. Briefly, it is somewhat similar to hopscotch hashing, only you pre-calculate the positions of the elements to put them into the 'best' spots by solving the assignment problem. Works for up to about 50k elements. It feels like it might have good theoretical properties too, might be even optimal, but it was a while since I've taken the algorithms class.
If anyone is interested to do a writeup and publish clean source code - you'd be welcome.