Какой контракт при добавлении элемента в HashMap?

Контракт при добавлении элемента в HashMap

Контракт HashMap определяет правила, которые необходимо соблюдать при добавлении элементов, чтобы структура работала корректно. Это связано с методами hashCode() и equals().

Основной контракт Object

Когда вы добавляете элемент в HashMap (например, key-value пару), HashMap опирается на два критических метода:

public class HashMapContract {
    // 1. hashCode() — определяет бакет (bucket)
    // 2. equals() — определяет позицию в цепочке коллизий
    
    public static void main(String[] args) {
        Map<MyKey, String> map = new HashMap<>();
        MyKey key = new MyKey("john");
        
        // Шаг 1: вычисляется hashCode()
        int hash = key.hashCode();  // Например, 100
        
        // Шаг 2: hash приводится к индексу бакета
        int index = hash & (map.capacity() - 1);  // ~33 (в бакет 33)
        
        // Шаг 3: в бакете ищется элемент с equals() == true
        // Если не найден — новая пара добавляется
        map.put(key, "value");
    }
}

Контракт hashCode() и equals()

Итак, вот обязательные правила:

1. Если a.equals(b) = true, то a.hashCode() == b.hashCode()

MyKey key1 = new MyKey("john");
MyKey key2 = new MyKey("john");

if (key1.equals(key2)) {  // true
    // ОБЯЗАТЕЛЬНО:
    assert key1.hashCode() == key2.hashCode();  // Должно быть true!
}

Это критично для HashMap. Если нарушить это правило:

static class BadKey {
    String name;
    
    @Override
    public int hashCode() {
        return 1;  // Простой хеш
    }
    
    @Override
    public boolean equals(Object obj) {
        // Но используем для сравнения другие поля
        return obj instanceof BadKey && ((BadKey)obj).name.equals(this.name);
    }
}

public static void main(String[] args) {
    Map<BadKey, String> map = new HashMap<>();
    BadKey k1 = new BadKey();
    k1.name = "john";
    map.put(k1, "value1");
    
    BadKey k2 = new BadKey();
    k2.name = "john";
    System.out.println(map.get(k2));  // null — ОШИБКА!
    // Хотя k1.equals(k2) == true
}

2. Если a.hashCode() == b.hashCode(), то a.equals(b) может быть false

Инверсия не действует. Несколько разных объектов могут иметь одинаковый hashCode (коллизия) — это нормально.

Integer i1 = 42;
Integer i2 = new Integer(42);

assert i1.equals(i2);  // true
assert i1.hashCode() == i2.hashCode();  // true

String s1 = "Aa";
String s2 = "BB";
assert s1.hashCode() == s2.hashCode();  // true (коллизия!)
assert !s1.equals(s2);  // false — это допустимо

Практическое значение при put()

Когда вы вызываете map.put(key, value):

public class PutExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        String key1 = "hello";
        map.put(key1, 1);
        // Сохранено в бакет [hash("hello") % capacity]
        
        String key2 = new String("hello");
        map.put(key2, 2);
        // key1.equals(key2) = true
        // key1.hashCode() = key2.hashCode() (100, например)
        // Проверяется equals() в том же бакете
        // Находится key1, ПЕРЕЗАПИСЫВАЕТСЯ значение с 1 на 2
        
        System.out.println(map.size());  // 1, не 2!
        System.out.println(map.get(key1));  // 2
        System.out.println(map.get(key2));  // 2
    }
}

Правильная реализация

public class CorrectKey {
    private final String name;  // Immutable
    private final int id;
    
    public CorrectKey(String name, int id) {
        this.name = name;
        this.id = id;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof CorrectKey)) return false;
        CorrectKey other = (CorrectKey) obj;
        return Objects.equals(this.name, other.name) && this.id == other.id;
    }
}

Резюме контракта

1. Обязательно: equals(true) ⟹ hashCode равны
2. Обязательно: используйте одни и те же поля в hashCode() и equals()
3. Обязательно: если объект — ключ HashMap, делайте его immutable
4. Желательно: распределение hashCode должно быть равномерным (хорошая функция хеширования)

Нарушение этих правил приведёт к потере данных, невозможности найти элементы и непредсказуемому поведению HashMap.