middle
Какова оценка временной сложности операций над элементами из HashMap
В среднем случае операции put(), get(), remove() и containsKey() работают за O(1) — константное время. Однако эта сложность не гарантирована и зависит от качества хэш-функции.
| Сценарий | Сложность | Причина |
|---|---|---|
| Средний случай | O(1) | Равномерное распределение по корзинам |
| Много коллизий (список) | O(N) | Линейный поиск в цепочке |
| Много коллизий (дерево, Java 8+) | O(log N) | Красно-черное дерево в корзине |
Начиная с Java 8, когда количество элементов в одной корзине достигает 8 (TREEIFY_THRESHOLD), связный список преобразуется в красно-черное дерево. Это гарантирует, что даже при плохой хэш-функции сложность не хуже O(log N). Обратное преобразование (дерево -> список) происходит при уменьшении до 6 элементов (UNTREEIFY_THRESHOLD).
На собеседовании: скажите O(1) в среднем, O(N) в худшем случае до Java 8, O(log N) в худшем случае с Java 8. Объясните механизм treeification.