Как написать hashcode java

Время на прочтение
4 мин

Количество просмотров 46K

Часто на собеседованиях приходится спрашивать про функцию hashCode().
Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией equals(). Данная информация есть во всех учебниках по Java и я не вижу смысла ее здесь повторять. Мне бы хотелось остановиться лишь на одном свойстве: hashCode должен быть равномерно распределен на области значений функции. Я задумался: “А чем гарантировано равномерное распределение?”

Забегая вперед, скажу, что я пришел к довольно интересным выводам. Мне бы хотелось, чтобы меня поправили, если я где-то ошибся в рассуждениях.

Спросим у Гуру

Вначале я решил обратиться к Java документации на Object.hashCode(). Как каждый может убедиться, там нет информации, которая нас интересует. После этого я пошел к Гуру. Брюс Эккель написал 5 страниц, кивнул на Блоха (точнее списал у него), привел пример со строками, а в конце посоветовал использовать “полезные библиотеки”. Джошуа Блох поступил лучше: он предложил алгоритм вычисления, высказался о пользе простых чисел и… тоже привел пример. Я не могу не удержаться от цитирования:

The multiplier 37 was chosen because it is an odd prime. … The advantages of using a prime number are less clear, but it is traditional to use primes for this purpose.

Никто из авторов не удосужился провести анализ приведенного алгоритма и доказать его корректность.

Алгоритм (в вольном пересказе)

1) Взять число, отличное от нуля, к примеру 17. Для удобства, назовем его p. Присвоить переменной result это начальное значение (result = p).
2) Для каждого поля вычислить hashCode c по некоторым правилам. Эти правила, нас сейчас не очень интересуют, они не влияют на результат. Для простоты будем работать с целыми числами (int) и будем принимать hashCode равным самому значению числа…
3) Скомбинировать result и полученный hashCode с: result = result * q + c, где q = 37, потому что, как мы помним, оно нечетное и простое.
4) Вернуть result.

Анализ алгоритма

Сначала сделаем несколько допущений:
1) Как уже сказано выше, будем работать с целыми числами.
2) Будем считать, что hashCode принимает значения от 0 до 2³². То есть мы не будем работать с отрицательными значениями.
3) Будем считать, что переполнения при умножении и сложении не происходит. Будем использовать только небольшие исходные значения.
4) Будем считать, что данные, на основании которых строится hashCode распределены, равномерно.

Чтобы быть более конкретным, я стану рассматривать точки с целочисленными координатами (x, y) на плоскости в двухмерном пространстве, при условии, что x>= 0, y>=0.

Запишем hash функцию для точки P1 (x1, y1):

(p*q + x1)*q + y1 = h

h — значение hash функции.
Теперь я хочу рассмотреть какую-нибудь другую точку P2(x2, y2) у которой будет такая же hash функция. То есть это как раз случай коллизии:

(p*q + x2)*q + y2 = h

Вычтем из первого выражение второе:

q(x1-x2) + y1 — y2 = 0 (Обратите внимание, что множитель, содержащий p пропал после вычитания)

Вынесем q в правую часть:

(x1 — x2) / (y2-y1) = q (понятно, что знаменатель должен быть отличен от нуля)

Если подобрать такие значения x1, x2, y1, y2, что выполнится полученное равенство, то эти координаты будут соответствовать значениям аргумента hash функции, при которой возникнет коллизия.

Можно предложить такой вариант:

x1 = 38
x2 = 1
y2= 2
y1 = 1

То есть точки P(38, 1) и P(1, 2) имеют одинаковый hashCode… Я думал, что имея 4 миллиарда возможных значений для hash кода, можно было бы избежать коллизий хотя бы в квадрате 100×100!

Теперь рассмотрим случай n переменных, независимо изменяющихся от 0 до некоторого M. Хотелось бы найти максимальное значение M, такое, что хорошо написанная функция hashCode не имела бы коллизий на промежутке от 0 до M по всем n переменным. После недолгих раздумий, получаем значение для M:

