Хэш-код объекта, hashcode

Implementing equals() and hashCode() method

We can define our own equals() and hashCode() method implementation but if we don’t implement them carefully, it can have weird issues at runtime. Luckily most of the IDE these days provide ways to implement them automatically and if needed we can change them according to our requirement.

We can use Eclipse to auto generate equals() and hashCode() methods.

Here is the auto generated equals() and hashCode() method implementations.

Notice that both equals() and hashCode() methods are using same fields for the calculations, so that their contract remains valid.

If you will run the test program again, we will get the object from map and program will print 10.

We can also use Project Lombok to auto generate equals and hashCode method implementations.

Java hashCode()

Java Object hashCode() is a native method and returns the integer hash code value of the object. The general contract of hashCode() method is:

• Multiple invocations of hashCode() should return the same integer value, unless the object property is modified that is being used in the equals() method.
• An object hash code value can change in multiple executions of the same application.
• If two objects are equal according to equals() method, then their hash code must be same.
• If two objects are unequal according to equals() method, their hash code are not required to be different. Their hash code value may or may-not be equal.

Требования к реализации equals() и hashCode()

Для поведения и существуют некоторые ограничения, которые указаны в документации по . В частности, метод должен обладать следующими свойствами:

• Симметричность: Для двух ссылок, и , тогда и только тогда, когда
• Рефлексивность: Для всех ненулевых ссылок,
• Транзитивность: Если и , то тогда
• Совместимость с : Два тождественно равных объекта должны иметь одно и то же значение

В спецификации представлено смутное описание принципа, согласно которому и являются совместимыми — их результаты будут одинаковы для последующих применений, из чего следует, что «не используется никакой информации при сравнении измененных объектов на тождество.» Это звучит, как «результат вычисления не должен изменяться, если только он не изменяется.» Чаще всего такое смутное утверждение, трактуется как тождество и вычисления значений хеширования должны являться детерминированными функциями свойства объекта и ничем иным.

When to override equals() and hashCode() methods?

When we override equals() method, it’s almost necessary to override the hashCode() method too so that their contract is not violated by our implementation.

Note that your program will not throw any exceptions if the equals() and hashCode() contract is violated, if you are not planning to use the class as Hash table key, then it will not create any problem.

If you are planning to use a class as Hash table key, then it’s must to override both equals() and hashCode() methods.

Let’s see what happens when we rely on default implementation of equals() and hashCode() methods and use a custom class as HashMap key.

When we run above program, it will print . It’s because Object hashCode() method is used to find the bucket to look for the key. Since we don’t have access to the HashMap keys and we are creating the key again to retrieve the data, you will notice that hash code values of both the objects are different and hence value is not found.

Описание тождества

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

Семантика для данного класса перекладывается на конструктор. Описание того, что для данного класса означает , является частью проектирования самого класса. Реализация по умолчанию, предоставленная классом , является просто тождеством ссылок:

  public boolean equals(Object obj) { 
    return (this == obj); 
  }

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

Простой пример замены equals()

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

  public boolean equals(Object obj) {
    return (obj instanceof Integer 
            && intValue() == ((Integer) obj).intValue());
  }

В данном описании два объекта тождественны, только если они содержат одно и тот же целочисленное значение. Все это, а также и неизменность , приводит к тому, что практично использовать в качестве ключа в . Такой характеризуемый значением подход к тождеству используется всеми элементарными классами-оболочками в библиотеке классов языка Java, например , , и , а также (два объекта тождественны, если они содержат одну и ту же последовательность символов). Благодаря тому, что все эти классы неизменны и корректно реализуют и , все они являются хорошими ключами хеширования.

Зачем изменять equals() и hashCode()?

Что случится, если не изменяет и ? Ничего, но только при условии, что мы никогда не использовали в качестве ключа в или других наборах на базе хеширования. Однако, если бы мы использовали такой объект в качестве ключа в , то мы смогли бы надежно получать соответствующее значение, если только мы не использовали тот же самый в вызове , как мы делали это в вызове . Для этого требуется удостовериться, что во всей нашей программе мы использовали только один объект , отвечающий конкретному целочисленному значению. Разумеется, этот подход неудобен и подвержен ошибкам.

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

Разработчики архитектуры Java предвидели всю важность классов-наборов на базе хеширования — например , и — для типичных Java-платформ, а сравнение нескольких объектов при помощи , может быть достаточно затратным с точки зрения вычислительных ресурсов. Наличие поддержки каждым объектом Java позволяет эффективно хранить и извлекать их с помощью наборов на базе хеширования.

