Какой алгоритм используется для генерации hashCode?

Алгоритм генерации hashCode в Java

Основной подход

В Java метод hashCode() является нативным для класса Object, но его реализация зависит от JVM. Однако ключевые алгоритмы стандартных классов известны.

Алгоритм для строк (String)

Наиболее известный алгоритм — для класса String. До Java 8 использовался алгоритм, похожий на полиномиальный хеш:

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 выбран как нечётное простое число
• Операция 31 * h оптимизируется компилятором в (h << 5) - h
• Алгоритм обеспечивает хорошее распределение для типичных строк

Алгоритмы для других классов

Для Integer:

public int hashCode() {
    return Integer.hashCode(value);
}
// Где Integer.hashCode() возвращает само значение

Для List (ArrayList):

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
    return hashCode;
}

Для HashMap (Node):

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Требования к hashCode()

Согласно контракту hashCode():

1. Консистентность: Для одного объекта должен возвращать одинаковое значение при многократных вызовах (при условии, что объект не изменялся)
2. Равенство объектов: Если a.equals(b) возвращает true, то a.hashCode() == b.hashCode()
3. Обратное не обязательно: Разные объекты могут иметь одинаковый хеш-код (коллизии)

Оптимизации в современных JVM

Хеширование в OpenJDK (HotSpot):

Для объектов используется Marsaglia's xor-shift алгоритм или системный рандом, в зависимости от конфигурации:

// Пример нативной реализации из HotSpot
static inline intptr_t get_next_hash(Thread* self, oop obj) {
    intptr_t value = 0;
    if (hashCode == 0) {
        value = os::random();  // Системный рандом
    } else if (hashCode == 1) {
        value = ++GVars.hcSequence;  // Последовательность
    } else if (hashCode == 2) {
        value = (intptr_t) obj;  // Адрес объекта
    } else if (hashCode == 3) {
        value = (intptr_t) obj->next_hash();  // Линейная последовательность
    } else if (hashCode == 4) {
        value = (intptr_t) obj ^ (GVars.hcRandom >> 32);  // Части адреса
    } else {
        unsigned ran = GVars.hcRandom;
        value = ran ^ (obj ^ self);  // Xor-shift вариант
    }
    return value & MarkWord::hash_mask;
}

Проблемы и решения

Коллизии:

// Пример коллизии строк
String s1 = "FB";
String s2 = "Ea";
System.out.println(s1.hashCode()); // 2236
System.out.println(s2.hashCode()); // 2236

Рекомендации для кастомных классов:

@Override
public int hashCode() {
    // Использование Objects.hash() для нескольких полей
    return Objects.hash(field1, field2, field3);
    
    // Или ручная реализация
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + (field2 != null ? field2.hashCode() : 0);
    result = 31 * result + (int) field3;
    return result;
}

Особенности в Android

В Android используются схожие алгоритмы, но с некоторыми оптимизациями:

1. Для строк кэширование хеша — вычисляется один раз
2. Использование Arrays.hashCode() для массивов
3. Упрощённые вычисления для экономии батареи

Выводы

• Основной алгоритм — полиномиальное хеширование с множителем 31
• Цель — минимизировать коллизии при сохранении производительности
• Важно соблюдать контракт между equals() и hashCode()
• В современных системах используются комбинации алгоритмов для баланса скорости и качества распределения