Что будет происходить при вставке в HashMap двух одинаковых элементов по equals с разным значением hashCode?

HashMap: equals и hashCode контракт

Вопрос: Что будет если вставить два элемента где equals=true, но hashCode разный?

Ответ: Это нарушение контракта и приведет к неправильной работе HashMap. Оба элемента будут в разных buckets.

HashMap внутреннее устройство

HashMap использует двухуровневую систему:

1. hashCode() → индекс bucket-a (корзины)
2. equals() → поиск внутри bucket-a

Пример проблемы

public class BadKey {
    private String value;
    
    public BadKey(String value) {
        this.value = value;
    }
    
    // ❌ ПЛОХО: equals говорит они равны
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadKey)) return false;
        return value.equals(((BadKey) o).value);
    }
    
    // ❌ ПЛОХО: hashCode нарушает контракт
    @Override
    public int hashCode() {
        return 42; // Всегда одно и то же (очень плохо!)
        // Но в нашем примере у разных объектов могут быть разные коды
    }
}

public class Problem {
    public static void main(String[] args) {
        HashMap<BadKey, String> map = new HashMap<>();
        
        BadKey key1 = new BadKey("John") {
            @Override
            public int hashCode() {
                return 1; // hashCode = 1
            }
        };
        
        BadKey key2 = new BadKey("John") {
            @Override
            public int hashCode() {
                return 2; // Такой же по equals, но hashCode = 2 !!!
            }
        };
        
        System.out.println("key1.equals(key2): " + key1.equals(key2)); // true
        System.out.println("key1.hashCode(): " + key1.hashCode());     // 1
        System.out.println("key2.hashCode(): " + key2.hashCode());     // 2
        
        // Вставляем первый ключ
        map.put(key1, "Value 1");
        
        // Вставляем второй ключ
        map.put(key2, "Value 2");
        
        // Проблема: оба ключа в HashMap!
        System.out.println("Map size: " + map.size()); // 2 ❌ Должно быть 1
        
        // Получение значения
        System.out.println("Get by key2: " + map.get(key2));       // "Value 2"
        System.out.println("Get by key1: " + map.get(key1));       // "Value 1" ❌ Неправильно!
    }
}

Почему это происходит

HashMap алгоритм поиска:

1. Вычисляем hash() от ключа
2. Вычисляем индекс bucket-a = hash & (capacity - 1)
3. Идем в эту корзину
4. Ищем элемент с equals() == true

Если hashCode разный:
→ Идем в разные bucket-ы
→ equals никогда не вызывается
→ Оба элемента добавляются в HashMap

Диаграмма

HashMap с capacity=16:

Букет 0: []
Букет 1: [key1="John", "Value 1"] ← hashCode()=1
Букет 2: [key2="John", "Value 2"] ← hashCode()=2 ❌ РАЗНЫЕ БУКЕТЫ!
Букет 3: []
Букет 4: []
...
Букет 15: []

Map.size() = 2 вместо 1

Контракт equals/hashCode

Правило: Если a.equals(b) == true, то a.hashCode() ДОЛЖЕН равняться b.hashCode()

// ✓ ПРАВИЛЬНО
public class GoodKey {
    private String value;
    
    public GoodKey(String value) {
        this.value = value;
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof GoodKey)) return false;
        return value.equals(((GoodKey) o).value);
    }
    
    @Override
    public int hashCode() {
        return value.hashCode(); // Зависит от value, как и equals
    }
}

public class CorrectBehavior {
    public static void main(String[] args) {
        HashMap<GoodKey, String> map = new HashMap<>();
        
        GoodKey key1 = new GoodKey("John");
        GoodKey key2 = new GoodKey("John");
        
        System.out.println("key1.equals(key2): " + key1.equals(key2)); // true
        System.out.println("key1.hashCode() == key2.hashCode(): " +
            (key1.hashCode() == key2.hashCode())); // true ✓
        
        map.put(key1, "Value 1");
        map.put(key2, "Value 2");
        
        System.out.println("Map size: " + map.size()); // 1 ✓ Правильно
        System.out.println("Map.get(key1): " + map.get(key1)); // "Value 2" ✓
    }
}

Хеш-коллизии (нормальные)

Если hashCode у двух разных объектов одинаков (но equals=false):

public class HashCollision {
    @Override
    public int hashCode() {
        return 42; // Очень плохая hash функция
    }
    
    @Override
    public boolean equals(Object o) {
        return this == o; // Разные объекты = не равны
    }
}

// HashMap поместит оба в одну корзину (bucket)
// Но они различны по equals(), поэтому оба остаются
// (хеш-коллизия обработана через linked list или red-black tree)

HashMap.put(collision1, "A");
HashMap.put(collision2, "B");

// Оба в корзине 42, но разные узлы

Разные хеши, но equals=true (ОШИБКА)

Это нарушение контракта — приводит к нарушению инвариантов HashMap:

HashMap<BadKey, String> map = new HashMap<>();

BadKey a = new BadKey("x") { hashCode() { return 1; } };
BadKey b = new BadKey("x") { hashCode() { return 2; } }; // Разные коды!

map.put(a, "Value A");
map.put(b, "Value B");

// ❌ Инвариант HashMap нарушен:
map.size(); // 2 (должно быть 1)
map.containsKey(a); // true
map.containsKey(b); // true (они по equals равны, но в разных bucket-ах)
map.values(); // Содержит оба значения

Как это найти (IDE помощь)

// IntelliJ подчеркнет:
@Override
public boolean equals(Object o) { ... } // ⚠️ hashCode не согласован

// Правильное решение:
@Override
public int hashCode() {
    return Objects.hash(field1, field2);
}

@Override
public boolean equals(Object o) {
    if (!(o instanceof MyClass)) return false;
    MyClass that = (MyClass) o;
    return Objects.equals(field1, that.field1) &&
           Objects.equals(field2, that.field2);
}

Best Practices

// ✓ Всегда use IDE generation
@Data // Lombok генерирует оба
public class User {
    private String id;
    private String name;
}

// ✓ Используй Objects.hash() и Objects.equals()
public class Product {
    @Override
    public int hashCode() {
        return Objects.hash(id, sku); // Правильно
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Product)) return false;
        Product product = (Product) o;
        return Objects.equals(id, product.id) &&
               Objects.equals(sku, product.sku);
    }
}

// ✗ Не используй случайные хеши
public class Bad {
    @Override
    public int hashCode() {
        return new Random().nextInt(); // ❌ НИКОГДА!
    }
}

На собеседовании

Правильный ответ:

"Это нарушение контракта equals/hashCode. HashMap использует hashCode() для выбора bucket-а, и если hashCode разный, элементы пойдут в разные bucket-ы, даже если equals говорит что они равны.

Результат: HashMap будет содержать оба элемента (вместо одного), что нарушает инвариант.

Контракт: если a.equals(b) == true, то a.hashCode() == b.hashCode().

Это правило обязательно, иначе HashMap (и HashSet, HashMap.keySet()) дают неправильные результаты."

Ключевые выводы

• Контракт: equals=true → hashCode ДОЛЖЕН быть одинаков
• Нарушение: приводит к дублям в HashMap
• hashCode определяет bucket (быстро)
• equals сравнивает внутри bucket-а (медленно)
• Всегда генерируй оба через IDE или Lombok
• Используй Objects.hash() и Objects.equals()
• Это частая ошибка и один из любимых вопросов на собеседованиях