Гарантирует ли HashMap заданную сложность при выборке элемента?

HashMap гарантирует среднюю O(1) сложность при выборке элемента (get). В худшем случае, когда все элементы попадают в одну корзину (например, при плохом распределении хеш-кодов), сложность возрастает до O(n), где n - количество элементов. С Java 8 и далее, при большом количестве коллизий в одной корзине, используется древовидная структура (красно-черное дерево) вместо списка, что снижает сложность в худшем случае до O(log n).