Всегда ли у поиска элемента по ключу в HashMap сложность O(1)

Нет, сложность O(1) - это средний случай. В худшем случае (при коллизиях) сложность может деградировать до O(n), если все ключи попадают в один бакет.

Основные причины:

1. Плохая реализация hashCode(), приводящая к частым коллизиям
2. Малое количество бакетов при создании HashMap

Пример плохого hashCode():

class BadKey {
    @Override
    public int hashCode() {
        return 1; // Все ключи в одном бакете
    }
}

С Java 8 при большом количестве коллизий в бакете (TREEIFY_THRESHOLD = 8) список преобразуется в красно-черное дерево, что улучшает худший случай до O(log n).