Когда возникает коллизия?

Коллизии в Java: когда и почему они возникают

Коллизия (hash collision) — это ситуация, когда два разных объекта имеют одинаковый хеш-код. Это одна из ключевых проблем при работе с хеш-таблицами (HashMap, HashSet) в Java.

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

Для понимания коллизий нужно разобраться с архитектурой HashMap:

public class HashMapBasics {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // При добавлении элемента:
        map.put("apple", 1);
        // 1. Java вычисляет hash code объекта: "apple".hashCode()
        // 2. Преобразует его в индекс: hash & (capacity - 1)
        // 3. Добавляет элемент в массив на этот индекс
    }
}

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

indexes:  [0] [1] [2] [3] [4] ...
values:   [X] [Y] [Z] ... [?]
           ↓   ↓   ↓
          bucket

Когда возникают коллизии

1. Разные объекты с одинаковым hashCode()

// Пример с Integer
Integer a = new Integer(1);
Integer b = new Integer(1);

System.out.println(a.hashCode()); // 1
System.out.println(b.hashCode()); // 1
System.out.println(a == b);       // false
System.out.println(a.equals(b));  // true

// a и b имеют одинаковый hash code, но это разные объекты
Map<Integer, String> map = new HashMap<>();
map.put(a, "first");
map.put(b, "second");  // Коллизия!

2. Плохо реализованный hashCode()

public class BadHashExample {
    private String name;
    
    // ❌ Плохая реализация: все объекты имеют одинаковый hash
    @Override
    public int hashCode() {
        return 42; // Константа!
    }
    
    @Override
    public boolean equals(Object obj) {
        // ...
    }
}

// Использование
BadHashExample obj1 = new BadHashExample();
BadHashExample obj2 = new BadHashExample();

Map<BadHashExample, String> map = new HashMap<>();
map.put(obj1, "first");
map.put(obj2, "second");  // Гарантированная коллизия!

3. Статистическая вероятность

Даже при хорошей функции хеширования коллизии возникают с вероятностью (парадокс дней рождения):

public class CollisionProbability {
    public static void main(String[] args) {
        // С 23 случайными числами вероятность коллизии ~ 50%
        // С 70 числами ~ 99.9%
        
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < 1000; i++) {
            int hash = (int) (Math.random() * Integer.MAX_VALUE);
            if (seen.contains(hash)) {
                System.out.println("Коллизия найдена на итерации " + i);
                break;
            }
            seen.add(hash);
        }
    }
}

Как HashMap обрабатывает коллизии

Метод 1: Chaining (Цепочки)

В Java 7 и ранее использовался метод linked list chaining:

// Внутренняя структура (упрощенно)
Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Node<K,V> next;  // Следующий элемент в цепи
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

При коллизии элементы хранятся в цепочке (linked list):

index [2]:
  ┌─────────────────┐
  │ Node ("apple") │ ──→ ┌─────────────────┐
  │ hash: 95321    │    │ Node ("pears")  │ ──→ null
  │ value: 5       │    │ hash: 95321     │
  └─────────────────┘    │ value: 3        │
                         └─────────────────┘

Метод 2: Balanced Tree (Java 8+)

Начиная с Java 8, при большом количестве коллизий (threshold = 8) цепочка преобразуется в Red-Black Tree:

// Когда в одной ячейке накопится 8+ элементов,
// HashMap преобразует цепочку в TreeMap
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

Почему это важно?

• Поиск в цепочке: O(n) в худшем случае
• Поиск в tree: O(log n) даже при коллизиях

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

public class Person {
    private String name;
    private int age;
    
    // ✅ Хорошая реализация
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        
        Person other = (Person) obj;
        return age == other.age && 
               Objects.equals(name, other.name);
    }
}

// Правила:
// 1. Если a.equals(b) → a.hashCode() == b.hashCode()
// 2. Если a.hashCode() != b.hashCode() → !a.equals(b)
// 3. Если a.hashCode() == b.hashCode() → a.equals(b) может быть true или false

Практические последствия коллизий

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

public class CollisionPerformance {
    public static void main(String[] args) {
        // Сценарий 1: Хороший hash (без коллизий)
        long start1 = System.nanoTime();
        Map<Integer, String> goodMap = new HashMap<>();
        for (int i = 0; i < 100_000; i++) {
            goodMap.put(i, "value");
        }
        long duration1 = System.nanoTime() - start1;
        
        // Сценарий 2: Плохой hash (все коллизии)
        long start2 = System.nanoTime();
        Map<BadHash, String> badMap = new HashMap<>();
        for (int i = 0; i < 100_000; i++) {
            badMap.put(new BadHash(i), "value");
        }
        long duration2 = System.nanoTime() - start2;
        
        System.out.println("Good hash: " + duration1);
        System.out.println("Bad hash: " + duration2);
        // Bad hash может быть в 10+ раз медленнее
    }
}

Защита от DoS атак через коллизии

// Java использует рандомизированный hash seed с версии 7
public class HashSecurity {
    // Сложно предсказать hash коды для данных от пользователя
    String userInput = "[attacker-crafted-data]";
    
    // Даже если хакер знает алгоритм хеширования,
    // он не может предсказать hash code из-за random seed
    Set<String> set = new HashSet<>();
    set.add(userInput);  // Безопасно
}

Заключение

Коллизии возникают:

1. При разных объектах с одинаковым hashCode()
2. Из-за плохо реализованного hashCode()
3. Статистически при работе с большими наборами данных

HashMap обрабатывает коллизии:

• До Java 7: только linked list chaining
• Java 8+: chaining + Red-Black Tree для оптимизации

Ключевое правило: equals() ↔ hashCode() должны быть согласованы. Если нарушить этот контракт, поведение HashMap будет непредсказуемо.