Для случая точек на плоскости M принимает значение 65536.

Похоже, что формула, приведенная Блохом, будет давать приемлемое распределение hash кодов для случая 8 и более переменных.

Рассмотрим теперь точки в трехмерном пространстве. Напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до 100 (всего миллион точек) и считает количество коллизий. Код этой программы элементарный, поэтому не буду его здесь приводить. Интересен результат: я получил 901692 коллизий! То есть чуть более, чем 90%. Получается, что Блох, под видом hash функции, предложил функцию для получения коллизий?

Хороший hashCode для случая двух переменных

Теперь попробуем построить хороший алгоритм для случая двух переменных (x1, y1). Чтобы равномерно раскидать значения x1 и y1 на числовой плоскости, воспользуемся умножением: умножим x1 на некоторое число p, а y1 — на q. Пока не будем накладывать на p и q никаких условий. Для получения значения hash функции, сложим эти произведения:

p*x1+q*y1=h

Воспользуемся приёмом, описанным выше: найдем x2, y2, такие, что значение hash функции выдаст коллизию.

p*x2+q*y2=h

Вычтем из первого равенства второе:

p*(x1-x2) + q(y1-y2) = 0
или
(x1-x2)/(y2-y1)=q/p (при условии, что знаменатель не равен нулю)

Если q взять равным 37, а p — 1, то получим формулу от Блоха.
Из последней формулы и из того факта, что мы работаем с целыми числами, следует:
1) Разность (x1-x2) пропорциональна q, разность (y2-y1) пропорциональна p.
2) Чем больше p и q, тем больше может быть расстояние между точками.
3) p и q должны быть взаимно простыми.
4) Имея верхнее ограничение на h=2³², получаем, что каждое из произведений p*x1, q*y1 должны быть меньше, чем 2³²/2. Отсюда следует, что p и q должны быть меньше 32768. К примеру 32765 и 32767 Тут следует напомнить о нашем допущении: мы работаем только с положительными числами. Когда произойдет переполнение при сложении, мы окажемся в отрицательной части числовой оси. Предлагаю читателям поразмыслить над этим самостоятельно

Выводы

Как писал Дональд Кнут в главе про генератор псевдослучайных последовательностей, если алгоритм выглядит сложно и запутанно, это еще не означает, что он работает правильно (недословное изложение).

Те кто используют реализацию hash функции от Джошуа Блоха, но имеют большое количество хешируемых переменных, могут спать спокойно. Так же могут не волноваться те, у кого различного рода Hash-коллекции не являются узким местом в производительности.

Если же вы бьетесь за производительность своего кода, учитываете все возможные мелочи, то вам, пожалуй, следует взглянуть на свои реализации hashCode() свежим взглядом. Учитывая, что хешируемые значения, могут быть не равномерно распределены для вашей конкретной бизнес области, вы сможете написать hash функцию с лучшим распределением hash кодов, чем любой сгенерированный вариант. Переписав hashCode(), вам, возможно, следует взглянуть на equals(): может быть вы сможете меньшим числом проверок вернуть значение false.

Спасибо тем, кто дочитал до конца.

Литература:
Bruce Eckel “Thinking in Java Third Edition”
Joshua Bloch “Effective Java: Programming Language Guide”

В классе Object, который является родительским классом для объектов java, определен метод hashCode(),
позволяющий получить уникальный целый номер для данного объекта. Когда объект сохраняют в коллекции типа
HashSet, то данный номер позволяет быстро определить его местонахождение в коллекции и
извлечь. Функция hashCode() объекта Object возвращает целое число int, размер которого равен 4-м
байтам и значение которого располагается в диапазоне от -2 147 483 648 до 2 147 483 647.

Рассмотрим простой пример HashCodeTest.java, который в консоли будет печатать значение hashCode.

