Что происходит в HashMap при добавлении новой пары ключ-значение, если ни один из ключей не совпадает с новым ключом по equals

Процесс добавления пары ключ-значение в HashMap

Процесс добавления нового элемента в HashMap — это фундаментальная операция, которая включает несколько этапов поиска, сравнения и потенциального расширения таблицы. Понимание этого процесса критично для эффективной работы с коллекциями.

1. Алгоритм поиска и добавления нового ключа

Когда в HashMap добавляется новая пара ключ-значение и новый ключ не совпадает по equals() ни с одним существующим ключом, происходит следующее:

// Демонстрация процесса
public class HashMapInsertionDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        
        // Шаг 1: Добавить первую пару
        map.put("key1", "value1");
        // HashMap:
        // 1. Вычисляет hashCode("key1")
        // 2. Находит индекс bucket: hash & (capacity - 1)
        // 3. В bucket ничего нет → добавляет Node("key1", "value1")
        
        // Шаг 2: Добавить вторую пару с ДРУГИМ ключом
        map.put("key2", "value2");
        // HashMap:
        // 1. Вычисляет hashCode("key2")
        // 2. Находит индекс bucket
        // 3. Если индекс != индексу "key1" → добавляет в пустой bucket
        // 4. Если индекс == индексу "key1" → добавляет в цепочку
    }
}

2. Вычисление индекса bucketа (hash function)

public class BucketIndexCalculation {
    
    // Первый шаг: вычисление hashCode
    public static int computeHash(String key) {
        return key.hashCode();
    }
    
    // Второй шаг: преобразование в индекс bucketа
    public static int computeIndex(int hash, int capacity) {
        // В HashMap: (hash & (capacity - 1))
        // Это эквивалентно hash % capacity, но быстрее
        return hash & (capacity - 1);
    }
    
    public static void main(String[] args) {
        String key1 = "user1";
        String key2 = "user2";
        
        int hash1 = key1.hashCode();
        int hash2 = key2.hashCode();
        
        // При capacity = 16 (начальная вместимость)
        int capacity = 16;
        int index1 = computeIndex(hash1, capacity);
        int index2 = computeIndex(hash2, capacity);
        
        System.out.println("hash1: " + hash1 + ", index1: " + index1);
        System.out.println("hash2: " + hash2 + ", index2: " + index2);
        
        if (index1 == index2) {
            System.out.println("Коллизия! Оба ключа идут в один bucket");
        } else {
            System.out.println("Разные buckets, оба добавляются без коллизий");
        }
    }
}

3. Случай 1: Ключи идут в разные buckets

Это самый простой и быстрый случай:

public class DifferentBucketsExample {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        
        // Ключи с разными hashCode, идут в разные buckets
        map.put(1, "value1");  // Индекс bucket = 1 % 16 = 1
        map.put(17, "value17"); // Индекс bucket = 17 % 16 = 1... может быть коллизия
        map.put(32, "value32"); // Индекс bucket = 32 % 16 = 0
        
        // Визуализация:
        // Bucket[0] → Node(32, "value32")
        // Bucket[1] → Node(1, "value1") → Node(17, "value17")
        // Bucket[2-15] → null
        
        System.out.println(map.size()); // 3
        System.out.println(map.get(32)); // "value32" — O(1) доступ
    }
}

4. Случай 2: Ключи идут в один bucket (коллизия)

Когда разные ключи имеют одинаковый хеш или одинаковый индекс bucket:

public class CollisionExample {
    static class CustomKey {
        int value;
        
        CustomKey(int value) {
            this.value = value;
        }
        
        @Override
        public int hashCode() {
            return value / 10; // Плохое распределение хешей
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CustomKey that = (CustomKey) o;
            return value == that.value;
        }
        
        @Override
        public String toString() {
            return "CustomKey(" + value + ")";
        }
    }
    
    public static void main(String[] args) {
        Map<CustomKey, String> map = new HashMap<>();
        
        // Оба ключа имеют одинаковый hashCode: 1 / 10 = 0
        CustomKey key1 = new CustomKey(5);   // hashCode = 0
        CustomKey key2 = new CustomKey(8);   // hashCode = 0
        CustomKey key3 = new CustomKey(15);  // hashCode = 1
        
        map.put(key1, "value1");
        // Bucket[0] → Node(key1, "value1")
        
        map.put(key2, "value2");
        // Шаги:
        // 1. hashCode(key2) = 0
        // 2. index = 0 & (16-1) = 0
        // 3. Bucket[0] НЕ пуст → есть Node(key1, "value1")
        // 4. Сравнить key2.equals(key1)? → false (5 != 8)
        // 5. Новый ключ → добавить в цепочку
        // Bucket[0] → Node(key1, "value1") <-- Node(key2, "value2")
        
        map.put(key3, "value3");
        // hashCode(key3) = 1
        // index = 1
        // Bucket[1] пуст → добавить
        // Bucket[1] → Node(key3, "value3")
        
        System.out.println("Map size: " + map.size()); // 3
        System.out.println("Get key1: " + map.get(key1)); // "value1" — O(1)
        System.out.println("Get key2: " + map.get(key2)); // "value2" — O(length_of_chain)
    }
}

5. Внутренняя структура: Node и связанные списки

В Java 8+, HashMap использует связанные списки ИЛИ красно-чёрные деревья при коллизиях:

// До Java 8: просто связный список
// Java 8+: связный список + красно-чёрное дерево (при > 8 элементов в bucket)

