Хеширование в java га sh таблице - PullRequest
Новая
       4

Хеширование в java га sh таблице

3 голосов
/ 04 февраля 2020

Я копался в ха sh таблице исходного кода. И обнаружил, как происходит хеширование: 

int index = (hash & 0x7FFFFFFF) % tab.length;

Я не понимаю, почему побитовое И используется здесь?

если мы превращаем 0x7FFFFFFF в двоичный файл, мы получаем = 111 1111 1111 1111 1111 1111 1111 1111

Как я знаю, побитовое И даст 1 , если первое di git, а второе = 1 Так что, если мы получим некоторый хэш-код объекта, например 2314539, включите его в двоичную систему, а также операции и операции, мы получаем одно и то же: di git:

2314539 = 10 0011 0101 0001 0010 1011 

10 0011 0101 0001 0010 1011
&
 11 1111 1111 1111 1111 1111‬
=
 10 0011 0101 0001 0010 1011

10 0011 0101 0001 0010 1011 = 2314539

Как видите, эта операция не вносит никаких изменений. Так какой тут смысл?

1 Ответ

3 голосов
/ 04 февраля 2020

Давайте начнем со значения остатка (%) в Java. Согласно JLS 15.17.3 :

Операция остатка для операндов, являющихся целыми числами после двоичного числа c продвижение (§5.6.2), дает значение результата так что (a/b)*b+(a%b) равно a.

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

Предположим, что index было вычислено как index = hash % tab.length. Если бы это было так, отрицательное значение для hash (дивиденд) привело бы к отрицательному значению для index.

Но мы будем использовать index для индексации tab, поэтому оно должно составлять l ie между 0 и tab.length.

Вместо фактических карт вычисления hash на неотрицательное число, сначала маскируя бит знака. Затем он выполняет оставшуюся операцию.

Так в чем здесь смысл?

  1. Ваш рабочий пример был для положительного значения hash. & имеет значение для отрицательных значений hash.
  2. Смысл в том, чтобы избежать отрицательного значения hash, дающего отрицательное значение index, которое приведет к ArrayIndexOutOfBoundsException.
...