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

В идеальном случае доступ к элементу в HashMap действительно O(1) благодаря хеш-функции. Однако есть нюансы:

1. Коллизии - если разные ключи дают одинаковый хеш, элементы хранятся в связанном списке/дереве (Java 8+), что может ухудшить сложность до O(n) в худшем случае.

2. Рехеширование - при заполнении таблицы (по умолчанию 75%) происходит увеличение размера и перераспределение элементов, что временно влияет на производительность.

Пример плохого хеширования:

class BadKey {
    @Override
    public int hashCode() { return 42; } // Все ключи в один бакет
}
HashMap<BadKey, String> map = new HashMap<>();
// Все операции будут O(n)

Для поддержания O(1) важно:

• Хорошая хеш-функция (String, Integer уже имеют)
• Разумный load factor
• Непереопределяемые ключи (immutable)