Как будет работать HashMap, если у всех элементов будет одинаковый ключ

HashMap с одинаковыми ключами

Это отличный вопрос для понимания внутреннего устройства HashMap. Если все элементы имеют одинаковый ключ, HashMap будет работать, но с критическим снижением производительности.

Что происходит: Пример

HashMap<String, Integer> map = new HashMap<>();

// Все элементы с одинаковым ключом \"key\"
map.put(\"key\", 1);
map.put(\"key\", 2);
map.put(\"key\", 3);
map.put(\"key\", 4);

System.out.println(map.size());  // 1, не 4!
System.out.println(map.get(\"key\"));  // 4 (последнее значение)

Ключ не дублируется — HashMap хранит только последнее значение для каждого ключа!

Внутреннее устройство HashMap

HashMap использует массив buckets:

buckets[0]: null
buckets[1]: Entry(key1, value1) -> Entry(key2, value2)
buckets[2]: Entry(key3, value3)
...

Ощё зависит от hash function и правило размещения:
index = hash(key) % buckets.length

Проблема: Hash Collision

Сценарий: все ключи имеют одинаковый hash код

public class BadKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 42;  // Все ключи имеют одинаковый hash!
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        BadKey other = (BadKey) obj;
        return value.equals(other.value);
    }
}

HashMap<BadKey, String> map = new HashMap<>();
map.put(new BadKey(\"a\"), \"value1\");
map.put(new BadKey(\"b\"), \"value2\");
map.put(new BadKey(\"c\"), \"value3\");

// Все элементы в ОДНОМ bucket,
// HashMap деградирует до LinkedList

Как HashMap справляется с Hash Collisions

Java 7 и ранее: Chaining (Linked List)

Если несколько ключей имеют одинаковый hash:

buckets[1]: Entry(\"a\", 1)
            ↓
            Entry(\"b\", 2)
            ↓
            Entry(\"c\", 3)
            ↓
            null (конец цепи)

Поиск \"b\":
1. hash(\"b\") → index = 1
2. Идём по цепи: a != b, b == b ✓
3. Находим в O(n) вместо O(1)

Java 8+: Tree Map если много коллизий

// Если в одном bucket > 8 элементов (TREEIFY_THRESHOLD),
// HashMap преобразует LinkedList в Red-Black Tree

// Tree структура даёт O(log n) поиск
// вместо O(n) для LinkedList

Практический пример: Деградация производительности

public class HashCollisionDemo {
    public static void main(String[] args) {
        // Хорошие ключи (хороший hash distribution)
        HashMap<Integer, String> goodMap = new HashMap<>();
        long start = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            goodMap.put(i, \"value\");
        }
        long goodTime = System.nanoTime() - start;
        
        // Плохие ключи (все одинаковый hash)
        HashMap<BadHashKey, String> badMap = new HashMap<>();
        start = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            badMap.put(new BadHashKey(i), \"value\");
        }
        long badTime = System.nanoTime() - start;
        
        System.out.println(\"Good HashMap: \" + goodTime / 1000000.0 + \" ms\");
        System.out.println(\"Bad HashMap: \" + badTime / 1000000.0 + \" ms\");
        System.out.println(\"Slowdown: \" + (badTime / goodTime) + \"x\");
        // Output: Bad HashMap может быть в 100-1000x медленнее!
    }
}

class BadHashKey {
    private int value;
    
    public BadHashKey(int value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return 42;  // Плохо!
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof BadHashKey)) return false;
        return value == ((BadHashKey) obj).value;
    }
}

Вопрос: Если у всех элементов одинаковый КЛЮЧ?

// ❓ Это означает одинаковые значения ключа, не hash
HashMap<String, Integer> map = new HashMap<>();
map.put(\"key\", 1);
map.put(\"key\", 2);  // Перезаписывает значение!
map.put(\"key\", 3);

map.size();  // 1, не 3
map.get(\"key\");  // 3

// HashMap хранит ПО ОДНОМУ значению для каждого ключа
// Повторное put() с тем же ключом перезаписывает значение

Внутренний механизм put()

public V put(K key, V value) {
    int hash = hash(key);
    int index = hash & (length - 1);  // bitwise AND для получения индекса
    
    Node<K, V> node = table[index];
    
    // Проходим по цепи / дереву в bucket'е
    while (node != null) {
        if (node.hash == hash && 
            (node.key == key || key.equals(node.key))) {
            // Ключ найден! Перезаписываем значение
            V oldValue = node.value;
            node.value = value;
            return oldValue;  // Возвращаем старое значение
        }
        node = node.next;
    }
    
    // Ключ не найден - добавляем новую запись
    addNewNode(hash, key, value);
    return null;
}

Правильная реализация ключа

public class GoodKey {
    private String id;
    private int number;
    
    @Override
    public int hashCode() {
        // Хороший hash должен быть:
        // 1. Быстро вычисляться
        // 2. Хорошо распределять элементы
        // 3. Детерминированным (одинаковый объект = одинаковый hash)
        return Objects.hash(id, number);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        GoodKey other = (GoodKey) obj;
        return Objects.equals(id, other.id) && number == other.number;
    }
}

// Использование
HashMap<GoodKey, String> map = new HashMap<>();
map.put(new GoodKey(\"a\", 1), \"value1\");
map.put(new GoodKey(\"b\", 2), \"value2\");
map.put(new GoodKey(\"c\", 3), \"value3\");
map.put(new GoodKey(\"a\", 1), \"updated\");  // Перезаписывает только одно значение

map.size();  // 3 (не 4)

Performance Analysis: Худший случай

Нормальная HashMap:
- get(), put(), remove(): O(1) в среднем

HashMap с коллизиями (все ключи с одинаковым hash):
- С LinkedList: O(n) - линейный поиск
- С Red-Black Tree (Java 8+): O(log n)

Пример с 1,000,000 элементов:
- Нормальная: ~ 0.5 ms
- С коллизиями (LinkedList): ~ 50,000 ms (100,000x медленнее!)
- С коллизиями (Tree): ~ 50 ms (100x медленнее)

Как избежать проблемы

1. Правильно реализуй hashCode() и equals()

// Используй Objects.hash() - правильный hash распределение
@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3);
}

@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (!(obj instanceof MyClass)) return false;
    MyClass other = (MyClass) obj;
    return Objects.equals(field1, other.field1) &&
           Objects.equals(field2, other.field2) &&
           Objects.equals(field3, other.field3);
}

2. Используй immutable ключи

// String, Integer, UUID - хорошие ключи
HashMap<String, String> map = new HashMap<>();
HashMap<Integer, String> map2 = new HashMap<>();
HashMap<UUID, String> map3 = new HashMap<>();

// Mutable ключи - опасны!
HashMap<StringBuilder, String> badMap = new HashMap<>();  // ❌

3. Профилируй при необходимости

# Java Flight Recorder для анализа collisions
java -XX:StartFlightRecording=duration=60s,filename=recording.jfr MyApp

Выводы

1. HashMap допускает дублирование ключей только по хешу, не по значению
2. Если все элементы имеют один ключ, HashMap хранит только 1 элемент
3. Hash collisions приводят к деградации: O(1) → O(n)
4. Java 8+ использует Red-Black Tree при много коллизиях
5. Правильный hashCode() критичен для производительности