Вступление

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

• нанизывать
• для класса
• равно
• hashCode (вы здесь)
• клон
• завершить
• ждать и уведомлять

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

Почему важен метод hashCode ()

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

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

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

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

Демонстрация использования хеш-таблицы

В Java концепция хеш-таблицы концептуализирована в интерфейсе java.util.Map и реализована в классе java.util.HashMap.

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

Person.java

 import java.time.LocalDate; 
 
 public class Person { 
 private final String firstName; 
 private final String lastName; 
 private final LocalDate dob; 
 
 public Person(String firstName, String lastName, LocalDate dob) { 
 this.firstName = firstName; 
 this.lastName = lastName; 
 this.dob = dob; 
 } 
 
 // omitting getters for brevity 
 
 @Override 
 public boolean equals(Object o) { 
 if (this == o) { 
 return true; 
 } 
 if (!(o instanceof Person)) { 
 return false; 
 } 
 Person p = (Person)o; 
 return firstName.equals(p.firstName) 
 && lastName.equals(p.lastName) 
 && dob.equals(p.dob); 
 } 
 } 

Main.java

 import java.time.LocalDate; 
 import java.util.HashMap; 
 import java.util.Map; 
 
 public class Main { 
 public static void main(String[] args) { 
 Map<Person, String> peopleMap = new HashMap<>(); 
 Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23")); 
 Person me2 = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23")); 
 System.out.println("Default hash: " + me.hashCode()); 
 System.out.println("Default hash: " + me2.hashCode()); 
 
 peopleMap.put(me, me.toString()); 
 System.out.println("me and me2 same? " + me.equals(me2)); 
 System.out.println("me2 in here? " + peopleMap.containsKey(me2)); 
 } 
 } 

Выход:

 Default hash: 1166726978 
 Default hash: 95395916 
 me and me2 same? true 
 me2 in here? false 

Как видно из выходных данных, хеш-значения по умолчанию для me и me2 не равны, хотя пользовательская реализация equals(Object) указывает, что они логически одинаковы. Это приводит к появлению двух отдельных записей в хеш-таблице, даже если вы ожидаете только одну, что открывает двери для некоторых неприятных ошибок в программе, если она будет реализовывать этот код.

Позвольте мне улучшить Person , убедившись, что метод hashCode() возвращает одно и то же значение для одинаковых объектов экземпляра me и me2 , например:

Person.java

 public class Person { 
 // omitting all other stuff for brevity 
 
 @Override 
 public int hashCode() { 
 return 31; 
 } 
 } 

Main.java

 public class Main { 
 public static void main(String[] args) { 
 Map<Person, String> peopleMap = new HashMap<>(); 
 Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23")); 
 Person me2 = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23")); 
 Person you = new Person("Jane", "Doe", LocalDate.parse("1999-12-25")); 
 System.out.println("Default hash: " + me.hashCode()); 
 System.out.println("Default hash: " + me2.hashCode()); 
 
 peopleMap.put(me, me.toString()); 
 System.out.println("me and me2 same? " + me.equals(me2)); 
 System.out.println("me2 in here? " + peopleMap.containsKey(me2)); 
 
 peopleMap.put(me2, me2.toString()); 
 peopleMap.put(you, you.toString()); 
 for(Person p : peopleMap.keySet()) { 
 String txt = peopleMap.get(p); 
 System.out.println(txt); 
 } 
 } 
 } 

Выход:

 Default hash: 31 
 Default hash: 31 
 me and me2 same? true 
 me2 in here? true 
 <Person: firstName=Adam, lastName=McQuistan, dob=1987-09-23> 
 <Person: firstName=Jane, lastName=Doe, dob=1999-12-25> 

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

Сначала я объясню, что происходит, когда в HashMap добавляются me и me2 Когда me2 Person добавляется к HashMap, уже содержащему me , HashMap замечает, что хэш такой же, а затем определяет, что они также логически эквивалентны с помощью метода equals(Object) Это приводит к тому, что HashMap просто заменяет первое me вторым me2 в этом месте хеш-таблицы.

