Реализация HashMap в Java. Как работает расчет индекса ковша?

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

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

Спасибо

Ответы на вопрос(4)

& 0x7FFFFFFFF)% hashmap_size добивается цели

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

Хеш-карта состоит из сегментов; объекты будут помещены в эти группы на основе идентификатора группы.

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

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

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

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

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

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

Пример:

     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)
 gnreddy04 июн. 2012 г., 13:39
понял, спасибо
 04 июн. 2012 г., 13:29
Very хорошо объяснил. Я впечатлен.
 13 окт. 2013 г., 22:08
Удивительное объяснение
 04 июн. 2012 г., 12:16
Имеет ли это смысл сейчас, или я должен подробнее остановиться на внутренних?
 15 апр. 2015 г., 13:17
Означает ли это, что хеш-память может содержать ключи с разнымиhashCodes если младшие 9 или около того битов совпадают, но старшие биты отличаются?
Решение Вопроса

hashэто вычисляетbucket.

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

 15 сент. 2012 г., 04:07
@LarsH Ну, было бы намного лучше, если бы это было степенное число 2, тогда вы получили бы чистую часть от старших битов. Как это происходит, реализация HashMap начинается с размера 16 и действительно умножается на два при изменении размера. Он все равно работал бы, если бы не степень двойки, но вы хотели бы столько битов "на" насколько это возможно дляlength -1 чтобы сбалансировать разброс между ведрами
 gnreddy04 июн. 2012 г., 11:48
Можете ли вы объяснить этот расчет здесь?
 14 сент. 2012 г., 20:00
Это предполагает, чтоlength такое сила 2?

Ваш ответ на вопрос