Какие знаешь проблемы, если сделать у ключа в HashMap метод hashCode, возвращающий рандомное значение?

Проблемы рандомного hashCode в HashMap

Это один из самых опасных и тонких багов, которые могут возникнуть при неправильном использовании HashMap. Давайте разберёмся, почему это критическая проблема.

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

Java имеет критичный контракт между методами:

// Контракт: если a.equals(b) == true, то a.hashCode() == b.hashCode()
// Но ОБРАТНОЕ НЕ обязательно: разные объекты могут иметь одинаковый hash

class BadUser {
    private String name;
    
    @Override
    public int hashCode() {
        return new Random().nextInt(); // НИКОГДА так не делай!
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadUser)) return false;
        return this.name.equals(((BadUser) obj).name);
    }
}

Проблема 1: Невозможно найти объект в HashMap

При каждом вызове hashCode() возвращается разное число. HashMap не сможет найти объект, который уже в ней есть:

BadUser user = new BadUser("Alice");
Map<BadUser, String> map = new HashMap<>();

map.put(user, "value1");
System.out.println(map.get(user)); // null!

// Что произошло:
// put(): user.hashCode() = 12345, положил в bucket[12345]
// get(): user.hashCode() = 54321, ищет в bucket[54321]
// Разные bucket-ы, не находит!

Этот баг особенно коварен, потому что не выбросится исключение — просто вернётся null.

Проблема 2: Утечка памяти

Объект попадает в HashMap, но его потом нельзя найти:

Map<BadUser, String> map = new HashMap<>();

for (int i = 0; i < 1_000_000; i++) {
    BadUser user = new BadUser("User" + i);
    map.put(user, "data");
    // каждый put создаёт новую запись и НЕ может её перезаписать
    // потому что get() не найдёт старую запись
}

// map.size() = 1_000_000
// Все объекты живут в памяти, но их нельзя удалить!
// Это практически утечка памяти

Проблема 3: Вырождение в O(n) вместо O(1)

В HashMap при коллизиях используется связный список. Если hashCode() случаен, происходит много коллизий:

// Нормальный случай: хорошее распределение hash-ей
Map<Integer, String> goodMap = new HashMap<>();
for (int i = 0; i < 100; i++) {
    goodMap.put(i, "value");  // O(1) операция
}

// Проблемный случай: рандомные hash-и → много коллизий
Map<BadUser, String> badMap = new HashMap<>();
BadUser u1 = new BadUser("Alice");
BadUser u2 = new BadUser("Bob");
BadUser u3 = new BadUser("Charlie");

badMap.put(u1, "v1"); // Может быть O(1) или O(n)
badMap.put(u2, "v2"); // Вероятно O(n) — столкновение
badMap.put(u3, "v3"); // Вероятно O(n) — столкновение

Проблема 4: Нарушение контракта equals-hashCode

Это приводит к очень странному поведению:

BadUser user = new BadUser("Alice");
BadUser user2 = new BadUser("Alice");

// Два РАВНЫХ объекта (по equals)
System.out.println(user.equals(user2)); // true

// Но с разными hash-ами (так как hashCode() рандомный)
System.out.println(user.hashCode() == user2.hashCode()); // false!
// Это нарушает контракт!

// Результат в HashMap
Map<BadUser, String> map = new HashMap<>();
map.put(user, "value1");
System.out.println(map.containsKey(user2)); // false!
// А должно быть true, потому что equals() говорит что они равны!

Проблема 5: Проблемы с HashSet и других коллекций

Все коллекции, основанные на hash, сломаются:

Set<BadUser> set = new HashSet<>();
BadUser user = new BadUser("Alice");

set.add(user);
System.out.println(set.contains(user)); // false! Должно быть true

// ConcurrentHashMap тоже сломается
Map<BadUser, String> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put(user, "value");
System.out.println(concurrentMap.get(user)); // null!

Проблема 6: Непредсказуемое поведение при каждом запуске

Map<BadUser, String> map = new HashMap<>();
BadUser user = new BadUser("Alice");

map.put(user, "found");

// В первом запуске: get() вернёт "found"
// Во втором запуске: get() может вернуть null
// Это зависит от рандомных hash-ей

// Очень сложно дебажить такие проблемы!

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

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

Итоги

1. hashCode() должен быть детерминированным — одинаковый объект всегда возвращает одинаковый hash
2. Контракт equals-hashCode обязателен — если a.equals(b), то a.hashCode() == b.hashCode()
3. Никогда не используй случайные значения в hashCode()
4. Никогда не используй изменяемые поля как основу hash-а
5. hashCode() должна быть быстрой — её вызывают часто
6. Используй Objects.hash() для простой и безопасной реализации