Ответ
В Java 8 HashMap оптимизирована для случаев коллизий. При достижении определенного порога элементов в одном бакете (по умолчанию 8), LinkedList преобразуется в TreeMap (красно-черное дерево). Это улучшает производительность поиска с O(n) до O(log n). Обратное преобразование (в LinkedList) происходит при уменьшении элементов до 6 (гистерезис для избежания частых преобразований).
Пример порогов:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;Причина: LinkedList эффективен для малых данных, но при росте количества элементов TreeMap обеспечивает лучшую производительность. Условие - ключи должны реализовывать Comparable.