hash - 在伏地魔中，为什么哈希环只延伸到 2^31-1？

Question

在项目 voldemort 设计页面上：

据说哈希环覆盖区间[0, 2^31-1]。

现在，区间 [0, 2^31-1] 代表 2^31 个总数，而最大的数 2^31-1 只是 31 位全部设置为 1。（为了说服自己，请考虑 2^3- 1. 2^3=8 是 0x1000。2^3-1=7 是 0x111)。

因此，如果使用普通的 32 位地址字来存储该值，则您有 1 位空闲。

因此，为什么 2^31-1 是上限？额外的位是否用于某种系统簿记？

（例如，1 个额外的位将为安全地添加两个有效的散列地址提供空间而不会溢出）。

最后，这个选择是voldemort特有的，还是在其他一致的哈希方案中看到的？

score 1 · Accepted Answer

我认为您只有 1 位空闲而不是 2。-1 说明了它以数字“0”而不是 1 开头的事实（循环从 0 计数到 count-1 的原因相同）。我猜他们使用 2^31 而不是 2^32 的原因是他们使用的是有符号整数，因此最后一位是符号位，因此不可用。

编辑：从您链接的页面：

为了可视化一致的散列方法，我们可以将可能的整数散列值视为一个从 0 开始并围绕 2^31-1 循环的环。

它指定了一个整数，所以除非你想要负哈希值，否则你会被 2^31 而不是 2^32 困住。

score 0 · Accepted Answer

回答一个问题有点晚了，只有 4 年 :)

原因是 Voldemort 是用 Java 编写的，而 Java 没有 unsigned int。2^31 对于分区来说已经很高了。通常，我们建议仅使用几千个分区运行。

2 回答 2