在Voldemort中，为什么散列环只扩展到2^31-1？

Question

在项目设计伏地魔页：

http://project-voldemort.com/design.php

据说，散列环覆盖所述区间[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特有的选择，还是在其他一致的哈希方案中看到？

Answer 1

我认为你只有1位空闲不是2. -1说明了它以数字'0'而不是1开始（同样的原因循环从0到count-1）。我猜想他们使用2^31而不是2^32的原因是他们使用了一个有符号的整数，所以最后一位是符号位，所以不可用。

编辑： 从页面链接你：

形象化的一致性哈希方法，我们可以看到的可能 整数哈希值环以0开头，并在周围盘旋到 2^31-1 。

它指定一个整数所以，除非你要负的哈希值你坚持2^31，而不是2^32。

Answer 2

回答问题有点晚，只是4年:)

原因是伏地魔用Java编写的Java没有无符号整型。对于分区，2^31已经很高了。通常我们建议只运行几千个分区。