Ръководство за hashCode () в Java

Програмиране

1. Общ преглед

Хеширането е основно понятие на компютърните науки.

В Java ефективните алгоритми за хеширане стоят зад някои от най-популярните колекции, които имаме на разположение - като HashMap (за задълбочен поглед към HashMap , не се колебайте да проверите тази статия) и HashSet.

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

2. Използване на hashCode () в Структурите на данни

Най-простите операции с колекции могат да бъдат неефективни в определени ситуации.

Например, това задейства линейно търсене, което е силно неефективно за списъци с огромни размери:

List words = Arrays.asList("Welcome", "to", "Baeldung"); if (words.contains("Baeldung")) { System.out.println("Baeldung is in the list"); }

Java предоставя редица структури от данни, за да се справи конкретно с този проблем - например, няколко реализации на интерфейса на Map са хеш таблици.

При използване на хеш-таблица, тези колекции изчисляват хеш стойност за даден ключ с помощта на хеш-код () метода и да използват тази стойност вътрешно, за да съхранявате данните - така, че операциите за достъп са много по-ефективни.

3. разбиране как хеш-код () Works

Най-просто казано, hashCode () връща целочислена стойност, генерирана от хеширащ алгоритъм.

Обектите, които са равни (според техните равни () ) трябва да връщат същия хеш код. Не се изисква различните обекти да връщат различни хеш кодове.

Общият договор на hashCode () гласи:

  • Винаги, когато той бъде извикан върху един и същ обект повече от веднъж по време на изпълнение на Java приложение, hashCode () трябва последователно да връща една и съща стойност, при условие че не се променя информация, използвана в сравнения на равни обекти. Тази стойност не трябва да остане последователна от едно изпълнение на приложение към друго изпълнение на същото приложение
  • Ако два обекта са равни според метода equals (Object) , тогава извикването на метода hashCode () за всеки от двата обекта трябва да доведе до една и съща стойност
  • Не се изисква, ако два обекта са неравни според метода equals (java.lang.Object) , тогава извикването на метода hashCode за всеки от двата обекта трябва да доведе до различни цели числа. Разработчиците обаче трябва да са наясно, че създаването на различни целочислени резултати за неравни обекти подобрява производителността на хеш таблици

„Колкото и да е разумно практично, методът hashCode () , дефиниран от клас Object , връща различни цели числа за отделни обекти. (Това обикновено се реализира чрез преобразуване на вътрешния адрес на обекта в цяло число, но тази техника на изпълнение не се изисква от езика за програмиране JavaTM.) “

4. Наивна реализация на hashCode ()

Всъщност е съвсем просто да има наивна реализация на hashCode (), която напълно се придържа към горния договор.

За да демонстрираме това, ще дефинираме примерен потребителски клас, който заменя изпълнението по подразбиране на метода:

public class User { private long id; private String name; private String email; // standard getters/setters/constructors @Override public int hashCode() { return 1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null) return false; if (this.getClass() != o.getClass()) return false; User user = (User) o; return id == user.id && (name.equals(user.name) && email.equals(user.email)); } // getters and setters here }

Класът User предоставя персонализирани реализации както за equals (), така и за hashCode (), които напълно се придържат към съответните договори. Дори нещо повече, няма нищо незаконно с това, че hashCode () връща някаква фиксирана стойност.

Тази реализация обаче влошава функционалността на хеш таблиците до нула, тъй като всеки обект ще се съхранява в една и съща единична група.

В този контекст търсенето на хеш таблица се извършва линейно и не ни дава никакво реално предимство - повече за това в раздел 7.

5. Подобряване на внедряването на hashCode ()

Нека подобрим малко текущата реализация на hashCode (), като включим всички полета от потребителския клас, така че да може да доведе до различни резултати за неравни обекти:

@Override public int hashCode() { return (int) id * name.hashCode() * email.hashCode(); }

Този основен алгоритъм за хеширане определено е много по-добър от предишния, тъй като изчислява хеш кода на обекта, като просто умножава хеш кодовете на полетата за име и имейл и id .

Като цяло можем да кажем, че това е разумно изпълнение на hashCode () , стига да поддържаме изпълнението на equals () в съответствие с него.

6. Стандартни реализации на hashCode ()

Колкото по-добър е алгоритъмът за хеширане, който използваме за изчисляване на хеш кодове, толкова по-добра ще бъде ефективността на хеш таблиците.

Нека да разгледаме „стандартна“ реализация, която използва две прости числа, за да добави още по-голяма уникалност към изчислените хеш кодове:

@Override public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); return hash; }

Въпреки че е от съществено значение да се разберат ролите, които играят методите hashCode () и equals () , не е нужно да ги прилагаме от нулата всеки път, тъй като повечето IDE могат да генерират персонализирани реализации на hashCode () и equals () и от Java 7, имаме полезен метод Objects.hash () за удобно хеширане:

Objects.hash(name, email)

IntelliJ IDEA генерира следното изпълнение:

@Override public int hashCode() { int result = (int) (id ^ (id >>> 32)); result = 31 * result + name.hashCode(); result = 31 * result + email.hashCode(); return result; }

И Eclipse произвежда това:

@Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((email == null) ? 0 : email.hashCode()); result = prime * result + (int) (id ^ (id >>> 32)); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; }

В допълнение към горните IDE-базирани реализации на hashCode () , възможно е също автоматично да се генерира ефективно изпълнение, например с помощта на Lombok. В този случай зависимостта lombok-maven трябва да бъде добавена към pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom

It's now enough to annotate the User class with @EqualsAndHashCode:

@EqualsAndHashCode public class User { // fields and methods here }

Similarly, if we want Apache Commons Lang's HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:

 commons-lang commons-lang 2.6

And hashCode() can be implemented like this:

public class User { public int hashCode() { return new HashCodeBuilder(17, 37). append(id). append(name). append(email). toHashCode(); } }

In general, there's no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch's Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.

What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:

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

7. Handling Hash Collisions

The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they're unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.

This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java's HashMap uses the separate chaining method for handling collisions:

“When two or more objects point to the same bucket, they're simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.

In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”

Hash collision methodologies show in a nutshell why it's so important to implement hashCode() efficiently.

Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).

8. Creating a Trivial Application

To test the functionality of a standard hashCode() implementation, let's create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.

Here's the sample application's entry point:

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); users.put(user1, user1); users.put(user2, user2); users.put(user3, user3); if (users.containsKey(user1)) { System.out.print("User found in the collection"); } } }

And this is the hashCode() implementation:

public class User { // ... public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); logger.info("hashCode() called - Computed hash: " + hash); return hash; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 User found in the collection

9. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

Както винаги, всички примери за кодове, показани в тази статия, са достъпни в GitHub.