У чего используется hashCode в HashMap: у ключа или значения

hashCode в HashMap: использование и важность

Краткий ответ

hashCode используется только для ключей (keys), а не для значений (values). Это критично для понимания работы HashMap.

Как HashMap внутри работает

HashMap использует комбинацию hash-таблицы и цепочек (bucket chains) для хранения данных:

// Внутренняя структура HashMap
private Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // hashCode ключа
    final K key;         // Сам ключ
    V value;             // Значение
    Node<K,V> next;      // Для цепочки коллизий
}

Почему hashCode нужен только для ключей

1. Определение position в таблице:

Когда ты добавляешь элемент в HashMap, сначала вычисляется hash ключа:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    
    int hash = hash(key.hashCode());  // hashCode КЛЮЧА
    int i = indexFor(hash, table.length);
    // Определяем в какой bucket положить элемент
}

Этот индекс говорит HashMap, в какую ячейку таблицы поместить Node.

2. Поиск значения:

Когда ты вызываешь get(key), HashMap:

1. Вычисляет hash(key.hashCode())
2. Идёт в соответствующий bucket
3. Проходит по цепочке коллизий, сравнивая equals()
4. Возвращает значение

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    
    int hash = hash(key.hashCode());  // hashCode КЛЮЧА
    for (Node<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key))  // Сравнение КЛЮЧА
            return e.value;                        // Возвращаем ЗНАЧЕНИЕ
    }
    return null;
}

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

public class User {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // hashCode вычисляется из полей ключа
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }
}

// Использование
HashMap<User, String> map = new HashMap<>();
User user1 = new User("John", 30);
String phone = "123-456-7890";

map.put(user1, phone);  // hashCode USER вычисляется, phone НЕ используется
String result = map.get(new User("John", 30));  // Находит по hashCode USER

Почему значения не нуждаются в hashCode

Ключ должен быть уникально идентифицируем для поиска. Значение просто хранится в Node.

Сценарий: у тебя может быть несколько ключей с одним и тем же значением:

HashMap<String, String> map = new HashMap<>();
map.put("city1", "Moscow");      // Значение "Moscow"
map.put("city2", "Moscow");      // То же значение
map.put("city3", "Moscow");      // Опять то же значение

// hashCode нужен только для ключей "city1", "city2", "city3"
// Значения "Moscow" вообще не используют hashCode

Частая ошибка: игнорирование hashCode и equals

public class BadKey {
    private String id;
    
    // Ошибка: не переопределён hashCode и equals
    // HashMap будет использовать identity hashCode (System.identityHashCode)
}

// Результат: одно и то же значение id будет храниться несколько раз
HashMap<BadKey, String> map = new HashMap<>();
BadKey key1 = new BadKey("same-id");
BadKey key2 = new BadKey("same-id");

map.put(key1, "value1");
map.put(key2, "value2");  // Добавится как разный ключ!

System.out.println(map.size());  // 2 вместо 1

Корректная реализация ключа

final class UserKey {
    private final String email;
    private final int departmentId;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof UserKey)) return false;
        UserKey userKey = (UserKey) o;
        return departmentId == userKey.departmentId && 
               Objects.equals(email, userKey.email);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(email, departmentId);
    }
}

Резюме

• hashCode используется для ключей для быстрого поиска в O(1) среднем случае
• hashCode НЕ используется для значений — они просто хранятся в Node
• Контракт: если equals() возвращает true, то hashCode() должен быть идентичен
• Всегда переопределяй оба метода вместе для пользовательских типов ключей