Какие знаешь контракты ключа в HashMap?

Контракты ключа в HashMap

HaspMap работает на основе хэширования, поэтому ключи должны удовлетворять определённым требованиям (контрактам). Эти контракты критичны для корректной работы HashMap.

1. equals() контракт — Equivalence Relation

Метод equals() должен удовлетворять четырём свойствам:

public class UserKey {
    private String email;
    private int id;
    
    // Контракт equals():
    
    // 1. Reflexivity: x.equals(x) == true
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true; // Reflexivity ✓
        
        if (obj == null || getClass() != obj.getClass()) return false;
        
        UserKey other = (UserKey) obj;
        
        // 2. Symmetry: x.equals(y) => y.equals(x)
        // 3. Transitivity: x.equals(y) && y.equals(z) => x.equals(z)
        return email.equals(other.email) && id == other.id;
        // 4. Consistency: multiple calls return same result
        //    (if object not modified)
    }
}

// Пример нарушения контракта (❌ ПЛОХО)
public class BadKey {
    private String value;
    
    @Override
    public boolean equals(Object obj) {
        // ❌ Зависит от времени
        return System.currentTimeMillis() % 2 == 0; // Нарушает Consistency!
    }
}

2. hashCode() контракт

Это самый важный контракт для HashMap:

public class ProperKey {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        // Контракт hashCode():
        
        // 1. Consistency: несколько вызовов возвращают одно значение
        //    (если объект не изменяется)
        // 2. equals() => hashCode()
        //    Если a.equals(b) == true, то a.hashCode() == b.hashCode()
        
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + age;
        return result;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        
        ProperKey other = (ProperKey) obj;
        return name.equals(other.name) && age == other.age;
    }
}

// Использование в HashMap
public class HashMapContractDemo {
    public static void main(String[] args) {
        Map<ProperKey, String> map = new HashMap<>();
        
        ProperKey key1 = new ProperKey("John", 30);
        ProperKey key2 = new ProperKey("John", 30);
        
        // key1 и key2 равны по equals()
        System.out.println(key1.equals(key2)); // true
        
        // И их hashCode одинаков
        System.out.println(key1.hashCode() == key2.hashCode()); // true
        
        map.put(key1, "value1");
        System.out.println(map.get(key2)); // "value1" ✓ Правильно!
    }
}

3. Правило: если equals(), то hashCode() должен быть одинаков

Это критичное правило:

// ✓ ПРАВИЛЬНО
public class GoodKey {
    private String id;
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof GoodKey)) return false;
        return id.equals(((GoodKey) obj).id);
    }
    
    @Override
    public int hashCode() {
        return id.hashCode(); // Одинаковый для равных объектов
    }
}

// ❌ НЕПРАВИЛЬНО — нарушение контракта
public class BadKey {
    private String id;
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadKey)) return false;
        return id.equals(((BadKey) obj).id);
    }
    
    @Override
    public int hashCode() {
        // ❌ Возвращает разные значения для равных объектов!
        return (int) System.currentTimeMillis();
    }
}

// Демонстрация проблемы
public void demonstrateProblem() {
    Map<BadKey, String> map = new HashMap<>();
    
    BadKey key1 = new BadKey("user1");
    map.put(key1, "value1");
    
    BadKey key2 = new BadKey("user1");
    // key1.equals(key2) == true
    // но key1.hashCode() != key2.hashCode() (разные при вызове)
    
    String result = map.get(key2);
    System.out.println(result); // null ❌ Ожидаем "value1"
    // HashMap ищет в неправильной bucket'е!
}

4. Иммутабельность (Immutability)

Ключи должны быть неизменяемыми (immutable):

// ✓ ПРАВИЛЬНО — неизменяемый ключ
public final class GoodImmutableKey {
    private final String name;
    private final int id;
    
    public GoodImmutableKey(String name, int id) {
        this.name = name;
        this.id = id;
    }
    
    // Нет setters!
    // Поля final
    
    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof GoodImmutableKey)) return false;
        GoodImmutableKey other = (GoodImmutableKey) obj;
        return name.equals(other.name) && id == other.id;
    }
}

// ❌ НЕПРАВИЛЬНО — изменяемый ключ
public class BadMutableKey {
    private String name; // Не final!
    private int id;      // Не final!
    
    public void setName(String name) { // Setter!
        this.name = name;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadMutableKey)) return false;
        BadMutableKey other = (BadMutableKey) obj;
        return name.equals(other.name) && id == other.id;
    }
}

