Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()?

HashMap с одинаковыми hashCode всех ключей

Да, HashMap будет работать корректно даже если все ключи имеют одинаковый hashCode. Однако производительность деградирует до O(n) вместо ожидаемого O(1).

Практический пример

public class BadKey {
    private String value;
    
    public BadKey(String value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return 42;  // Все объекты возвращают одинаковый хеш
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        BadKey other = (BadKey) obj;
        return value.equals(other.value);
    }
}

// Использование:
HashMap<BadKey, String> map = new HashMap<>();
map.put(new BadKey("key1"), "value1");
map.put(new BadKey("key2"), "value2");
map.put(new BadKey("key3"), "value3");

String result = map.get(new BadKey("key2"));  // Работает, но медленнее
System.out.println(result);  // value2

Внутренняя структура

Внутри HashMap все элементы попадут в одну ячейку массива и образуют длинную цепочку (linked list):

// Внутренняя структура HashMap:
// table[0]: Node -> Node -> Node -> Node
// table[1]: null
// table[2]: null
// ...
// table[15]: null

// При поиске HashMap проходит всю цепочку:
public V get(Object key) {
    int hash = hash(key.hashCode());
    Node<K,V> e = table[hash & (capacity - 1)];  // Все попадают в один индекс
    
    // Проходит по всей цепочке O(n)
    for (; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key)) {
            return e.value;
        }
    }
    return null;
}

Почему это работает?

1. hashCode возвращает только индекс в массиве, не определяет уникальность
2. Реальное сравнение ключей проводится через equals()
3. Коллизии разрешаются через цепочки — элементы хранятся в linked list
4. HashMap проходит по цепочке и находит нужный элемент по equals()

// Поиск в цепочке:
for (; e != null; e = e.next) {
    if (e.hash == hash &&           // Сначала сравнивает хеш
        key.equals(e.key)) {         // Потом сравнивает ключ через equals()
        return e.value;
    }
}

Производительность

// Тест производительности
HashMap<BadKey, Integer> map = new HashMap<>();

// Добавляем 100k элементов
for (int i = 0; i < 100_000; i++) {
    map.put(new BadKey("key" + i), i);
}

// Поиск будет медленным
long start = System.nanoTime();
for (int i = 0; i < 10_000; i++) {
    map.get(new BadKey("key" + i));
}
long duration = System.nanoTime() - start;
System.out.println("Время: " + duration / 1_000_000 + "ms");

// С нормальными хешами это займет ~5ms
// С одинаковыми хешами: ~500ms или больше

Java 8+ оптимизация

Начиная с Java 8, HashMap использует красно-чёрное дерево вместо linked list при слишком длинной цепочке:

// Когда цепочка достигает длины TREEIFY_THRESHOLD (8),
// LinkedList преобразуется в TreeMap

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

// Это улучшает производительность с O(n) до O(log n)
// Но все же медленнее чем O(1)

Правильная реализация hashCode

public class GoodKey {
    private String value;
    private int id;
    
    @Override
    public int hashCode() {
        // Используй все значимые поля
        final int prime = 31;
        int result = 1;
        result = prime * result + id;
        result = prime * result + value.hashCode();
        return result;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        GoodKey other = (GoodKey) obj;
        return id == other.id && value.equals(other.value);
    }
}

Вывод

1. HashMap будет работать с одинаковыми hashCode
2. Производительность деградирует до O(n) вместо O(1)
3. Java 8+ использует TreeMap при длинных цепочках, улучшая до O(log n)
4. Никогда не пишите hashCode() возвращающий константу без очень веской причины
5. Плохой hashCode приводит к DoS атакам при обработке ненадежных данных