Как устроен HashMap в Java и что происходит при коллизии?

Question

Accepted Answer

HashMap хранит массив бакетов. Хеш ключа определяет индекс бакета. При коллизии элементы лежат в связном списке, а при достаточном числе элементов и размере таблицы бакет превращается в красно черное дерево. Поиск сравнивает hash, затем ключ через equals. Средняя сложность get/put — O 1 , худшая для дерева — O log n .