Использование пользовательского класса в качестве ключа в Java HashMap

1. Обзор

В этой статье мы узнаем, как HashMap внутренне управляет парами ключ-значение и как писать собственные реализации ключей.

2. Управление ключами

2.1. Внутренняя структура

Карты используются для хранения значений, назначенных ключам. Ключ используется для идентификации значения на карте и для обнаружения дубликатов.

В то время как TreeMap использует метод Comparable#compareTo(Object) для сортировки ключей (а также для определения равенства), HashMap использует структуру на основе хэша, которую легче объяснить с помощью быстрого наброска:

Карта не допускает дублирования ключей, поэтому ключи сравниваются друг с другом с помощью метода Object #equals(Object) . Поскольку этот метод имеет низкую производительность, следует по возможности избегать вызовов. Это достигается с помощью метода Object#hashCode() . Этот метод позволяет сортировать объекты по их хеш-значениям, а затем метод Object#equals нужно вызывать только тогда, когда объекты имеют одно и то же хеш-значение.

Этот тип управления ключами также применяется к классу HashSet , реализация которого использует HashMap внутри.

2.2. Вставка и поиск пары ключ-значение

Давайте создадим пример HashMap простого магазина, который управляет количеством товаров на складе ( Integer ) по идентификатору статьи ( String ). Там мы вводим примерное значение:

Map<String, Integer> items = new HashMap<>();
// insert
items.put("158-865-A", 56);
// find
Integer count = items.get("158-865-A");

Алгоритм вставки пары ключ-значение:

1. вызывает «158-865-A».hashCode() , чтобы получить хеш-значение

2. ищет список существующих ключей, которые имеют одно и то же значение хеш-функции

3. сравнивает любой ключ из списка с «158-865-A».equals(key)

4. Первое равенство идентифицируется как уже существующее, а новое заменяет присвоенное значение.

5. Если равенства нет, пара ключ-значение вставляется как новая запись.

Алгоритм поиска значения тот же, за исключением того, что значение не заменяется и не вставляется.

3. Пользовательские ключевые классы

Мы можем сделать вывод, что для использования пользовательского класса для ключа необходимо, чтобы hashCode() и equals() были реализованы правильно . Проще говоря, мы должны убедиться, что метод hashCode() возвращает:

• одно и то же значение для объекта, пока состояние не меняется ( внутренняя согласованность )
• одно и то же значение для объектов, которые равны ( Equals Consistency )
• как можно больше различных значений для объектов, которые не равны.

Обычно мы можем сказать, что hashCode() и equals() должны учитывать одни и те же поля в своих вычислениях, и мы должны переопределить оба или ни одно из них. Мы можем легко добиться этого, используя Lombok или генератор нашей IDE.

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

У неизменяемости здесь есть преимущество: хеш-значение может быть вычислено один раз при создании экземпляра объекта, что может повысить производительность, особенно для сложных объектов.

3.1. Хороший пример

В качестве примера мы создадим класс Coordinate , состоящий из значений x и y , и будем использовать его в качестве ключа в HashMap :

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
pixels.put(coord, Color.CYAN);
// read the color
Color color = pixels.get(new Coordinate(1, 2));

Давайте реализуем наш класс координат :

public class Coordinate {
    private final int x;
    private final int y;
    private int hashCode;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
        this.hashCode = Objects.hash(x, y);
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Coordinate that = (Coordinate) o;
        return x == that.x && y == that.y;
    }

    @Override
    public int hashCode() {
        return this.hashCode;
    }
}

В качестве альтернативы мы могли бы сделать наш класс еще короче, используя Lombok:

@RequiredArgsConstructor
@Getter
// no calculation in the constructor, but
// since Lombok 1.18.16, we can cache the hash code
@EqualsAndHashCode(cacheStrategy = CacheStrategy.LAZY)
public class Coordinate {
    private final int x;
    private final int y;
}

Оптимальной внутренней структурой будет:

3.2. Плохой пример: статическое хеш-значение

Если мы реализуем класс Coordinate , используя статическое хеш-значение для всех экземпляров, HashMap будет работать правильно, но производительность значительно снизится:

public class Coordinate {

    ...

    @Override
    public int hashCode() {
        return 1; // return same hash value for all instances
    }
}

Структура хеша выглядит следующим образом:

Это полностью сводит на нет преимущество хеш-значений.

3.3. Плохой пример: изменяемое хеш-значение

Если мы сделаем ключевой класс изменяемым, мы должны гарантировать, что состояние экземпляра никогда не изменится, пока он используется в качестве ключа:

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2); // x=1, y=2
pixels.put(coord, Color.CYAN);
coord.setX(3); // x=3, y=2

Поскольку координата хранится под старым хеш-значением, ее нельзя найти под новым. Итак, строка ниже приведет к нулевому значению:

Color color = pixels.get(coord);

И следующая строка приведет к тому, что объект будет дважды сохранен в Map :

pixels.put(coord, Color.CYAN);

4. Вывод

В этой статье мы пояснили, что реализация собственного класса ключей для HashMap — это вопрос правильной реализации equals() и hashCode() . Мы видели, как значение хеш-функции используется внутри и как это может быть затронуто как в хорошем, так и в плохом смысле.

Как всегда, код примера доступен на GitHub .