Java Academy · Урок

Реализация hashCode

Пишите корректные хеш-функции

«Реализация hashCode» — бесплатный урок Java Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Цели хорошего hashCode

Хороший hashCode() должен:

Возвращать одно и то же значение для равных объектов (таково требование контракта).
Распределять неравные объекты по множеству различных значений.
Вычисляться быстро.

Неудачный hashCode, возвращающий константу, всё ещё удовлетворяет контракту, но превращает map в медленный связный список.

public class Main {
    public static void main(String[] args) {
        // Legal but terrible: every object collides
        System.out.println("constant hashCode is legal but kills performance");
    }
}

Objects.hash для распространённого случая

Самый простой корректный подход — Objects.hash(field1, field2, ...).

Метод обрабатывает нулевые значения и объединяет поля с помощью стандартного алгоритма. Используйте те же поля, которые сравниваются в equals.

import java.util.Objects;

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() { return Objects.hash(name, age); }
    }
    public static void main(String[] args) {
        User a = new User("Ada", 36);
        User b = new User("Ada", 36);
        System.out.println(a.hashCode() == b.hashCode());
    }
}

Классический множитель 31

При написании хеширования вручную стандартный шаблон умножает текущий результат на 31 и добавляет хеш каждого поля.

31 — нечётное простое число, а 31 * x эквивалентно (x << 5) - x, поэтому JVM может оптимизировать это вычисление.

public class Main {
    static class User {
        final String name; final int age;
        User(String name, int age) { this.name = name; this.age = age; }
        @Override public int hashCode() {
            int result = 17;
            result = 31 * result + (name == null ? 0 : name.hashCode());
            result = 31 * result + age;
            return result;
        }
    }
    public static void main(String[] args) {
        System.out.println(new User("Ada", 36).hashCode());
    }
}

Хеширование примитивных типов

Для каждого примитивного типа рекомендуется свой способ вычисления хеша:

int: используйте само значение.
long: (int)(value ^ (value >>> 32)).
boolean: 1 или 0.
double: Double.hashCode(value).

public class Main {
    public static void main(String[] args) {
        long id = 4_000_000_000L;
        int longHash = (int) (id ^ (id >>> 32));
        System.out.println("long hash: " + longHash);
        System.out.println("double hash: " + Double.hashCode(3.14));
        System.out.println("bool hash: " + Boolean.hashCode(true));
    }
}

Хеширование массивов

Не вызывайте hashCode() непосредственно для массива: этот метод использует идентичность, а не содержимое.

Используйте Arrays.hashCode(arr) для обычного массива или Arrays.deepHashCode(arr) для вложенных массивов.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        System.out.println("identity equal: " + (a.hashCode() == b.hashCode()));
        System.out.println("content equal: " + (Arrays.hashCode(a) == Arrays.hashCode(b)));
    }
}

Согласованность equals и hashCode

Поля, используемые в hashCode(), должны быть подмножеством полей, используемых в equals() (в идеале — в точности теми же полями).

Если equals сравнивает больше полей, чем hashCode, два равных объекта всё равно имеют общий хеш-код. Это допустимо. Но если hashCode использует поле, которое игнорирует equals, контракт нарушается.

import java.util.Objects;

public class Main {
    static class Coord {
        final int x, y;
        Coord(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof Coord c && c.x == x && c.y == y;
        }
        @Override public int hashCode() { return Objects.hash(x, y); }
    }
    public static void main(String[] args) {
        Coord a = new Coord(3, 4), b = new Coord(3, 4);
        System.out.println(a.equals(b) && a.hashCode() == b.hashCode());
    }
}

Кэширование хеша

Для неизменяемых объектов с дорогостоящим вычислением хеша можно сохранить результат в поле.

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

import java.util.Objects;

public class Main {
    static final class Key {
        final String a, b;
        private int hash; // 0 until computed
        Key(String a, String b) { this.a = a; this.b = b; }
        @Override public int hashCode() {
            int h = hash;
            if (h == 0) { h = Objects.hash(a, b); hash = h; }
            return h;
        }
    }
    public static void main(String[] args) {
        Key k = new Key("x", "y");
        System.out.println(k.hashCode());
        System.out.println(k.hashCode());
    }
}

Распределение имеет значение

Хорошо распределённый hashCode равномерно распределяет ключи по корзинам. Посчитаем количество различных хеш-кодов для группы объектов.

Чем больше различных значений, тем меньше коллизий и тем быстрее работает map.

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Main {
    record Pair(int a, int b) {}
    public static void main(String[] args) {
        Set<Integer> hashes = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            hashes.add(Objects.hash(i, i * 7));
        }
        System.out.println("distinct hashes: " + hashes.size());
    }
}

Пример плохого распределения

Сложение полей без умножения приводит к коллизиям: (1,2) и (2,1) в обоих случаях дают хеш-код 3.

Множитель 31 нарушает эту симметрию, поскольку порядок полей начинает иметь значение.

public class Main {
    static int badHash(int a, int b) { return a + b; }
    static int goodHash(int a, int b) { return 31 * a + b; }
    public static void main(String[] args) {
        System.out.println("bad (1,2): " + badHash(1, 2) + ", (2,1): " + badHash(2, 1));
        System.out.println("good (1,2): " + goodHash(1, 2) + ", (2,1): " + goodHash(2, 1));
    }
}

Предпочитайте записи для типов-значений

Для объектов, служащих только контейнерами данных, record автоматически создаёт корректный и хорошо распределённый hashCode.

Пишите hashCode вручную только при необходимости нестандартной семантики или невозможности использовать запись.

public class Main {
    record Money(long cents, String currency) {}
    public static void main(String[] args) {
        Money a = new Money(1099, "USD");
        Money b = new Money(1099, "USD");
        System.out.println(a.equals(b));
        System.out.println(a.hashCode() == b.hashCode());
    }
}

Собираем всё вместе

Полный класс-значение: неизменяемые поля, equals и hashCode на основе одних и тех же полей и аккуратный toString.

import java.util.Objects;

public class Main {
    static final class Version {
        final int major, minor, patch;
        Version(int major, int minor, int patch) {
            this.major = major; this.minor = minor; this.patch = patch;
        }
        @Override public boolean equals(Object o) {
            return o instanceof Version v && v.major == major && v.minor == minor && v.patch == patch;
        }
        @Override public int hashCode() { return Objects.hash(major, minor, patch); }
        @Override public String toString() { return major + "." + minor + "." + patch; }
    }
    public static void main(String[] args) {
        Version v = new Version(2, 1, 0);
        System.out.println(v + " hash=" + v.hashCode());
    }
}

Быстрая проверка

Проверьте свои навыки работы с hashCode.

Итоги

Вы научились правильно реализовывать hashCode:

Используйте Objects.hash(...) в распространённом случае.
Применяйте шаблон с множителем 31 при написании хеширования вручную.
Хешируйте массивы с помощью Arrays.hashCode, а не используйте реализацию по умолчанию.
Согласовывайте поля hashCode с equals и предпочитайте записи.

Далее Вы узнаете, как Java 8+ преобразует переполненные корзины в деревья.

import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        System.out.println("hashCode recap done: " + Objects.hash("done"));
    }
}

Часто задаваемые вопросы

Урок «Реализация hashCode» бесплатный?

Да — полный текст урока «Реализация hashCode» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Реализация hashCode»?

Пишите корректные хеш-функции Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Реализация hashCode»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Как работает HashMap
Контракт equals/hashCode
Реализация hashCode
Преобразование в дерево и производительность

← Назад к Java Academy