Побитовое И в Java Hashtable поиска хеша?

Question

Побитовое И в Java Hashtable поиска хеша?

Я заметил, что код хэш-функции как часть java.util.Hashtable#get(K key) делает следующее: int index = (hash & 0x7FFFFFFF) % tab.length;, Эта двоичная операция "и" предназначена только для сброса знака? и поэтому избегайте отрицательного доступа к таблице.

ОБНОВЛЕНИЕ: тот факт, что они 'и' с 0x7FFFFFFF, а не 0xEFFFFFFF, озадачил меня. Почему для знака требуется полный байт, а не один бит?

2

java data-structures hash bit-manipulation hashtable

Источник

user1142881 20 янв '13 в 19:26

2 ответа

Решение

тот факт, что они 'и' с 0x7FFFFFFF, а не 0xEFFFFFFF, озадачил меня. Почему для знака требуется полный байт, а не один бит?

0x7FFFFFFF - это только верхний бит. В двоичном виде это 01111111111111111111111111111111. Где 0xEFFFFFFF равно 11101111111111111111111111111111, поэтому он будет маскировать другой бит.

3

Источник

user57695 20 янв '13 в 21:28

Другие вопросы по тегам java data-structures hash bit-manipulation hashtable

user501557 20 янв '13 в 19:28 2013-01-20 19:28 · Accepted Answer · 2013-01-20 19:28

Да, это правильно. Это сделано для того, чтобы избежать негативного индексирования в базовый массив в хеш-таблице.

Обратите внимание, что в языках с целочисленными типами без знака, таких как C или C++, этого можно избежать, просто используя значения без знака в хэш-функции.

РЕДАКТИРОВАТЬ: учитывая ваш новый вопрос о том, почему 0x7FFFFFF против 0xEFFFFFF - первое из этих чисел - все 1 с верхним битом, установленным в 0. Второе из них не имеет этого свойства; выходит 1110 с последующим лотом 1 с. Следовательно, маскирование с помощью первого сбрасывает 1 бит, а маскирование с помощью второго может этого не делать.

Надеюсь это поможет!