Какая временная сложность базовых операций в HashMap (Java)?

В HashMap<K, V> средняя временная сложность операций put(), get() и remove() составляет O(1) (амортизированное константное время). В худшем случае (при множественных коллизиях) она может деградировать до O(n) для связанного списка или O(log n) для сбалансированного дерева (Java 8+).

Пример операций:

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 10);   // ~O(1) - вставка
int val = map.get("key"); // ~O(1) - поиск
map.remove("key");    // ~O(1) - удаление

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

1. Хеш-функция (hashCode()): Должна равномерно распределять ключи по бакетам, минимизируя коллизии.
2. Коэффициент загрузки (Load Factor): По умолчанию 0.75. При его превышении происходит rehashing — увеличение размера массива бакетов вдвое.
3. Структура бакета: В Java 8 при большом количестве коллизий в одном бакете (TREEIFY_THRESHOLD = 8) список преобразуется в красно-черное дерево, улучшая худший случай до O(log n).