e·qual

(ē′kwəl)
adj.
1. Having the same quantity, measure, or value as another.

2. Mathematics Being the same or identical to in value.

3.
a. Having the same privileges, status, or rights:

b. Being the same for all members of a group:

4.
a. Having the requisite qualities, such as strength or ability, for a task or situation:

b. Similar to or the same as another, as in ability:

n. One that is equal to another:

tr.v. e·qualed, e·qual·ing, e·quals or e·qualled or e·qual·ling
1. To be equal to, especially in value.

2. To do, make, or produce something equal to:

[Middle English, from Latin aequālis, from aequus, even, level.]

e′qual·ly adv.

Usage Note: It has been argued that equal is an absolute term—two quantities either are or are not equal—and hence cannot be qualified as to degree. Therefore one cannot logically speak of a more equal allocation of resources among the departments. But this usage is fairly common, and was acceptable to 71 percent of the Usage Panel as far back as 1967. Objections to the more equal construction assume that the mathematical notion of equality is appropriate to the description of a world where the equality of two quantities is often an approximate matter, and where statements of equality are always relative to an implicit standard of tolerance. In The two boards are of equal length, we assume that the equality is reckoned to some order of approximation determined by the context; if we did not, we would be required always to use nearly equal when speaking of the dimensions of physical objects. What is more, we often speak of the equality of things that cannot be measured quantitatively, as in The college draft was introduced in an effort to make the teams in the National Football League as equal as possible, or The candidates for the job should all be given equal consideration. In such cases, equality is naturally a gradient notion and can be modified in degree. This much is evident from the existence of the word unequal, for the prefix un- attaches only to gradient adjectives. We say unmanly but not unmale; and the word uneven can be applied to a surface (whose evenness may be a matter of degree) but not to a number (whose evenness is an either/or affair). · The adverb equally is often regarded as redundant when used in combination with as, as in Experience is equally as valuable as theory or Aptitude is essential; but equally as important is the desire to learn. In our 2015 ballot, the example sentences above were deemed unacceptable by 64 percent and 53 percent of the Usage Panel respectively. Even among those Panelists who rated the sentences as acceptable, there were several who commented that it would be preferable to avoid the redundancy for stylistic reasons. Fortunately, one can easily streamline sentences such as these, as by deleting equally from the first example and as from the second. See Usage Notes at absolute, as1, center, perfect, unique.

e•qual

(ˈi kwəl) adj., n., v. e•qualed, e•qual•ingesp. Brit.e•qualled, e•qual•ling.adj. 1. as great as; the same as (often fol. by to or with).
2. like or alike in quantity, degree, value, etc.
3. of the same rank, ability, merit, etc.:
4. evenly proportioned or balanced:
5. uniform in operation or effect:
6. adequate or sufficient in quantity or degree.
7. having adequate ability or means; suited:
8. level, as a plain.
9. tranquil or undisturbed.
10. impartial or equitable.
n. 11. a person or thing that is equal.
v.t. 12. to be or become equal to; meet or match, as in value.
13. to make or do something equal to:
14. Archaic. to make equal; equalize.
15. Obs. to recompense fully.
[1350–1400; < Latin aequālis equal, like]
usage: See unique.

What is Hash Collision

In very simple terms, Java Hash table implementations uses following logic for get and put operations.

1. First identify the “Bucket” to use using the “key” hash code.
2. If there are no objects present in the bucket with same hash code, then add the object for put operation and return null for get operation.
3. If there are other objects in the bucket with same hash code, then “key” equals method comes into play.
   • If equals() return true and it’s a put operation, then object value is overridden.
   • If equals() return false and it’s a put operation, then new entry is added to the bucket.
   • If equals() return true and it’s a get operation, then object value is returned.
   • If equals() return false and it’s a get operation, then null is returned.

Below image shows a bucket items of HashMap and how their equals() and hashCode() are related.

The phenomenon when two keys have same hash code is called hash collision. If hashCode() method is not implemented properly, there will be higher number of hash collision and map entries will not be properly distributed causing slowness in the get and put operations. This is the reason for prime number usage in generating hash code so that map entries are properly distributed across all the buckets.

Java equals()

Object class defined equals() method like this:

According to java documentation of equals() method, any implementation should adhere to following principles.

• For any object x, should return .
• For any two object x and y, should return if and only if returns .
• For multiple objects x, y, and z, if returns and returns , then should return .
• Multiple invocations of should return same result, unless any of the object properties is modified that is being used in the method implementation.
• Object class equals() method implementation returns only when both the references are pointing to same object.