Затем идет you , который снова имеет то же значение хэша, но на этот раз HashMap идентифицирует, что он логически отличается от существующего хэша в этом me2 . Это приводит к тому, что HashMap добавляет you в корзину, превращая эту корзину в коллекцию в виде списка. Для небольшого количества коллизий это не оказывает слишком большого влияния, но в моем примере выше, где каждый экземпляр гарантированно имеет одно и то же значение хеш-функции, сегмент, представляющий 31 в HashMap, быстро ухудшится до плохой реализации списка. для всего HashMap.

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

Ниже приведена программа, которая создает две коллекции одинакового размера, peopleList и peopleMap , Person с одинаковыми случайными именами и выбранными днями рождения. Я измерю количество времени, необходимое для создания коллекций для первого сравнительного измерения. Затем я измерю количество времени, необходимое для поиска каждой коллекции на предмет существования одинаково размещенного известного экземпляра, me .

 import java.time.Duration; 
 import java.time.LocalDate; 
 import java.time.LocalDateTime; 
 import java.util.ArrayList; 
 import java.util.Arrays; 
 import java.util.HashMap; 
 import java.util.List; 
 import java.util.Map; 
 import java.util.Random; 
 import java.util.stream.Collectors; 
 
 public class Main { 
 private static final char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray(); 
 
 public static void main(String[] args) { 
 Person me = new Person("Adam", "McQuistan", LocalDate.parse("1987-09-23")); 
 
 LocalDateTime start = LocalDateTime.now(); 
 List<Person> peopleList = new ArrayList<>(); 
 for (int i = 0; i < 10000; i++) { 
 if (i == 4999) { 
 peopleList.add(me); 
 } 
 peopleList.add(new Person(getRandomName(), getRandomName(), getRandomDate())); 
 } 
 System.out.println("Microseconds to build list: " + getTimeElapsed(start, LocalDateTime.now())); 
 
 start = LocalDateTime.now(); 
 Map<Person, String> peopleMap = new HashMap<>(); 
 for (int i = 0; i < 10000; i++) { 
 if (i == 4999) { 
 peopleMap.put(me, me.toString()); 
 } 
 Person p = new Person(getRandomName(), getRandomName(), getRandomDate()); 
 peopleMap.put(p, p.toString()); 
 } 
 System.out.println("Microseconds to build map: " + getTimeElapsed(start, LocalDateTime.now())); 
 
 start = LocalDateTime.now(); 
 boolean found = peopleList.contains(me); 
 System.out.println("Microseconds to search list is " + getTimeElapsed(start, LocalDateTime.now())); 
 
 start = LocalDateTime.now(); 
 found = peopleMap.containsKey(me); 
 System.out.println("Microseconds to search map is " + getTimeElapsed(start, LocalDateTime.now())); 
 } 
 
 public static String getRandomName() { 
 int size = alphabet.length; 
 Random rand = new Random(); 
 List<Character> chars = Arrays.asList( 
 alphabet[rand.nextInt(size)], 
 alphabet[rand.nextInt(size)], 
 alphabet[rand.nextInt(size)], 
 alphabet[rand.nextInt(size)] 
 ); 
 return chars.stream().map(String::valueOf).collect(Collectors.joining()); 
 } 
 
 public static LocalDate getRandomDate() { 
 Random rand = new Random(); 
 int min = (int) LocalDate.of(1980, 1, 1).toEpochDay(); 
 int max = (int) LocalDate.of(2018, 10, 14).toEpochDay(); 
 long day = min + rand.nextInt(max - min); 
 return LocalDate.ofEpochDay(day); 
 } 
 
 public static long getTimeElapsed(LocalDateTime start, LocalDateTime end) { 
 Duration duration = Duration.between(start, end); 
 return Math.round(duration.getNano() / 1000); 
 } 
 } 

Выход:

 Microseconds to build list: 53789 
 Microseconds to build map: 892043 
 Microseconds to search list is 450 
 Microseconds to search map is 672 

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

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

A. hashCode() вручную

