В 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. (Чтобы убедиться в этом, рассмотрим ^ 3-1. 2 ^ 3 = 8 и равно 0x1000. 2 ^ 3-1 = 7 и равно 0x111).

Таким образом, если для хранения значения используется обычное 32-разрядное адресное слово, у вас есть 1 свободный бит.

Таким образом, почему верхний предел равен 2 ^ 31-1? Используется ли этот дополнительный бит для какой-либо системы учета?

(например, 1 дополнительный бит предоставил бы место для безопасного добавления двух допустимых хеш-адресов без переполнения).

И, наконец, этот выбор специфичен для Волдеморта или он встречается в других последовательных схемах хеширования?

Answer 1

Я думаю, что у вас есть только 1 свободный бит, а не 2. Значение -1 объясняет тот факт, что оно начинается с числа «0» вместо 1 (та же самая причина повторяет счет от 0 до 1). Я думаю, причина, по которой они используют 2 ^ 31 вместо 2 ^ 32, заключается в том, что они используют целое число со знаком, так что последний бит является знаковым битом и поэтому не может использоваться.

Edit: Со страницы, на которую вы ссылаетесь:

Чтобы визуализировать метод последовательного хеширования, мы можем увидеть возможные целочисленные значения хеш-функции в виде кольца, начинающегося с 0 и вращающегося вокруг 2 ^ 31-1.

Указывает целое число, поэтому, если вы не хотите, чтобы отрицательные значения хеша застряли с 2 ^ 31 вместо 2 ^ 32.

Answer 2

Отвечая на вопрос немного поздно, всего на 4 года:)

Причина в том, что Волдеморт написан на Java, а в Java нет беззнаковых int. 2 ^ 31 уже очень высока для перегородок. Обычно мы рекомендуем работать с несколькими тысячами разделов.