Внутренняя работа HashMap в Java

[ladutsko]

Метод hashCode() класса Object возвращает ссылку на адресс в памяти объекта в целочисленной форме.

Я просто оставлю это здесь — Как работает hashCode() по умолчанию?

[nahmnenik]

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

[turbanoff]

>происходит переход к сбалансированным деревьям
Как именно происходит переход?
Получается ключи в HashMap должны быть Comparable?

[nahmnenik]

Можно почитать implementation notes. Но вообще на сколько я понимаю, если ключи не comparable вызывается метод tieBreakOrder

Само дерево начинает строится тут

[Suvitruf]

На хабре была отличная статья про HashMap.

[nonnenmacher]

OutOfMemoryError, а не Exception в Java.

[poxvuibr]

А можно ссылку на оригинал? А то я что-то не нашёл.

[nahmnenik]

Спасибо, добавил ссылку. Видимо пропала при публикации, она была в заголовке.

[Barrya42]

Изменения в Java 8

Как мы уже значем знаем (исправьте опечатку).в случае возникновения коллизий объект node сохраняется в структуре данных «связанный список» и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).

[Lungo]

На этой картинке ошибка. Для объекта «vishal» поле next уже не будет null

[nahmnenik]

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

[Nialpe]

Понимаю, что взято с оригинала, но там под капотом чуть сложнее все происходит в строке:
index = hashCode(key) & (n-1).
Происходит подмена понятий, правильнее писать:
i = hash(key) & (n-1)
Где в hash(key) — методе HashMap происходит дополнительная магия с key.hashCode().
Пытливые умы могут залезть в исходники HashMap и посмотреть какая именно.

[andrew_k_21_12]

В тексте есть следующее упоминание:

Bucket -ы различаются по ёмкости (свойство capacity). Отношение между bucket и capacity выглядит следующим образом:

capacity = number of buckets * load factor

В то время как в документации к HashMap пишется: "The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created."

Возможно, имелось в виду, что:
макс. количество элементов (entries) в HashMap до перехэширования <= capacity (number of buckets) * load factor
?

[poxvuibr]

Да, это на редкость странное утверждение, что бакеты различаются по ёмкости. Ёмкость это показатель относящийся ко всей HashMap.

Что касается вашего вопроса, то я всегда думал, что capacity это максимальное количество элементов во всей HashMap. То есть сумма элементов во всех бакетах.

Но, согласно документации, capacity это количество бакетов ))). То есть то же самое, что number of buckets. И формула capacity = number of buckets * load factor получается неправильная, если понимать слово capacity в том смысле, в котором оно используется в документации к HashMap

И максимальное количество элементов до перехеширования меньше либо равно capacity * load factor.

А load factor это среднее количество элементов в одном бакете. Ну или процент пустых бакетов при условии, что в заполненных по одному элементу. По умолчания там, кажется 0.75, то есть в среднем в каждом бакете должно быть меньше одного элемента

[andrew_k_21_12]

Что касается вашего вопроса, то capacity это максимальное количество
элементов во всей HashMap. То есть сумма элементов во всех бакетах.

Похоже, что документация к HashMap противоречит этому:

The capacity is the number of buckets in the hash table, ...

Тут не говорится о том, что capacity - сумма элементов во всех бакетах. Тут говорится, что capacity - это количество самих бакетов, про элементы в бакетах нет упоминаний. Вопрос только в терминах: похоже, что то, что вы называете "capacity", в документации - "number of entries".

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

[poxvuibr]

Похоже, что документация к HashMap противоречит этому

Всё вы правильно пишете. Единственное, что я успел за это время перечитать документацию и поправить свой комментарий ))