Всегда ли доступ в HashMap имеет сложность O(1)?

Question

Нет, доступ в HashMap не всегда имеет сложность O(1).При большом количестве коллизий поиск может стать линейным.Начиная с Java 8, в худшем случае используется красно-чёрное дерево.Это ограничивает сложность до O(log n).Таким образом, HashMap защищена от сильной деградации.

YeaHub · Accepted Answer

Хотя HashMap оптимизирована под быстрый доступ, существуют неблагоприятные сценарии, влияющие на асимптотику.Причина деградацииОсновная причина — коллизии:разные ключи дают одинаковый hashCode()элементы попадают в один бакетЕсли бакет представлен списком:поиск требует перебора элементовсложность становится O(n)Защита в Java 8+Начиная с Java 8, применяется оптимизация:при большом числе элементов бакет превращается в деревоиспользуется красно-чёрное деревоРезультат:поиск становится O(log n)стабильная производительность даже при атаках на хешиВажный нюансДерево используется только если:ключи реализуют Comparableразмер бакета превышает порогВыводHashMap не гарантирует O(1) всегда, но современные реализации эффективно ограничивают худший случай.