algorithm - Why does the split-ordered hash table use reversed key?

Question

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?

Answer 1

我认为这是因为对于大小为 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 更接近，并且执行此操作的一种方法是在比较之前进行位反转。

另一种方法是使用哈希值的高位而不是低位 - 实际上将哈希值视为二进制定点数，其二进制点位于最左侧。这对于廉价的 hash(x) = x % p 散列函数没有意义，但他们已经对散列函数做出了强有力的假设。然后，当您增加您注意到的哈希值的位数时，您正在拆分已经按合理顺序排列的值 - 有点像将对象列表编号为 (10) (20) (30)...因此您可以稍后在 (10) 和 (20) 之间插入 (15)。

警告：我已经在无锁论文中看到了足够多的微妙之处，因此我非常警惕与其中任何一个纠缠不清 - 如果我必须使用它，我会更乐意让其他人编写它并让他们对它进行模型检查并进行详尽的测试然后等待一两年让其他人找到错误。