Как в HashMap решена проблема с одинаковыми хэшкодами и разными ключами

# HashMap: Решение проблемы коллизий хэшкодов

Что такое коллизия

Коллизия возникает, когда разные объекты дают одинаковый hashCode():

String key1 = "AB";
String key2 = "BA";

// Оба дают одинаковый хэш!
System.out.println(key1.hashCode()); // 2080
System.out.println(key2.hashCode()); // 2080

Вопрос: как HashMap различить эти ключи, если хэши одинаковые?

Решение: Chaining (Цепочки)

HashMap использует метод Chaining (цепочки) для разрешения коллизий.

Архитектура HashMap

HashMap = массив бакетов (buckets)

Бакет 0: null
Бакет 1: Entry → Entry → Entry (цепочка)
Бакет 2: Entry
Бакет 3: null
...
Бакет N: Entry → Entry

Каждый Entry содержит:
- key
- value
- hash
- next (ссылка на следующий Entry)

Как это работает

Добавление (put)

map.put(key1, "value1");

Шаги:
1. hash = key1.hashCode()        // Получаю хеш
2. index = hash & (table.length - 1) // Вычисляю индекс бакета
3. if (table[index] == null) {
       table[index] = new Entry(key1, "value1");
   } else {
       // В бакете уже есть Entry!
       // Ищу нужный key в цепочке
       Entry entry = table[index];
       while (entry != null) {
           if (entry.key.equals(key1)) {
               entry.value = "value1"; // Обновляю
               return;
           }
           entry = entry.next;
       }
       // Не нашёл - добавляю в начало цепочки
       new Entry(key1, "value1", table[index]);
   }

Поиск (get)

String value = map.get(key1);

Шаги:
1. hash = key1.hashCode()
2. index = hash & (table.length - 1)
3. Entry entry = table[index];
   while (entry != null) {
       // Проверяю hash И equals()
       if (entry.hash == hash && entry.key.equals(key1)) {
           return entry.value; // Нашёл!
       }
       entry = entry.next; // Следующий в цепочке
   }
return null; // Не нашёл

Ключевой момент: hash AND equals()

Напомню контрат:

if (obj1.equals(obj2)) {
    obj1.hashCode() == obj2.hashCode()
}

В HashMap:

• Сначала проверяет hashCode()
• Затем проверяет equals()

// Проверяю ОБА условия
if (entry.hash == hash && entry.key.equals(key1)) {
    // Это точно нужный ключ
}

Пример с коллизией

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

String key1 = "AB";
String key2 = "BA";

map.put(key1, "Value1"); // hash = 2080
map.put(key2, "Value2"); // hash = 2080 (коллизия!)

// В памяти:
//
// Бакет [2080 % tableSize]:
//     Entry("BA", "Value2", hash=2080) → Entry("AB", "Value1", hash=2080)
//

System.out.println(map.get(key1)); // "Value1" (нашла через цепочку)
System.out.println(map.get(key2)); // "Value2"
System.out.println(map.size());    // 2 (разные ключи!)

Почему цепочки, а не линейное тестирование

HashMap использует именно цепочки (chaining), а не линейное тестирование (open addressing), потому что:

Преимущества Chaining:

1. Удаление просто: просто удаляю Entry из цепочки
2. Коэффициент загрузки > 1: можно иметь больше элементов чем бакетов
3. Худший случай O(1) в среднем: если распределение хорошее
4. Лучше для равномерного распределения

Линейное тестирование (используется в некоторых других структурах):

1. Сложное удаление (tombstone markers)
2. Кластеризация (clustering problems)
3. Нужно искать свободное место

Визуализация процесса

1. Добавление key1 (hash = 5):
   Бакет 5: [Entry(key1, val1)]

2. Добавление key2 (hash = 5) - коллизия:
   Бакет 5: [Entry(key2, val2)] → [Entry(key1, val1)]

3. Добавление key3 (hash = 5) - ещё одна коллизия:
   Бакет 5: [Entry(key3, val3)] → [Entry(key2, val2)] → [Entry(key1, val1)]

4. Поиск key1:
   index = 5
   Перебираю цепочку:
   - Entry(key3, val3): key3.equals(key1)? НЕТ
   - Entry(key2, val2): key2.equals(key1)? НЕТ  
   - Entry(key1, val1): key1.equals(key1)? ДА - найдена!

Оптимизация в Java 8+: Red-Black Tree

C Java 8 HashMap использует ещё одну оптимизацию:

Если в одной цепочке много элементов (>= 8), она преобразуется в красно-чёрное дерево:

// Java 8+ HashMap реализация упрощённо:

private static final int TREEIFY_THRESHOLD = 8; // Если цепь >= 8

if (chain.size >= TREEIFY_THRESHOLD) {
    // Преобразую цепочку в TreeMap
    // О(log n) вместо O(n)
}

Это защищает от худшего случая: O(n) для цепочек становится O(log n).

Коэффициент загрузки (Load Factor)

HashMap имеет коэффициент загрузки (по умолчанию 0.75):

Если (size / capacity) > 0.75
→ Пересчитываю HashMap на больший размер (resize)

Это контролирует среднюю длину цепочек:

HashMap<String, String> map = new HashMap<>();
// Начальная capacity = 16
// Resize происходит при 16 * 0.75 = 12 элементов

for (int i = 0; i < 12; i++) {
    map.put("key" + i, "value" + i);
}
// После 12-го элемента пересчитается

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

public class HashMapTest {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        
        // Добавляю элементы с известными коллизиями
        // Для Integer хеш это само число
        // Поэтому 1, 17, 33, 49... дадут одинаковый индекс (при capacity=16)
        
        map.put(1, "One");
        map.put(17, "Seventeen"); // Коллизия с 1
        map.put(33, "Thirty-three"); // Коллизия с 1 и 17
        
        System.out.println(map.get(1));  // "One"
        System.out.println(map.get(17)); // "Seventeen"
        System.out.println(map.get(33)); // "Thirty-three"
        System.out.println(map.size());  // 3
    }
}

Важные точки

1. Коллизии неизбежны - это нормально
2. Chaining разрешает коллизии - храню несколько значений в одном бакете
3. Проверяю hash И equals() - оба условия необходимы
4. Средняя сложность O(1) - при хорошем распределении
5. Resize тяжёлая операция - пересчитываю всю таблицу
6. Java 8+ оптимизирует - цепочки становятся деревьями

Формула индекса

int index = hash & (table.length - 1);
// Эквивалентно: hash % table.length
// Но быстрее благодаря битовой операции &

Например:

hash = 2080 (binary: 100000100000)
table.length = 16 (binary: 10000)
table.length - 1 = 15 (binary: 01111)

hash & 15 = 0 (индекс бакета)

Заключение

HashMap решает проблему коллизий хэшкодов через:

1. Chaining - цепочки Entry в одном бакете
2. Сравнение через hash AND equals() - два условия проверки
3. Resize - автоматическое увеличение размера при превышении load factor
4. Tree optimization (Java 8+) - преобразование больших цепочек в деревья

Это обеспечивает среднюю сложность O(1) даже при коллизиях.