Для чего нужен hashcode()?

Назначение и использование hashCode()

Основное назначение

Метод hashCode() возвращает числовое представление объекта — хеш-код. Это не идентификатор объекта, а скорее отпечаток пальца, который помогает быстро находить объекты в хеш-таблицах.

Основная цель: оптимизация поиска в коллекциях типа HashMap, HashSet, Hashtable.

Как работает hashCode() в коллекциях

Без хеш-кодов поиск элемента в HashSet требовал бы проверку каждого элемента (O(n)):

// Плохо: линейный поиск
for (Object obj : collection) {
    if (obj.equals(searchElement)) {
        return true;  // O(n) операция
    }
}

С хеш-кодами поиск работает за O(1) в среднем:

// Хорошо: хеширование
Set<User> users = new HashSet<>();
users.add(new User("John", 30));  // вычисляется hashCode()
User search = new User("John", 30);
if (users.contains(search)) {     // сначала проверяется hashCode()
    System.out.println("Found");
}

Контракт между equals() и hashCode()

Это критически важный контракт в Java:

public class User {
    private String name;
    private int age;
    
    // Правило: если equals вернёт true, hashCode() должен вернуть ОДИНаковые значения
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof User)) return false;
        User other = (User) obj;
        return this.name.equals(other.name) && this.age == other.age;
    }
    
    @Override
    public int hashCode() {
        // ПРАВИЛЬНО: используем те же поля что и в equals()
        return Objects.hash(name, age);
    }
}

Почему контракт важен

Если нарушить контракт, HashSet/HashMap не будут работать корректно:

public class BadUser {
    private String name;
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadUser)) return false;
        return this.name.equals(((BadUser) obj).name);
    }
    
    @Override
    public int hashCode() {
        // ОШИБКА: возвращаем константу, не зависит от name
        return 42;
    }
}

// Результат: HashSet работает неправильно
Set<BadUser> set = new HashSet<>();
set.add(new BadUser("John"));
set.add(new BadUser("Jane"));
set.add(new BadUser("John")); // добавится ещё раз
System.out.println(set.size()); // 3 вместо 2!

Реальное использование в HashMap

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("apple", 3);  // обновится существующий ключ

// Вход: вычисляется hashCode("apple")
// HashMap: быстро находит bucket по хешу
// Проверка: если в bucket есть ключи, сравнивает через equals()
System.out.println(map.get("apple")); // 3

Интернально HashMap работает так:

// Упрощённое объяснение
private static final int DEFAULT_CAPACITY = 16;
private Entry<K, V>[] table = new Entry[DEFAULT_CAPACITY];

public V put(K key, V value) {
    int hash = key.hashCode();
    int index = hash % DEFAULT_CAPACITY;  // индекс bucket
    
    // Если в bucket коллизия, используем equals()
    Entry<K, V> entry = table[index];
    while (entry != null) {
        if (entry.key.equals(key)) {
            return entry.setValue(value);  // обновляем
        }
        entry = entry.next;
    }
    // Добавляем новую пару
    table[index] = new Entry<>(key, value, table[index]);
    return null;
}

Распространённые ошибки

Ошибка 1: Используем mutable поля в hashCode()

public class MutableUser {
    private List<String> tags;  // mutable!
    
    @Override
    public int hashCode() {
        // ОПАСНО: если tags изменится, hashCode() вернёт другое значение
        return Objects.hash(tags);
    }
}

Set<MutableUser> set = new HashSet<>();
MutableUser user = new MutableUser();
user.tags = Arrays.asList("admin");
set.add(user);

user.tags.add("moderator");  // изменили объект
set.contains(user);  // false! объект потерялся

Ошибка 2: Переопределяем только equals() или только hashCode()

// НЕПРАВИЛЬНО
public class Broken {
    @Override
    public boolean equals(Object obj) {
        return this == obj;
    }
    // hashCode() не переопределён, использует Object.hashCode()
}

Как правильно реализовать

Используйте IDE или Objects.hash():

public class User {
    private String email;
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof User)) return false;
        User user = (User) obj;
        return email.equals(user.email) &&
               name.equals(user.name) &&
               age == user.age;
    }
    
    @Override
    public int hashCode() {
        // Используем те же поля что в equals()
        return Objects.hash(email, name, age);
    }
}

Выводы

1. hashCode() нужен для быстрого поиска в HashSet/HashMap
2. Контракт: если equals() вернёт true, hashCode() должен вернуть одинаковые значения
3. Всегда переопределяйте оба метода вместе
4. Используйте только immutable поля в hashCode()
5. Стандартное решение: Objects.hash(field1, field2, ...)