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. Лучшая реализация hashCode
При выборе хэш-функции необходимо учитывать два фактора: качество создаваемых хеш-кодов и скорость.
4.1. Измерение качества хэш-кода
Хеш-коды хранятся внутри переменных типа int , поэтому количество возможных хэшей ограничено емкостью типа int . Так и должно быть, потому что хэши используются для вычисления индексов массива с сегментами. Это означает, что существует также ограниченное количество ключей, которые мы можем хранить в HashMap без коллизии хэшей.
Чтобы избежать коллизий, насколько это возможно, мы хотим распределить хэши как можно более равномерно. Другими словами, мы хотим добиться равномерного распределения. Это означает, что каждое значение хеш-кода имеет такую же вероятность появления, как и любое другое.
Точно так же плохой метод hashCode будет иметь очень несбалансированное распределение. В самом худшем случае он всегда будет возвращать одно и то же число.
4.2. Хэш- код объекта по умолчанию ``
В общем, мы не должны использовать метод hashCode объекта по умолчанию, потому что мы не хотим использовать идентификатор объекта в методе equals . Однако в очень маловероятном сценарии, когда мы действительно хотим использовать идентификатор объекта для ключей в HashMap , функция hashCode по умолчанию будет работать нормально. В противном случае нам понадобится пользовательская реализация. [](/lessons/b/-java-map-key-byte-array)
4.3. Пользовательский хэш-код
Обычно мы хотим переопределить метод 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. Оно простое, дает хорошее распределение, оно маленькое, и умножение на него можно оптимизировать с помощью операции побитового сдвига:
31 * i == (i << 5) - i
Однако теперь, когда нам не нужно бороться за каждый цикл ЦП, можно использовать более крупные простые числа. Например, 524287 тоже можно оптимизировать:
524287 * i == i << 19 - i
И это может обеспечить хэш лучшего качества, что приведет к меньшей вероятности коллизии. Имейте в виду, что эти оптимизации битового сдвига выполняются JVM автоматически , поэтому нам не нужно запутывать ими наш код.
4.4. Класс полезности объектов
Алгоритм, который мы только что реализовали, хорошо зарекомендовал себя, и обычно нам не нужно каждый раз воссоздавать его вручную. Вместо этого мы можем использовать вспомогательный метод, предоставляемый классом Objects :
@Override
public int hashCode() {
return Objects.hash(id, name);
}
Под капотом он использует в точности описанный ранее алгоритм с числом 31 в качестве множителя.
4.5. Другие хеш-функции
Существует множество хэш-функций, которые обеспечивают меньшую вероятность коллизии, чем описанная ранее. Проблема в том, что они вычислительно тяжелее и, следовательно, не обеспечивают прирост скорости, который мы ищем.
Если по каким-то причинам нам очень нужно качество и мало заботит скорость, мы можем взглянуть на класс Hashing из библиотеки Guava :
@Override
public int hashCode() {
HashFunction hashFunction = Hashing.murmur3_32();
return hashFunction.newHasher()
.putInt(id)
.putString(name, Charsets.UTF_8)
.hash().hashCode();
}
Важно выбрать 32-битную функцию, потому что мы все равно не можем хранить более длинные хэши.
5. Вывод
HashMap в современной Java — это мощная и хорошо оптимизированная структура данных. Однако его производительность может ухудшиться из-за плохо спроектированного метода hashCode . В этом уроке мы рассмотрели возможные способы сделать хеширование быстрым и эффективным.
Как всегда, примеры кода для этой статьи доступны на GitHub .