Можно ли гарантировать уникальность hashCode при String ключе?

Уникальность hashCode для String ключей

Это один из самых важных вопросов о работе хеш-таблиц в Java. Прямой ответ: нет, гарантировать абсолютную уникальность hashCode невозможно, но для String это обычно не проблема на практике.

Теория коллизий хеша

hashCode — это не уникальный идентификатор, это просто число. По определению, бесконечное количество объектов может отображаться в конечное количество хешей. Это называется коллизией хеша.

Для String в Java используется алгоритм:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Множитель 31 выбран потому что это простое число, что снижает вероятность коллизий. Но это всё равно не гарантирует уникальность!

Почему коллизии случаются

hashCode возвращает int — всего 2³² возможных значений (примерно 4 миллиарда). Если у вас будет больше уникальных String'ов, неизбежно произойдут коллизии по принципу Парадокса дней рождения.

Примеры коллизий:

String s1 = "FB";
String s2 = "Ea";

System.out.println(s1.hashCode()); // 2236
System.out.println(s2.hashCode()); // 2236

Как HashMap обрабатывает коллизии

HashMap не полагается только на hashCode. При коллизии используется метод equals() для проверки эквивалентности:

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int index = hash & (table.length - 1);
    Entry<K, V> entry = table[index];
    while (entry != null) {
        if (entry.hash == hash && entry.key.equals(key)) {
            V oldValue = entry.value;
            entry.value = value;
            return oldValue;
        }
        entry = entry.next;
    }
}

Контракт hashCode и equals

КРИТИЧНО помнить: если два объекта равны по equals(), то их hashCode ДОЛЖЕН быть одинаков. Для String это соблюдается.

Почему для String это не критично

1. Вероятность коллизии низкая — String'ы редко конфликтуют
2. HashMap адаптивна — с Java 8 преобразует бакеты в красно-черные деревья при слишком много коллизий
3. equals() спасает ситуацию — коллизия просто проверяется дополнительным сравнением

Практические выводы

• ❌ Нельзя гарантировать уникальность hashCode
• ✅ HashMap разрешает коллизии через equals()
• ✅ String безопасно использовать как ключ благодаря правильной реализации