// Демонстрация проблемы
public void demonstrateMutableKeyProblem() {
    Map<BadMutableKey, String> map = new HashMap<>();
    
    BadMutableKey key = new BadMutableKey("user1", 1);
    map.put(key, "value1");
    
    // Изменяем ключ
    key.setName("user2"); // ❌ Изменили hashCode()!
    
    // HashMap больше не может найти значение
    String result = map.get(key); // null ❌
    
    // Но значение всё ещё там, просто в неправильной bucket'е
    System.out.println(map.containsValue("value1")); // true
}

5. Как работает HashMap с этими контрактами

public void hashMapInternals() {
    Map<String, Integer> map = new HashMap<>();
    
    // PUT операция
    map.put("key1", 100);
    // 1. Вычисляется hashCode("key1") = 123456
    // 2. Вычисляется index = 123456 % buckets.length = 5
    // 3. В bucket[5] добавляется entry (key1, 100)
    
    // GET операция
    Integer value = map.get("key1");
    // 1. Вычисляется hashCode("key1") = 123456
    // 2. Вычисляется index = 123456 % buckets.length = 5
    // 3. В bucket[5] ищется ключ через equals()
    // 4. Возвращается 100
    
    // Если в bucket'е несколько ключей (коллизия):
    // HashMap использует equals() для поиска нужного
}

6. Хорошие и плохие примеры ключей

// ✓ ПРАВИЛЬНЫЕ ключи

// String — встроенный, неизменяемый
Map<String, String> map1 = new HashMap<>();
map1.put("key", "value");

// Integer — встроенный, неизменяемый
Map<Integer, String> map2 = new HashMap<>();
map2.put(42, "answer");

// UUID — неизменяемый
Map<UUID, String> map3 = new HashMap<>();
map3.put(UUID.randomUUID(), "value");

// Custom immutable class
public final class UserId {
    private final long id;
    
    public UserId(long id) {
        this.id = id;
    }
    
    @Override
    public int hashCode() {
        return Long.hashCode(id);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof UserId)) return false;
        return id == ((UserId) obj).id;
    }
}

Map<UserId, String> map4 = new HashMap<>();
map4.put(new UserId(123), "value");

// ❌ НЕПРАВИЛЬНЫЕ ключи

// ArrayList — изменяемый! НЕ ИСПОЛЬЗУЙ КАК КЛЮЧ
List<String> list = new ArrayList<>();
List<String> list2 = new ArrayList<>();
Map<List, String> badMap1 = new HashMap<>();
list.add("a");
list2.add("a");
badMap1.put(list, "value");
list.add("b"); // ❌ Изменили hashCode()!

// HashMap — изменяемый! НЕ ИСПОЛЬЗУЙ КАК КЛЮЧ
Map<String, String> innerMap = new HashMap<>();
innerMap.put("key", "val");
Map<Map, String> badMap2 = new HashMap<>();
badMap2.put(innerMap, "value");
innerMap.put("key2", "val2"); // ❌ Нарушил контракт!

// Объект с неправильно реализованным equals()/hashCode()
public class BadHashCodeKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 1; // ❌ Все объекты имеют одинаковый hashCode!
    }
}

7. Java встроенные вспомогательные методы

public class UtilMethods {
    
    public static void main(String[] args) {
        // Objects.hash() — удобно для реализации hashCode()
        String name = "John";
        int age = 30;
        int hash = Objects.hash(name, age); // Правильная реализация
        
        // Objects.equals() — безопасное сравнение с null
        String str1 = "hello";
        String str2 = null;
        boolean equals = Objects.equals(str1, str2); // false, не NullPointerException
    }
}

Резюме контрактов ключа

1. Уникальность через equals():

   • Два ключа с equals() == true считаются одним ключом
   • Переопредели equals() правильно

2. Хэширование через hashCode():

   • Одинаковые ключи (по equals) должны иметь одинаковый hashCode
   • Используй Objects.hash() для удобства

3. Иммутабельность:

   • Ключ не должен изменяться после добавления в HashMap
   • Используй final поля и отсутствие setters

4. Встроенные типы:

   • String, Integer, UUID и другие встроенные типы уже правильно реализуют контракт
   • Используй их когда возможно

5. Комбинация:

   • equals(), hashCode() и иммутабельность работают вместе
   • Нарушение одного нарушает работу HashMap

Нарушение этих контрактов приводит к потере данных, невозможности найти значения и другим трудноуловимым багам.