public class HashCodeTest
{
    public static void main(String[] args)
    {
        int hCode = (new Object()).hashCode();
        System.out.println("hashCode = " + hCode);
    }
}

Значение hashCode программы можно увидеть в консоли.

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

Функция сравнения объектов equals()

В родительском классе Object наряду с функцией hashCode() имеется еще и логическая функция
equals(Object)/ Функция equals(Object) используется для проверки равенства двух объектов. Реализация
данной функции по умолчанию просто проверяет по ссылкам два объекта на предмет их эквивалентности.

Рассмотрим пример сравнения двух однотипных объектов Test следующего вида :

class Test
{
    int f1 = -1;
    int f2 = -1;

    public Test (final int f1, final int f2)
    {
        this.f1 = f1;
        this.f2 = f2;
    }
    public int getF1()
    {
        return this.f1;
    }
    public int getF2()
    {
        return this.f2;
    }
}

Создадим 2 объекта типа Test с одинаковыми значениями и сравним объекты с использованием функции equals().

public class EqualsExample
{
    public static void main(String[] args)
    {
        Test obj1 = new Test(11, 12);
        Test obj2 = new Test(11, 12);
        System.out.println("Объекты :ntobj1 = " + obj1 + 
                                    "ntobj2 = " + obj2);
        System.out.println("hashCode объектов :" +
                               "ntobj1.hashCode = " + obj1.hashCode() + 
                               "ntobj2.hashCode = " + obj2.hashCode());
        System.out.println("Сравнение объектов :" +
                          "ntobj1.equals(obj2) = " + obj1.equals(obj2));
    }
}

Результат выполнения программы будет выведен в консоль :

Объекты :
    obj1 = example.Test@780324ff
    obj2 = example.Test@16721ee7
hashCode объектов :
    obj1.hashCode = 2013471999
    obj2.hashCode = 376577767
Сравнение объектов :
    obj1.equals(obj2) = false
 

Не трудно было догадаться, что результат сравнения двух объектов вернет «false». На самом деле, это не совсем верно,
поскольку объекты идентичны и в real time application метод должен вернуть true. Чтобы достигнуть этого корректного
поведения, необходимо переопределить метод equals() объекта Test.

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

    Test other = (Test) obj;
    if (f1 != other.getF1())
        return false;
    else if (f2 != other.getF2())
        return false;
    return true;
}

Вот теперь функция сравнения equals() возвращает значение «true». Достаточно ли этого? Попробуем добавить
объекты в коллекцию HashSet и посмотрим, сколько объектов будет в коллекции? Для этого в в метод main
примера EqualsExample добавим следующие строки :

Set<Test> objects = new HashSet<Test>();
objects.add(obj1);
objects.add(obj2);

System.out.println("Коллекция :nt" + objects);

Однако в коллекции у нас два объекта.

Коллекция :
	[example.Test@780324ff, example.Test@16721ee7]
 

Поскольку Set содержит только уникальные объекты, то внутри HashSet должен быть только один экземпляр. Чтобы
этого достичь, объекты должны возвращать одинаковый hashCode. То есть нам необходимо переопределить также
функцию hashCode() вместе с equals().

@Override
public int hashCode()
{
    final int prime = 31;
    int result = 1;
    result = prime * result + f1;
    result = prime * result + f2;
    return result;
}

Вот теперь все будет корректно выполняться — для двух объектов с одинаковыми параметрами функция
equals() вернет значение «true», и в коллекцию попадет только один объект. В консоль будет
выведен следующий текст работы программы :

Объекты :
	obj1 = example.Test@696
	obj2 = example.Test@696
hashCode объектов :
	obj1.hashCode = 1686
	obj2.hashCode = 1686
Сравнение объектов :
	obj1.equals(obj2) = true
Коллекция :
	[example.Test@696]
 

Таким образом, переопределяя методы hashCode() и equals() мы можем корректно управлять
нашими объектами, не допуская их дублирования.

