Внутренняя структура данных HashMap в Java устроена следующим образом: 12

1. Динамический массив ключей. 1 Каждый элемент массива — своеобразная «корзинка», которая хранит связанный список со значением. 1 На каждый ключ приходится только одно значение. 1
2. Хэш ключа для оптимизации доступа. 1 Когда в HashMap добавляют ключ и значение, для ключа сразу высчитывается хэш. 1 По нему определяется позиция в массиве для этой пары. 1
3. Устранение коллизий. 2 Коллизия возникает, когда два объекта имеют одинаковый хэш-код, но разные ключи. 2 В таком случае, HashMap использует связанный список (LinkedList) или более новую структуру данных — красно-чёрное дерево (Red-Black Tree) для хранения значений с одинаковыми индексами. 2
4. Добавление и получение значений. 2 При добавлении значения в HashMap, оно помещается в соответствующий bucket по вычисленному индексу. 2 Если в этом bucket уже есть другие значения, то новое значение добавляется в конец связанного списка или в красно-чёрное дерево. 2 При получении значения по ключу, HashMap сначала вычисляет хэш-код ключа и находит соответствующий индекс. 2 Затем он проходит по связанному списку или красно-чёрному дереву, чтобы найти значение с нужным ключом. 2