I am reading hash table related code in freeradius project, and know the algorithm is from "Split-Ordered Lists: Lock-Free Extensible Hash Tables".I have read the paper, but can't understand why the hash table uses the reversed key to sort the nodes in the list. Could someone can explain it?
I think it is a consequence of the fact that for a table of pointers of size 2^k they use the low k bits of the hash function as the lookup. Suppose k=3 then they look at the hash values mod 8 so 0 and 8 indirect off the 0th slot in the table of points, 1 and 9 indirect of tab[1], and so on. This means that if you insert 0 and 8 they must be very close in the sorted list, because they are both reached via tab[0].
Now they increase the table size and start using hash values mod 16. 0 and 8 now map through tab[0] and tab[8], but if you inserted them with a table of size 8 they will be next door to each other in the sorted list. So you need an order for the sorted list that puts 0 and 8 closer together than 0 and 1, and one way to do this is to bit-reverse before comparing.
An alternative would have been to use the HIGH order bits of the hash value instead of the low - in effect treating the hash value as a binary fixed point number with its binary point at the far left. This wouldn't make sense with a cheap hash(x) = x % p hash function, but they are already making strong assumptions about the hash function. Then when you increase the number of bits of the hash value you take note of, you are splitting values which are already in a sensible order - a bit like numbering a list of objects as (10) (20) (30)... so you can later insert (15) between (10) and (20).
Warning: I have seen sufficient subtleties in lock-free papers that I am very wary about tangling with any of it - if I have to use it I would be happier to let someone else write it and have them model-check it and exhaustively test it and then wait a year or two for other people to find the bugs.