В чем заключается наихудший сценарий использования HashMap?

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

• Ключи имеют плохую реализацию метода hashCode(), приводящую к одинаковым или близким значениям.
• Используются ключи с одинаковыми хешами, например, специально подобранные.

В таком случае все элементы попадают в одну корзину, и поиск, вставка или удаление требуют перебора всех элементов в этой корзине.

Пример плохого сценария:

class BadKey {
    @Override
    public int hashCode() {
        return 42; // Все ключи имеют одинаковый хеш
    }

    @Override
    public boolean equals(Object obj) {
        return this == obj;
    }
}

HashMap<BadKey, String> map = new HashMap<>();
// При добавлении множества таких ключей производительность резко падает

Поэтому важно обеспечивать хорошее распределение хешей и использовать качественные реализации hashCode().