Какое худшее время работы метода get(key) для ключа, которого нет в HashMap

Худшее время — O(N) (до Java 8) или O(log N) (с Java 8). Это случай, когда все элементы попали в одну корзину из-за коллизий hashCode.

До Java 8: корзина содержит связный список, и для определения отсутствия ключа нужно перебрать все N элементов, вызывая equals() для каждого. Только убедившись, что ни один не совпал, метод вернет null.

С Java 8: при 8+ элементах в корзине список преобразуется в красно-черное дерево, и поиск по дереву выполняется за O(log N). Это гарантирует, что даже при плохой хэш-функции деградация ограничена.

На собеседовании: ответ — O(N) до Java 8, O(log N) с Java 8. Объясните через treeification.