Когда у разных объектов могут быть одинаковые hashCode?

Когда у разных объектов могут быть одинаковые hashCode?

Ответ: ДА, разные объекты могут иметь одинаковый hashCode. Это называется hash collision и является нормальным, ожидаемым явлением в Java.

Контракт hashCode и equals

Важно понимать контракт между hashCode() и equals():

Правило 1: Если два объекта равны по equals(), они ДОЛЖНЫ иметь одинаковый hashCode()

if (object1.equals(object2)) {
    // ОБЯЗАТЕЛЬНО
    assert object1.hashCode() == object2.hashCode();
}

Правило 2: Если два объекта имеют одинаковый hashCode(), они МОГУТ быть не равны по equals()

if (object1.hashCode() == object2.hashCode()) {
    // Они могут быть равны, а могут и не быть
    // Нужно проверить с equals()
    if (object1.equals(object2)) {
        // Объекты действительно равны
    } else {
        // Это hash collision - нормальное явление
    }
}

Почему происходят коллизии?

1. hashCode() возвращает int (32-бита)

Инт может содержать только ~4 миллиарда значений, а объектов может быть намного больше. По принципу Pigeonhole Principle коллизии неизбежны:

// hashCode() возвращает int (-2^31 до 2^31-1)
public native int hashCode();  // int имеет 2^32 возможных значений

// А объектов может быть бесконечно много
User u1 = new User("John", "john@example.com");
User u2 = new User("Jane", "jane@example.com");
User u3 = new User("Jack", "jack@example.com");
// ... и так далее

2. Плохая реализация hashCode()

// ❌ Плохо - всегда возвращает одно значение
public class BadUser {
    public int hashCode() {
        return 1;  // Все объекты имеют одинаковый хеш!
    }
}

// Все объекты BadUser будут коллидировать
BadUser u1 = new BadUser();
BadUser u2 = new BadUser();
Set<BadUser> users = new HashSet<>();
users.add(u1);
users.add(u2);
// И u1, и u2 пойдут в один bucket, производительность упадет

Как работают коллизии в HashMap/HashSet?

// Внутренняя работа HashMap при коллизии

// 1. Объект помещается в bucket на основе hashCode()
int hash = object.hashCode();
int bucketIndex = hash % capacity;

// 2. Если в bucket уже есть объекты (коллизия), они связываются в цепочку
Bucket[bucketIndex] = new Entry(key, value, nextEntry);

// 3. При поиске (get) проверяется:
//    a) Правильный bucket по hashCode()
//    b) Затем перебираются все объекты в цепочке и проверяется equals()

Object retrieved = null;
for (Entry entry : bucket[bucketIndex]) {
    if (key.equals(entry.key)) {
        retrieved = entry.value;
        break;
    }
}

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

// Два разных пользователя
class User {
    private String name;
    private String email;
    
    @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(email, user.email);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(email);
    }
}

// Создаем пользователей
User alice = new User("Alice", "alice@example.com");
User bob = new User("Bob", "bob@example.com");

// По-чистому случаю у них может быть одинаковый hashCode
System.out.println(alice.hashCode());  // 123456
System.out.println(bob.hashCode());    // 123456 (коллизия!)

// Но они НЕ равны по equals
System.out.println(alice.equals(bob)); // false

// HashMap корректно обработает оба объекта
Map<User, String> map = new HashMap<>();
map.put(alice, "Software Engineer");
map.put(bob, "Data Scientist");

System.out.println(map.get(alice));  // Software Engineer
System.out.println(map.get(bob));    // Data Scientist

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

В Java 8+ используется комбинация подходов:

До Java 8: Цепочки (linked lists) в buckets

Bucket[0] → User("Alice") → User("Adam") → User("Austin") → null
           (все имеют hashCode() % capacity == 0)

Java 8+: Переход на красно-черное дерево при большом количестве коллизий

// Когда в одном bucket накапливается >8 элементов,
// цепочка преобразуется в TreeMap для O(log n) поиска
if (binCount >= TREEIFY_THRESHOLD - 1) {  // TREEIFY_THRESHOLD = 8
    treeifyBin(tab, hash);
}

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

// Хорошая реализация hashCode - мало коллизий
class GoodUser {
    private String email;
    
    @Override
    public int hashCode() {
        return email.hashCode();  // Распределение хорошее
    }
}

// Плохая реализация hashCode - много коллизий
class BadUser {
    private String email;
    
    @Override
    public int hashCode() {
        return 42;  // Все объекты коллидируют!
    }
}

// Тест производительности
Set<GoodUser> good = new HashSet<>();
Set<BadUser> bad = new HashSet<>();

for (int i = 0; i < 100000; i++) {
    good.add(new GoodUser("user" + i));
    bad.add(new BadUser("user" + i));
}

// bad.contains() будет намного медленнее!
// O(1) вместо O(n) в худшем случае

Best practices для hashCode()

// ✅ Используй Objects.hash()
@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3);
}

// ✅ Или идиоматичный способ
@Override
public int hashCode() {
    return 31 * email.hashCode() + age;
}

// ❌ Не используй все поля если они не нужны для equals()
@Override
public boolean equals(Object o) {
    // Только email важен
    return email.equals(other.email);
}

@Override
public int hashCode() {
    // hashCode тоже должен зависеть только от email
    return email.hashCode();
}

// ❌ Не используй объекты с изменяющимся hashCode как ключи Map
HashSet<StringBuilder> set = new HashSet<>();
StringBuilder sb = new StringBuilder("hello");
set.add(sb);
sb.append("world");  // Изменили содержимое - hashCode изменился!
// Теперь sb потеряется в HashSet!

Выводы

1. Коллизии нормальны — у разных объектов может быть одинаковый hashCode
2. Контракт важен — если equals() истинно, hashCode() должны быть одинаковы
3. HashMap обрабатывает коллизии — использует цепочки и деревья
4. Качество hashCode влияет на производительность — плохо распределенный хеш замедляет работу
5. Используй Objects.hash() — это простой и надежный способ

Коллизии — это не ошибка, а неотъемлемая часть хеширования. Java корректно их обрабатывает благодаря использованию equals() для окончательного сравнения.