Использование библиотеки commons-lang.jar для переопределения hashCode() и equals()

Процесс формирования методов hashCode() и equals() в IDE Eclipse автоматизирован. Для создания данных
методов необходимо правой клавишей мыши вызвать контекстное меню класса (кликнуть на классе) и выбрать пункт меню
Source (Class >> Source), в результате которого будет открыто следующее окно со списком меню для класса.

Выбираем пункт меню «Generate hachCode() and equals()» и в класс будут добавлены соответствующие методы.

@Override
public int hashCode()
{
    final int prime = 31;
    int result = 1;
    result = prime * result + f1;
    result = prime * result + f2;
    return result;
}

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

    Test other = (Test) obj;
    if (f1 != other.f1)
        return false;
    if (f2 != other.f2)
        return false;
    return true;
}

Библиотека Apache Commons включает два вспомогательных класса HashCodeBuilder и
EqualsBuilder для вызова методов hashCode() и equals(). Чтобы включить их в класс
необходимо внести следующие изменения.

import org.apache.commons.lang.builder.EqualsBuilder;
import org.apache.commons.lang.builder.HashCodeBuilder;

 ...
@Override
public int hashCode()
{
    final int prime = 31;
    return new HashCodeBuilder(getF1()%2 == 0 ? 
                                        getF1() + 1 : 
                                        getF1(), prime).toHashCode();
}

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

    Test other = (Test) obj;
    return new EqualsBuilder().append(getF1(),other.getF1()).isEquals();
}

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

Скачать пример

Исходный код рассмотренного примера в виде проекта Eclipse можно
скачать здесь (263 Kб).

At SitePoint we’re always looking to expand the range of topics we cover. Lately, we’ve set our sights on exploring the world of Java. If you’re a strong Java developer who wants to contribute to our coverage, get in touch with a few ideas for articles you’d like to write.

So you’ve decided that identity isn’t enough for you and wrote a nice equals implementation?
Great! But now you have to implement hashCode as well.

Let’s see why and how to do it correctly.

Equality and Hash Code

While equality makes sense from a general perspective, hash codes are much more technical. If we were being a little hard on them, we could say that they are just an implementation detail to improve performance.

Most data structures use equals to check whether they contain an element. For example:

List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

The variable contains is true because, while instances of "b" are not identical (again, ignoring String interning), they are equal.

Comparing every element with the instance given to contains is wasteful, though, and a whole class of data structures uses a more performant approach. Instead of comparing the requested instance with each element they contain, they use a shortcut that reduces the number of potentially equal instances and then only compare those.

This shortcut is the hash code, which can be seen as an object’s equality boiled down to an integer value. Instances with the same hash code are not necessarily equal but equal instances have the same hash code. (Or should have, we will discuss this shortly.) Such data structures are often named after this technique, recognizable by the Hash in their name, with HashMap the most notable representative.

This is how they generally work:

• When an element is added, its hash code is used to compute the index in an internal array (called a bucket).
• If other, non-equal elements have the same hash code, they end up in the same bucket and must be bundled together, e.g. by adding them to a list.
• When an instance is given to contains, its hash code is used to compute the bucket. Only elements therein are compared to the instance.

This way, very few, ideally no equals comparisons are required to implement contains.

As equals, hashCode is defined on Object.

Thoughts on Hashing

If hashCode is used as a shortcut to determine equality, then there is really only one thing we should care about: Equal objects should have the same hash code.

This is also why, if we override equals, we must create a matching hashCode implementation! Otherwise things that are equal according to our implementation would likely not have the same hash code because they use Object‘s implementation.

The hashCode Contract

Quoting the source:

The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

The first bullet mirrors the consistency property of equals and the second is the requirement we came up with above. The third states an important detail that we discuss will in a moment.

Implementing hashCode

A very easy implementation of Person.hashCode is the following:

