Что будет при добавлении ключа с одинаковым hashCode в HashMap и equals равным False?

Коллизия hashCode при различных equals в HashMap

Это важный вопрос о работе HashMap. Ответ: оба элемента будут сохранены в HashMap.

Сценарий: одинаковый hashCode, но equals = false

public class CollisionDemo {
    
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        
        // Добавим два объекта с одинаковым hashCode
        String key1 = "ab";
        String key2 = "ba";
        
        // Интересно: "ab".hashCode() == "ba".hashCode()
        System.out.println("key1 hashCode: " + key1.hashCode());  // 3104
        System.out.println("key2 hashCode: " + key2.hashCode());  // 3104
        System.out.println("equals: " + key1.equals(key2));       // false
        
        map.put(key1, "value1");
        map.put(key2, "value2");
        
        // Оба значения сохранены!
        System.out.println(map.get(key1));  // "value1"
        System.out.println(map.get(key2));  // "value2"
        System.out.println(map.size());     // 2
    }
}

Как HashMap разрешает коллизии

HashMap использует связные списки (или красно-черные деревья) для разрешения коллизий.

public class HashMapCollisionHandling {
    
    // Схема внутри HashMap:
    // Таблица бакетов:
    // Индекс 0: [Entry1] → [Entry2] → null
    // Индекс 1: [Entry3] → null
    // Индекс 2: [Entry4] → [Entry5] → [Entry6] → null
    // ...
    
    public static void main(String[] args) {
        Map<CustomKey, String> map = new HashMap<>();
        
        // Два объекта с одинаковым hashCode
        CustomKey key1 = new CustomKey(1, "A");
        CustomKey key2 = new CustomKey(2, "B");
        
        // Оба имеют hashCode = 100
        System.out.println(key1.hashCode());  // 100
        System.out.println(key2.hashCode());  // 100
        System.out.println(key1.equals(key2)); // false
        
        map.put(key1, "value1");
        map.put(key2, "value2");
        
        // HashMap поместит их в один бакет
        System.out.println(map.size());        // 2
        System.out.println(map.get(key1));    // "value1"
        System.out.println(map.get(key2));    // "value2"
    }
}

class CustomKey {
    int id;
    String name;
    
    public CustomKey(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    @Override
    public int hashCode() {
        return 100;  // Преднамеренно одинаковый
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        CustomKey other = (CustomKey) obj;
        return id == other.id && name.equals(other.name);
    }
}

Порядок операций внутри HashMap

Когда добавляешь ключ:

1. Вычисляется hashCode() ключа
2. По hashCode определяется индекс бакета: index = hash & (length - 1)
3. Ищутся существующие entries в этом бакете
4. Для каждого entry проверяется: existingKey.equals(newKey)
5. Если equals() вернул true - обновляем значение
6. Если equals() вернул false - добавляем новый entry в список

public class HashMapPutProcess {
    
    // Упрощенная реализация HashMap.put():
    public Object put(Object key, Object value) {
        int hash = key.hashCode();               // 1. hashCode()
        int index = hash & (table.length - 1);   // 2. Индекс бакета
        
        Entry entry = table[index];              // 3. Первый entry в бакете
        
        while (entry != null) {                  // 4. Проходим по списку
            if (entry.hash == hash && 
                entry.key.equals(key)) {         // 5. Проверка equals
                Object oldValue = entry.value;   // Обновляем
                entry.value = value;
                return oldValue;
            }
            entry = entry.next;                  // Следующий entry
        }
        
        // 6. Если не нашли - добавляем новый entry
        addEntry(hash, key, value, index);
        return null;
    }
}

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

public class CollisionExample {
    
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // Найдем пару строк с одинаковым hashCode
        // (это реальное свойство HashMap)
        
        String str1 = "Aa";
        String str2 = "BB";
        
        System.out.println("str1: " + str1 + ", hash: " + str1.hashCode());
        System.out.println("str2: " + str2 + ", hash: " + str2.hashCode());
        System.out.println("equals: " + str1.equals(str2));
        
        // Добавляем обе строки
        map.put(str1, 1);
        map.put(str2, 2);
        
        System.out.println("\nРезультат:");
        System.out.println("map.size() = " + map.size());      // 2
        System.out.println("map.get(str1) = " + map.get(str1)); // 1
        System.out.println("map.get(str2) = " + map.get(str2)); // 2
    }
}

Важная таблица

┌──────────────┬──────────────┬─────────────────────────────────────┐
│ hashCode()   │ equals()     │ Результат в HashMap                 │
├──────────────┼──────────────┼─────────────────────────────────────┤
│ Разные       │ false        │ Разные элементы, разные бакеты      │
│ Одинаковые   │ false        │ Разные элементы, ОДИН бакет (коллизия)
│ Одинаковые   │ true         │ Один элемент, обновляем значение    │
│ Разные       │ true         │ ОШИБКА! Нарушение контракта         │
└──────────────┴──────────────┴─────────────────────────────────────┘

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

public class HashCodeEqualsContract {
    
    // ПРАВИЛО: Если a.equals(b) == true,
    // то a.hashCode() == b.hashCode() ОБЯЗАТЕЛЬНО
    
    public static void main(String[] args) {
        User user1 = new User("john", 25);
        User user2 = new User("john", 25);
        
        if (user1.equals(user2)) {
            // Эта проверка ВСЕГДА должна быть true
            assert user1.hashCode() == user2.hashCode();
        }
    }
}

class User {
    String name;
    int age;
    
    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public boolean equals(Object obj) {
        // equals проверяет оба поля
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        User other = (User) obj;
        return name.equals(other.name) && age == other.age;
    }
    
    @Override
    public int hashCode() {
        // hashCode должен учитывать ОБА поля
        return Objects.hash(name, age);
    }
}

Производительность при коллизиях

public class CollisionPerformance {
    
    // При идеальном hashCode (без коллизий):
    // get() и put() работают за O(1)
    
    // При плохом hashCode (много коллизий):
    // get() и put() деградируют к O(n)
    
    public static void main(String[] args) {
        Map<BadKey, String> map = new HashMap<>();
        
        // Если все ключи имеют одинаковый hashCode
        for (int i = 0; i < 100000; i++) {
            BadKey key = new BadKey(i);
            map.put(key, "value" + i);
        }
        
        // То поиск станет ОЧЕНЬ медленным
        BadKey searchKey = new BadKey(50000);
        long start = System.currentTimeMillis();
        String value = map.get(searchKey);
        long time = System.currentTimeMillis() - start;
        
        System.out.println("Время поиска: " + time + "ms");
    }
}

class BadKey {
    int id;
    
    public BadKey(int id) {
        this.id = id;
    }
    
    @Override
    public int hashCode() {
        return 0;  // Все ключи имеют одинаковый hashCode - ПЛОХО
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        BadKey other = (BadKey) obj;
        return id == other.id;
    }
}

Вывод

Когда добавляешь ключ с одинаковым hashCode, но equals = false:

• Оба элемента сохраняются в HashMap
• Они размещаются в одном бакете (в связном списке)
• При поиске HashMap проверит оба элемента через equals()
• Это называется коллизией хеша - нормальное явление
• В Java 8+ при большом количестве коллизий HashMap переходит на красно-черные деревья
• Это не ошибка - HashMap корректно разрешает коллизии
• Главное правило: если equals() true, то hashCode() должен быть одинаковым