Сообщить об ошибкеМетод цепочек
При возникновении коллизий (когда два ключа возвращают одинаковый бакет-индекс), HashMap использует метод цепочек. Элементы одного бакета связываются между собой ссылками next.
Преобразование в дерево
Начиная с Java 8, если длина связного списка в бакете превышает 8 элементов, он преобразуется в сбалансированное красно-черное дерево. Обратное преобразование происходит при уменьшении размера бакета до 6 элементов.
Практические задания
Проверьте себя: сформулируйте ответ вслух или выполните задание до того, как откроете подсказку.
Спровоцировать коллизии осознанно
Напишите класс-ключ, у которого hashCode() всегда возвращает одно и то же число, а equals() сравнивает поле id.
Положите в HashMap 10 таких ключей и объясните, что произойдёт со структурой бакета и со сложностью операции get.
Показать подсказку
Все ключи попадут в один бакет: сначала цепочка, после порога — дерево.