Какая временная сложность основных операций в HashMap и какие факторы на неё влияют?

Основные операции put(), get() и remove() в HashMap имеют амортизированную сложность O(1), но могут деградировать в худших сценариях.

Факторы, влияющие на производительность:

1. Коллизии хешей

   • При совпадении хеш-кодов разные ключи помещаются в один бакет (bucket).
   • В Java 8+ бакет из связного списка преобразуется в красно-чёрное дерево, если коллизий много.
   • Худший случай: O(n) для списка или O(log n) для дерева в одном бакете.

2. Качество реализации hashCode() и equals()

   • Плохая хеш-функция, возвращающая константу, сводит все ключи в один бакет.
   • Пример плохого hashCode:

     @Override
     public int hashCode() {
     return 1; // Катастрофически много коллизий!
     }

3. Ресайзинг (увеличение вместимости)

   • При достижении порога (load factor, по умолчанию 0.75) внутренний массив бакетов увеличивается вдвое.
   • Происходит перехеширование всех элементов — операция стоимостью O(n).

Практический вывод: Для сохранения сложности ~O(1) ключи должны иметь эффективные и равномерно распределяющие hashCode() и equals() методы.