В книге « Эффективная Java: лучшие практики для платформы{.amazon-link} Java» гуру Java 3-го издания Джошуа Блох описывает следующий алгоритм реализации вашего собственного метода hashCode()

i) составить хэш первого поля детерминированного класса, используемого в реализации equals(Object) и присвоить его переменной, которую я назову result .
ii) для каждого оставшегося детерминированного поля, используемого в реализации equals(Object) result на 31 и добавьте хеш-значение детерминированного поля.

В моем Person этот подход выглядит примерно так:

 public class Person { 
 private final String firstName; 
 private final String lastName; 
 private final LocalDate dob; 
 
 // omitting all other stuff for brevity 
 
 @Override 
 public boolean equals(Object o) { 
 if (this == o) { 
 return true; 
 } 
 if (!(o instanceof Person)) { 
 return false; 
 } 
 Person p = (Person)o; 
 return firstName.equals(p.firstName) 
 && lastName.equals(p.lastName) 
 && dob.equals(p.dob); 
 } 
 
 @Override 
 public int hashCode() { 
 int result = dob == null ? 1 : dob.hashCode(); 
 result = 31 * result + firstName == null ? 0 : firstName.hashCode(); 
 result = 31 * result + lastName == null ? 0 : lastName.hashCode(); 
 return result; 
 } 
 } 

Теперь, если я перезапущу ту же программу, которая строит List и HashMap измеряющую время выполнения, я увижу значительную разницу.

Выход:

 Microseconds to build list: 54091 
 Microseconds to build map: 35528 
 Microseconds to search list is 582 
 Microseconds to search map is 20 

Довольно шокирующе, правда !? Сам HashMap почти вдвое быстрее, плюс время, необходимое для поиска me находится на совершенно другом уровне.

Б. Использование Objects.hash(...)

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

Ниже приведен пример этой реализации для класса Person:

 public class Person { 
 // omitting all other stuff for brevity 
 
 @Override 
 public int hashCode() { 
 return Objects.hash(dob, firstName, lastName); 
 } 
 } 

Вот результат работы программы анализа:

 Microseconds to build list: 56438 
 Microseconds to build map: 38112 
 Microseconds to search list is 733 
 Microseconds to search map is 24 

Как видите, он практически идентичен реализации, скрученной вручную.

В. Автогенерация с помощью IDE

Мой предпочтительный метод реализации методов equals(Object) и hashCode() самом деле заключается в использовании функции автогенерации в моей выбранной Java IDE Eclipse. Реализация, предоставляемая Eclipse, показана ниже.

 public class Person { 
 
 // omitting all other stuff for brevity 
 
 @Override 
 public int hashCode() { 
 final int prime = 31; 
 int result = 1; 
 result = prime * result + ((dob == null) ? 0 : dob.hashCode()); 
 result = prime * result + ((firstName == null) ? 0 : firstName.hashCode()); 
 result = prime * result + ((lastName == null) ? 0 : lastName.hashCode()); 
 return result; 
 } 
 
 @Override 
 public boolean equals(Object obj) { 
 if (this == obj) 
 return true; 
 if (obj == null) 
 return false; 
 if (getClass() != obj.getClass()) 
 return false; 
 Person other = (Person) obj; 
 if (dob == null) { 
 if (other.dob != null) 
 return false; 
 } else if (!dob.equals(other.dob)) 
 return false; 
 if (firstName == null) { 
 if (other.firstName != null) 
 return false; 
 } else if (!firstName.equals(other.firstName)) 
 return false; 
 if (lastName == null) { 
 if (other.lastName != null) 
 return false; 
 } else if (!lastName.equals(other.lastName)) 
 return false; 
 return true; 
 } 
 } 

Результат программы анализа следующий:

 Microseconds to build list: 53737 
 Microseconds to build map: 27287 
 Microseconds to search list is 1500 
 Microseconds to search map is 22 

Опять же, эта реализация почти идентична по производительности.

Заключение

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

Как всегда, спасибо за чтение и не стесняйтесь комментировать или критиковать ниже.