Внутренняя структура данных HashMap в Java основана на массиве бакетов (корзин), каждый из которых содержит связанный список или дерево (начиная с Java 8) элементов с одинаковым хеш-кодом.

Основные компоненты:

Массив бакетов: каждый элемент массива — это либо null, либо ссылка на первый элемент связанного списка или дерева.
Хеш-функция: вычисляет индекс бакета по ключу, используя хеш-код ключа и операцию по модулю размера массива.
Связанные списки: при коллизиях (разных ключах с одинаковым индексом) элементы хранятся в связанном списке.
Красно-черное дерево: если количество элементов в одном бакете превышает порог (обычно 8), связанный список преобразуется в дерево для ускорения поиска.

При вставке HashMap вычисляет индекс бакета, затем добавляет пару ключ-значение в соответствующую структуру. При поиске — сначала вычисляет индекс, затем ищет в списке или дереве.

Это обеспечивает амортизированное время доступа близкое к O(1), но в худшем случае (много коллизий) может быть O(n).

Как организована внутренняя структура данных в реализации HashMap?