Relativistic hash tables, part 1: Algorithms

Nice solution.

As for the hash tables, I use in my simple applications (no RCU) solution where AVL roots pointers are stored in hash indexed table instead of list head pointers. The items (expected to be stored in table) include embedded AVL node. The same thing can be done with kernel R-B tree. There is overhead of AVL/R-B node in each item but the tree roots are cheap (single pointer). This solution protects hash to unfortunate or intentional hash collision attacks and worst search complexity is O(log(n)). The size of the table can be automatically scaled to enhance lookup times. The code to test implementation/use example can be found in file ul_hashtabchk.c and implementation in surrounding files

http://sourceforge.net/p/ulan/ulut/ci/master/tree/ulut/

My two cents are not rocket science as relativistic hashes are but idea may be inspiring for somebody for something better.