При коллизии в
HashMap<> элементы хранятся в односвязном списке в баккете. Поиск в списке составляет сложность O(n) - это худшее время поиска.По достижении количества 8 элементов в 1 баккете, наш список перестраивается в дерево, что дает нам стабильное время поиска элемента -
O(log(n)), что является лучше, чем O(n). Мы ведь не знаем, сколько у нас элементов.