Что происходит в HashSet, если у ключей совпадает Hash

Отличный вопрос, который касается самой сути работы HashSet и его взаимосвязи с hashCode() и equals(). Это фундаментальная тема для понимания коллекций в Java/Kotlin.

Краткий ответ: Если у ключей (элементов) HashSet совпадает хэш-код, они помещаются в одну и ту же корзину (bucket). Однако внутри этой корзины элементы с одинаковым хэш-кодом, но не равные друг другу по методу equals(), будут храниться как разные элементы, формируя связанный список (или дерево, в зависимости от условий). Если же хэш-код и equals() совпадают, новый элемент считается дубликатом и не добавляется.

Давайте разберем это детально, так как процесс происходит в два ключевых этапа.

1. Распределение по корзинам (Hashing)

Внутри HashSet (который построен на основе HashMap) есть массив Node<K,V>[] table. Индекс корзины в этом массиве вычисляется на основе хэш-кода элемента.

// Упрощенная логика вычисления индекса
int index = (table.length - 1) & hash(key);

Если хэш-коды двух разных элементов A и B совпадают, эта формула даст один и тот же индекс. Оба элемента будут претендовать на место в одной и той же корзине. Это называется коллизией хэш-кода.

2. Разрешение коллизий внутри корзины (Collision Resolution)

Попадание в одну корзину не означает, что элементы будут признаны одинаковыми. Дальше вступает в силу метод equals().

• Сценарий 1: hashCode() совпал, equals() == false

    Это классическая коллизия. Внутри корзины элементы хранятся в структуре данных. В Java 8+ это **связанный список, который при достижении определенного порога преобразуется в сбалансированное бинарное дерево (красно-черное дерево)**.

```java
// Пример: два разных объекта с одинаковым хэш-кодом
class Person {
    String name;
    int id;

    @Override
    public int hashCode() {
        // Плохая, но наглядная реализация - всегда возвращает 1
        return 1;
    }

    @Override
    public boolean equals(Object o) {
        // Сравниваем по id
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id;
    }
}

// В HashSet
Set<Person> set = new HashSet<>();
set.add(new Person("Alice", 1)); // hash=1, помещается в корзину 1
set.add(new Person("Bob", 2));   // hash=1, тоже корзина 1. equals() с Alice -> false.
// В корзине с индексом 1 теперь лежат два объекта Person в виде списка или дерева.
System.out.println(set.size()); // Вывод: 2
```

• Сценарий 2: hashCode() совпал, equals() == true

    В этом случае `HashSet` определяет, что это **один и тот же ключ**. Новый элемент не добавляется, а значение ассоциированное с ним (для `HashSet` это заглушка `PRESENT`) обновляется. Размер коллекции не меняется.

```java
set.add(new Person("Alice", 1));
set.add(new Person("AliceClone", 1)); // hash=1, equals() с первым -> true (id одинаковы)
System.out.println(set.size()); // Вывод: 1. Второй объект не добавлен.
```

Последствия и важность контракта hashCode()/equals()

Для корректной работы HashSet ОБЯЗАТЕЛЬНО выполнение контракта:

1. Если два объекта равны по equals(), их hashCode() должны быть одинаковыми.
2. Обратное не обязательно: объекты с одинаковым hashCode() могут быть не равны по equals() (это и есть коллизия).

Что произойдет, если нарушить контракт? Например, равные объекты будут возвращать разный хэш-код. Они попадут в разные корзины, и HashSet добавит их как два разных элемента, даже если equals() говорит, что они одинаковы. Это сломает фундаментальное свойство Set — уникальность элементов.

// Нарушенный контракт - ОПАСНО!
@Override
public int hashCode() {
    return Objects.hash(name); // Хэш только по имени
}
@Override
public boolean equals(Object o) {
    // Сравнение и по имени, и по id
    Person person = (Person) o;
    return id == person.id && Objects.equals(name, person.name);
}
// Два объекта с одинаковым id, но разным name будут считаться равными (equals()=true),
// но иметь разный хэш-код. HashSet может добавить ОБА.

Итог и влияние на производительность

Совпадение хэш-кодов (высокая частота коллизий) негативно влияет на производительность HashSet:

• В лучшем случае (O(1)): Поиск, добавление, удаление происходит за константное время, если элементы равномерно распределены по корзинам.
• В худшем случае (O(n) или O(log n)): При множестве коллизий все элементы скапливаются в одной корзине. Поиск деградирует до линейного сканирования списка (O(n)) или до поиска в дереве (O(log n)), что значительно медленнее.

Поэтому качественная реализация hashCode(), равномерно распределяющая объекты по диапазону целых чисел, критически важна для эффективной работы HashSet (и всех хэш-коллекций).