@Override
public int hashCode() {
    return Objects.hash(firstName, lastName);
}

The person’s hash code is computed by computing the hash codes for the relevant fields and combining them. Both is left to Objects‘ utility function hash.

Selecting Fields

But which fields are relevant? The requirements help answer this: If equal objects must have the same hash code, then hash code computation should not include any field that is not used for equality checks. (Otherwise two objects that only differ in those fields would be equal but have different hash codes.)

So the set of fields used for hashing should be a subset of the fields used for equality. By default both will use the same fields but there are a couple of details to consider.

Consistency

For one, there is the consistency requirement. It should be interpreted rather strictly. While it allows the hash code to change if some fields change (which is often unavoidable with mutable classes), hashing data structures are not prepared for this scenario.

As we have seen above the hash code is used to determine an element’s bucket. But if the hash-relevant fields change, the hash is not recomputed and the internal array is not updated.

This means that a later query with an equal object or even with the very same instance fails! The data structure computes the current hash code, different from the one used to store the instance, and goes looking in the wrong bucket.

Conclusion: Better not use mutable fields for hash code computation!

Performance

Hash codes might end up being computed about as often as equals is called. This can very well happen in performance critical parts of the code so it makes sense to think about performance. And unlike equals there is a little more wiggle room to optimize it.

Unless sophisticated algorithms are used or many, many fields are involved, the arithmetic cost of combining their hash codes is as negligible as it is unavoidable. But it should be considered whether all fields need to be included in the computation! Particularly collections should be viewed with suspicion. Lists and sets, for example, will compute the hash for each of their elements. Whether calling them is necessary should be considered on a case-by-case basis.

If performance is critical, using Objects.hash might not be the best choice either because it requires the creation of an array for its varargs.

But the general rule about optimization holds: Don’t do it prematurely! Use a common hash code algorithm, maybe forego including the collections, and only optimize after profiling showed potential for improvement.

Collisions

Going all-in on performance, what about this implementation?

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

It’s fast, that’s for sure. And equal objects will have the same hash code so we’re good on that, too. As a bonus, no mutable fields are involved!

But remember what we said about buckets? This way all instances will end up in the same! This will typically result in a linked list holding all the elements, which is terrible for performance. Each contains, for example, triggers a linear scan of the list.

So what we want is as few items in the same bucket as possible! An algorithm that returns wildly varying hash codes, even for very similar objects, is a good start.

How to get there partly depends on the selected fields. The more details we include in the computation, the more likely it is for the hash codes to differ. Note how this is completely opposite to our thoughts about performance. So, interestingly enough, using too many or too few fields can result in bad performance.

The other part to preventing collisions is the algorithm that is used to actually compute the hash.

Computing The Hash

The easiest way to compute a field’s hash code is to just call `hashCode` on it. Combining them could be done manually. A common algorithm is to start with some arbitrary number and to repeatedly multiply it with another (often a small prime) before adding a field’s hash:

int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

This might result in overflows, which is not particularly problematic because they cause no exceptions in Java.

Note that even great hashing algorithms might result in uncharacteristically frequent collisions if the input data has specific patterns. As a simple example assume we would compute the hash of points by adding their x and y-coordinates. May not sound too bad until we realize that we often deal with points on the line f(x) = -x, which means x + y == 0 for all of them. Collisions, galore!

But again: Use a common algorithm and don’t worry until profiling shows that something isn’t right.

Summary

We have seen that computing hash codes is something like compressing equality to an integer value: Equal objects must have the same hash code and for performance reasons it is best if as few non-equal objects as possible share the same hash.

This means that hashCode must always be overridden if equals is.

When implementing hashCode:

• Use a the same fields that are used in equals (or a subset thereof).
• Better not include mutable fields.
• Consider not calling hashCode on collections.
• Use a common algorithm unless patterns in input data counteract them.

Remember that hashCode is about performance, so don’t waste too much energy unless profiling indicates necessity.