在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已經很高了。通常我們建議只運行幾千個分區。