Как влияет на производительность HashMap, если все ключи получают одинаковый хеш-код?

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

Почему так происходит:

• HashMap использует хеш-код для распределения ключей по корзинам (бакетам).
• Если все ключи попадают в один бакет из-за одинакового хеш-кода, то внутри этого бакета ключи хранятся в связном списке или дереве.
• При поиске, вставке или удалении приходится последовательно перебирать все элементы в этом бакете.

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

Пример:

Map<Key, String> map = new HashMap<>() {
    @Override
    public int hashCode() {
        return 42; // Все ключи имеют одинаковый хеш-код
    }
};

// При добавлении большого количества таких ключей производительность падает

Вывод: для хорошей производительности важно, чтобы функция хеширования равномерно распределяла ключи по бакетам.