🤔 Почему hashcode могут быть равны?

Хеш-коды могут быть равны для разных объектов из-за того, что они являются конечными представлениями данных, а количество возможных хеш-кодов ограничено. В Java метод hashCode возвращает значение типа int, что означает, что существует только \(2^{32}\) возможных значений хеш-кодов. Однако количество возможных объектов значительно больше, чем \(2^{32}\), что приводит к коллизиям хеш-кодов.

🚩Основные причины

🟠Ограниченный диапазон хеш-кодов
Хеш-коды представлены 32-битным целым числом, что дает \(2^{32}\) возможных значений. Это означает, что множество объектов должно быть отображено в это ограниченное пространство хеш-кодов, что приводит к коллизиям.

🟠Коллизии хеш-кодов
Коллизия возникает, когда два разных объекта имеют одинаковый хеш-код. Это неизбежно при использовании конечного диапазона хеш-кодов для представления множества объектов.

🚩Как работают коллизии

В Java структуры данных, такие как HashMap и HashSet, обрабатывают коллизии хеш-кодов, используя внутренние механизмы для разрешения коллизий. При коллизии хеш-кодов, когда два разных объекта имеют одинаковый хеш-код, они все равно могут быть правильно размещены и найдены в хеш-таблице.

public class Example {
    private int value;

    public Example(int value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Example example = (Example) obj;
        return value == example.value;
    }

    @Override
    public int hashCode() {
        return value % 10; // Искусственно создаем коллизии для демонстрации
    }

    public static void main(String[] args) {
        Example ex1 = new Example(1);
        Example ex2 = new Example(11);

        System.out.println(ex1.hashCode()); // 1
        System.out.println(ex2.hashCode()); // 1

        System.out.println(ex1.equals(ex2)); // false

        HashSet<Example> set = new HashSet<>();
        set.add(ex1);
        set.add(ex2);

        System.out.println(set.size()); // 2, так как объекты разные
    }
}

🚩Обработка коллизий

🟠Цепочки (Chaining)
Каждый элемент в хеш-таблице указывает на список (или другую структуру), содержащий все элементы с одинаковым хеш-кодом.
🟠Открытая адресация (Open Addressing)
В случае коллизии алгоритм ищет другую позицию в хеш-таблице для размещения элемента, используя определенную стратегию пробирования (linear probing, quadratic probing и т.д.).

Ставь 👍 и забирай 📚 Базу знаний