Какова временная сложность получения элемента из HashMap, если внутри используется красно-черное дерево?

В Java начиная с версии 8, если в бакете HashMap слишком много коллизий (более 8 элементов), список внутри бакета преобразуется в красно-черное дерево для улучшения производительности.

Временная сложность получения элемента из HashMap в этом случае меняется с амортизированного O(1) (при использовании связного списка) на O(log n), где n — количество элементов в конкретном бакете (то есть глубина дерева).

Таким образом, при использовании красно-черного дерева внутри бакета, поиск элемента выполняется за O(log n).