public class BucketStructure {
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next; // Связь к следующему элементу в цепочке
        
        Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    
    public static void main(String[] args) {
        // Визуализация структуры при коллизиях:
        /*
        HashMap с capacity = 16:
        
        Bucket[0]:
          Node(hash=0, key="a", value="val_a")
            ↓ next
          Node(hash=0, key="b", value="val_b")
            ↓ next
          Node(hash=0, key="c", value="val_c")
            ↓ next
          null
        
        Bucket[1]:
          Node(hash=17, key="x", value="val_x")
            ↓ next
          null
        
        Bucket[2-15]:
          null
        */
    }
}

6. Процесс добавления нового ключа пошагово

public class DetailedInsertionProcess {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>(16, 0.75f);
        // capacity = 16, loadFactor = 0.75
        // resize сработает при size > 12
        
        // ШАГ 1: Добавить первый элемент
        map.put("apple", 1);
        // 1. key = "apple", value = 1
        // 2. hash = "apple".hashCode() → некое число, например 1234
        // 3. index = 1234 & 15 = 2
        // 4. Bucket[2] пуст
        // 5. Создать новый Node и поместить в Bucket[2]
        // 6. size = 1
        
        // ШАГ 2: Добавить элемент с ключом, не совпадающим по equals()
        map.put("banana", 2);
        // 1. key = "banana", value = 2
        // 2. hash = "banana".hashCode() → другое число, например 5678
        // 3. index = 5678 & 15 = 6
        // 4. Bucket[6] пуст
        // 5. Создать новый Node и поместить в Bucket[6]
        // 6. size = 2
        
        // ШАГ 3: Добавить третий элемент
        map.put("cherry", 3);
        // 1. hash = "cherry".hashCode()
        // 2. index = ... (может быть любой)
        // 3. Если bucket пуст → создать Node
        // 4. size = 3
        // ...
        // После 13 элементов: size >= 12, load factor превышен
        // HashMap РАСШИРИТСЯ (resize): capacity = 32
        
        System.out.println("Final map size: " + map.size());
    }
}

7. Расширение HashMap (Rehashing)

public class HashMapResizing {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>(4, 0.75f);
        // Начальная capacity = 4
        // Resize при size > 3 (4 * 0.75 = 3)
        
        map.put("key1", "val1"); // size = 1
        map.put("key2", "val2"); // size = 2
        map.put("key3", "val3"); // size = 3
        
        System.out.println("Before resize: size=3");
        // Все 3 элемента в buckets capacity=4
        
        map.put("key4", "val4"); // size = 4
        // size (4) > threshold (3) → RESIZE!
        // 1. Создать новый array размером 8 (capacity * 2)
        // 2. Пересчитать индексы для всех элементов
        //    index_new = hash & (8 - 1)
        // 3. Переместить элементы в новые positions
        // 4. Уничтожить старый array
        
        System.out.println("After resize: capacity doubled");
        
        // Временная сложность операции:
        // - Добавление без resize: O(1) в среднем
        // - Добавление с resize: O(n) (пересчёт всех элементов)
    }
}

8. Сравнение equals() при поиске в цепочке

public class EqualsComparisonInChain {
    static class User {
        String id;
        String name;
        
        User(String id, String name) {
            this.id = id;
            this.name = name;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            User user = (User) o;
            return Objects.equals(id, user.id) &&
                   Objects.equals(name, user.name);
        }
    }
    
    public static void main(String[] args) {
        Map<User, String> map = new HashMap<>();
        
        User user1 = new User("1", "Alice");
        User user2 = new User("2", "Bob");
        User user3 = new User("1", "Charlie"); // Другой объект, но id="1"
        
        map.put(user1, "Developer"); // id=1, hashCode одинаковый
        map.put(user2, "Manager");   // id=2, другой hashCode
        
        // При put(user3, ...):
        // 1. hashCode(user3) === hashCode(user1) (оба id=1)
        // 2. index будет одинаковым → коллизия!
        // 3. Bucket[index] содержит Node(user1, "Developer")
        // 4. Проверить: user3.equals(user1)?
        //    id="1" == id="1" → true
        //    name="Charlie" != name="Alice" → false
        // 5. equals вернёт false → это РАЗНЫЕ ключи
        // 6. Добавить user3 в цепочку
        
        map.put(user3, "Analyst");
        
        System.out.println("Map size: " + map.size()); // 3
        System.out.println("Get user1: " + map.get(user1)); // "Developer"
        System.out.println("Get user3: " + map.get(user3)); // "Analyst"
    }
}

Итоговый процесс добавления

При добавлении map.put(key, value) где ключ НОВЫй (не совпадает по equals):

1. Вычислить hashCode(key)
2. Вычислить index = hashCode & (capacity - 1)
3. Получить Bucket[index]

4а. Если Bucket[index] пуст:
    → Создать новый Node
    → Поместить в Bucket[index]
    → size++
    → O(1) операция

4б. Если Bucket[index] не пуст (коллизия):
    → Пройти по цепочке (или дереву) в Bucket[index]
    → Для каждого Node: проверить node.key.equals(key)
    → Если equals() → обновить значение (O(chain_length))
    → Если не найдено → добавить новый Node в начало цепочки (O(1))
    → size++ (если добавили новый ключ)

5. Проверить: size > loadFactor * capacity?
    → Если да: вызвать resize(), пересчитать все индексы
    → Временная сложность resize: O(n)

6. Вернуть старое значение (если был update) или null (если был insert)

Ключевые моменты

• Новый ключ в пустой bucket: O(1) — просто добавить Node
• Новый ключ в занятый bucket: O(chain_length) — пройти по цепочке, затем добавить
• После Java 8: цепочка становится деревом при >8 элементов → O(log n)
• Resize: O(n) × амортизировано за большое количество операций
• Equals() вызывается: только если hashCode совпадает