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

44

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

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

Спасибо

Ваш Ответ

4   ответа
-1

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

2

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

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

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

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

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

90

Сам хеш рассчитывается по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)
Означает ли это, что хеш-память может содержать ключи с разнымиhashCodes если младшие 9 или около того битов совпадают, но старшие биты отличаются?
понял, спасибо gnreddy
Удивительное объяснение
Имеет ли это смысл сейчас, или я должен подробнее остановиться на внутренних?
Very хорошо объяснил. Я впечатлен.
29

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

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

Можете ли вы объяснить этот расчет здесь? gnreddy
Это предполагает, чтоlength такое сила 2?
@LarsH Ну, было бы намного лучше, если бы это было степенное число 2, тогда вы получили бы чистую часть от старших битов. Как это происходит, реализация HashMap начинается с размера 16 и действительно умножается на два при изменении размера. Он все равно работал бы, если бы не степень двойки, но вы хотели бы столько битов "на" насколько это возможно дляlength -1 чтобы сбалансировать разброс между ведрами

Похожие вопросы