我正在阅读freeradius项目中哈希表相关代码，并且知道该算法来自"分序列表:无锁可扩展哈希表"。我读过这篇论文，但不明白为什么哈希表使用反向键对列表中的节点进行排序。有人能解释一下吗?
我认为这是一个事实的结果，对于一个大小为2^k的指针表，他们使用哈希函数的低k位作为查找。假设k=3，然后他们查看哈希值mod 8，所以0和8间接地从点表的第0个槽中取出，1和9间接地从tab[1]取出，以此类推。这意味着如果你插入0和8，它们在排序列表中必须非常接近，因为它们都是通过tab[0]到达的。
现在他们增加表的大小，并开始使用哈希值mod 16。0和8现在通过tab[0]和tab[8]映射，但是如果你用大小为8的表插入它们，它们将在排序列表中彼此相邻。所以你需要一个排序列表，让0和8比0和1更接近，一种方法是在比较之前进行位反转。
另一种选择是使用哈希值的HIGH位而不是low位——实际上是将哈希值视为二进制固定点数，其二进制点位于最左边。对于一个便宜的hash(x) = x % p哈希函数来说，这是没有意义的，但是他们已经对哈希函数做出了很强的假设。然后，当你增加你注意到的哈希值的位数时，你正在分割已经按合理顺序排列的值-有点像将对象列表编号为(10)(20)(30)…因此，稍后可以在(10)和(20)之间插入(15)。
警告:我已经在无锁文件中看到了足够多的微妙之处，我非常谨慎地避免与它纠缠在一起——如果我必须使用它，我更愿意让别人来写它，让他们对它进行模型检查和详尽的测试，然后等上一两年，让其他人来发现错误。