«1. Введение

HashMap — это мощная структура данных, имеющая широкое применение, особенно когда требуется быстрое время поиска. Тем не менее, если мы не обращаем внимания на детали, это может стать неоптимальным.

В этом уроке мы рассмотрим, как максимально быстро сделать HashMap.

2. Узкое место HashMap

Оптимистическое постоянное время извлечения элемента HashMap (O(1)) обусловлено мощностью хеширования. Для каждого элемента HashMap вычисляет хэш-код и помещает элемент в корзину, связанную с этим хэш-кодом. Поскольку неравные объекты могут иметь одинаковые хэш-коды (явление, называемое конфликтом хэш-кодов), сегменты могут увеличиваться в размерах.

Сегмент на самом деле представляет собой простой связанный список. Поиск элементов в связанном списке не очень быстрый (O(n)), но это не проблема, если список очень маленький. Проблемы начинаются, когда у нас много коллизий хэш-кода, поэтому вместо большого количества маленьких сегментов у нас есть небольшое количество больших сегментов.

В худшем случае, когда мы помещаем все в одно ведро, наш HashMap понижается до связанного списка. Следовательно, вместо времени поиска O(1) мы получаем очень неудовлетворительное O(n).

3. Дерево вместо LinkedList

Начиная с Java 8, в HashMap встроена одна оптимизация: когда сегменты становятся слишком большими, они преобразуются в деревья вместо связанных списков. Это приводит пессимистическое время O (n) к O (log (n)), что намного лучше. Чтобы это работало, ключи HashMap должны реализовать интерфейс Comparable.

Это хорошее автоматическое решение, но оно не идеально. O(log(n)) по-прежнему хуже, чем желаемое постоянное время, а преобразование и хранение деревьев требует дополнительной мощности и памяти.

4. Лучшая реализация хэш-кода

При выборе хеш-функции необходимо учитывать два фактора: качество создаваемых хэш-кодов и скорость.

4.1. Измерение качества хэш-кода

Хэш-коды хранятся внутри переменных типа int, поэтому количество возможных хэшей ограничено емкостью типа int. Так и должно быть, потому что хэши используются для вычисления индексов массива с сегментами. Это означает, что существует также ограниченное количество ключей, которые мы можем хранить в HashMap без коллизии хэшей.

Чтобы избежать коллизий, насколько это возможно, мы хотим распределить хэши как можно более равномерно. Другими словами, мы хотим добиться равномерного распределения. Это означает, что каждое значение хеш-кода имеет такую ​​же вероятность появления, как и любое другое.

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

4.2. Хеш-код объекта по умолчанию

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

4.3. Custom hashCode

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

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

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithId that = (MemberWithId) o;

    return id.equals(that.id);
}

@Override
public int hashCode() {
    return id;
}

Это будет очень быстро и не вызовет коллизий. Наш HashMap будет вести себя так, как будто он имеет целочисленный ключ вместо сложного объекта.

Ситуация усложнится, если у нас будет больше полей, которые нам нужно учитывать. Допустим, мы хотим установить равенство как для id, так и для имени: 

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithIdAndName that = (MemberWithIdAndName) o;

    if (!id.equals(that.id)) return false;
    return name != null ? name.equals(that.name) : that.name == null;
}

Теперь нам нужно каким-то образом объединить хэши id и name.

Во-первых, мы получим такой же хэш id, как и раньше. Затем мы умножим его на какое-то тщательно выбранное число и добавим хэш имени: 

@Override
public int hashCode() {
    int result = id.hashCode();
    result = PRIME * result + (name != null ? name.hashCode() : 0);
    return result;
}

«

31 * i == (i << 5) - i

«Как выбрать это число — не простой вопрос, на который можно ответить достаточно. Исторически самым популярным числом было 31. Это простое число, оно дает хорошее распределение, оно мало, и умножение на него можно оптимизировать с помощью операции побитового сдвига: 

524287 * i == i << 19 - i

Однако теперь, когда мы не нужно бороться за каждый цикл процессора, можно использовать несколько больших простых чисел. Например, 524287 также можно оптимизировать:

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

4.4. Objects Utility Class 

@Override
public int hashCode() {
    return Objects.hash(id, name);
}

Алгоритм, который мы только что реализовали, хорошо зарекомендовал себя, и нам обычно не нужно каждый раз воссоздавать его вручную. Вместо этого мы можем использовать вспомогательный метод, предоставляемый классом Objects:

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

4.5. Другие хеш-функции

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

@Override
public int hashCode() {
    HashFunction hashFunction = Hashing.murmur3_32();
    return hashFunction.newHasher()
      .putInt(id)
      .putString(name, Charsets.UTF_8)
      .hash().hashCode();
}

Если по какой-то причине нам очень нужно качество и не важна скорость, мы можем взглянуть на класс Hashing из библиотеки Guava:

Важно выбрать 32-битную функцию, потому что мы все равно не можем хранить более длинные хэши.

5. Заключение

HashMap в современной Java — это мощная и хорошо оптимизированная структура данных. Однако его производительность может ухудшиться из-за плохо спроектированного метода hashCode. В этом уроке мы рассмотрели возможные способы сделать хеширование быстрым и эффективным.