Подтвердить что ты не робот

Внедрение HashMap в Java. Как работает расчет индекса ковша?

Я рассматриваю реализацию HashMap в Java и застрял в одной точке.
Как вычисляется функция indexFor?

static int indexFor(int h, int length) {
   return h & (length-1);
}

Спасибо

Ответ 1

Он не вычисляет хэш, вычисляет ведро.

Выражение h & (length-1) выполняет бит-бит AND на h, используя length-1, который как битовая маска, возвращает только младшие разряды h, тем самым делая сверхбыстрый вариант h % length.

Ответ 2

Сам хэш вычисляется методом hashCode() объекта, который вы пытаетесь сохранить.

То, что вы видите здесь, вычисляет "ведро" для хранения объекта на основе хэша h. В идеале, чтобы избежать столкновений, вы должны иметь такое же количество ведер, как и максимальное достижимое значение h, но это может быть слишком требовательным к памяти. Таким образом, вы обычно имеете меньшее количество ведер с опасностью столкновений.

Если h - это, скажем, 1000, но в вашем базовом массиве всего 512 ведер, вам нужно знать, куда поместить объект. Обычно операции mod на h было бы достаточно, но это слишком медленно. Учитывая внутреннее свойство HashMap, что у базового массива всегда есть число кодов, равное 2^n, инженеры Sun могут использовать идею h & (length-1), она выполняет побитовое И с номером, состоящим из всех 1, практически считывая только младшие разряды n хэша (что то же самое, что и при выполнении h mod 2^n, только намного быстрее).

Пример:

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

Ответ 3

Он вычисляет ведро хэш-карты, где будет храниться запись (пара ключ-значение). Идентификатор ведра hashvalue/buckets length.

Карта хешей состоит из ведер; объекты будут помещены в эти ведра на основе идентификатора bucket.

Любое количество объектов может фактически попадать в одно и то же ведро на основе их значения hash code / buckets length. Это называется "столкновением".

Если многие объекты попадают в одно и то же ведро, в то время как поиск их метода equals() будет вызван для устранения неоднозначности.

Число столкновений косвенно пропорционально длине ковша.