Ответ
В худшем случае сложность поиска в HashMap деградирует до O(n), если все элементы имеют одинаковый hashCode. Это происходит из-за коллизий - все элементы попадают в одну корзину (bucket), превращая HashMap в связный список.
// Плохая реализация hashCode
override fun hashCode(): Int = 1 // Все объекты будут в одном bucket
val map = HashMap<Key, String>()
// Все операции (put/get) будут O(n)Однако в Java 8+ при большом количестве коллизий (TREEIFY_THRESHOLD = 8) список преобразуется в красно-черное дерево, что улучшает худший случай до O(log n).