The hashCode and equals methods
Какие бывают ассоциативные массивы (Map)? Какие из них быстрее? Что нужно сделать, чтобы они заработали быстрее? Для чего нужны ф-ии hashCode и equals?
Рассмотрим основные моменты, для понимания потребности в методах. Разделим ассоциативные массивы на три различных типа мапов:
HashMap(выводит элементы без порядка)(Для хранения элементов используются бакеты(Backet/Slot))
LinkedHashMap(вывел элементы в том порядке, в каком и добавляли)(Для хранения элементов используются бакеты(Backet/Slot))
TreeMap(выводит элементы в порядке отсортированном по ключу)(является самым медленным, по той причине, что когда мы добавляем элемент, он сравнивает его ключ с ключами присутствующих элементов, и основываясь на результате сравнения, в процессе добавления, сортирует порядок)
Основная логика ассоциативных массивов, что вы можете добавить в них большое кол-во данных с ключами и дальше по ключу их оттуда доставать. При этом, каждый ключ имеет одно уникальное значение.
В TreeMap ключи должны соответствовать интерфейсу Comparable. Для этого достаточно имплементировать интерфейс Comparable и реализовать ф-ю compareTo() которая возвращает значение Integer. (TreeMap не использует ф-ю equals).
В HashMap, LinkedHashMap, нам нужно переопределить ф-ии hashCode и equals, таким образом, чтобы сравнить все внутренние элементы нашего класса.
- Рефлексивность (reflexive): Объект должен быть равен самому себе, т.е. для каждого нулевого x, x.equals(x) должно возвращать true.
- Симметричность (symmetric): Объекты должны быть равны друг другу, т.е. для ненулевых x и y, x.equals(y) должно возвращать true только если y.equals(x) возвращает true.
- Транзитивность (transitive): Для ненулевых x, y, z (три объекта), если x.equals(y) возвращает true, и y.equals(z) возвращает true, то x.equals(z) должно возвращать true.
- Повторяемость (consistent): Для ненулевых x и y последовательные вызовы x.equals(y) должны постоянно возвращать true или постоянно возвращать false при условии, что x и y не меняются.
- У двух одинаковых объектов должен быть одинаковый хеш-код.
- У двух разных объектов могут быть одинаковые хеш-коды. (Как написать функцию, чтобы избежать возникновение коллизии?)
- Нельзя возвращать константу или рандомное число.
Работая со множеством, мы проверяем, не имеют ли наши объекты одинаковый hashCode. И использование hashCode и equals интересно тогда, когда мы работаем с группой объектов одного типа, и для их быстрого различия, мы и используем ф-ию hashCode.
Сначала мы обращаемся к методу hashCode(проверяем уникальность), и если хеш-коды одинаковые (напомню, что это значит произошла коллизия), переходим в метод equals.
Соответственно, при проектирования какого либо класса, если мы понимаем, что будем сравнивать объекты этого класса, то необходимо реализовать метод hashCode.
Переопределение методов (@Override)
При переопределении методов, в большинстве случаев, мы выбираем все поля нашего класса. Методы hashCode и equals переопределяются всегда вместе, так как связаны одним контрактом.
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Human human = (Human) o;
return id == human.id && Objects.equals(firstName, human.firstName) && Objects.equals(lastName, human.lastName);}if (this == o) return true; - говорит нам о том, что наши ссылки равны друг другу.
if (o == null || getClass() != o.getClass()) return false; - если объект равен нулю и объект не принадлежит одному и тому же классу(т.е. классы не равны), то возвращаем false.
@Override
public int hashCode() {
return Objects.hash(id, firstName, lastName);}return Objects.hash(id, firstName, lastName); - возвращаем хэш код нашего объекта.
В нашем примере, мы можем сами устанавливать критерии сравнения наших объектов. Например, сравнивать только по id. Или сравнивать по всем параметрам типа, как указано выше.
Что такое бакеты(bucket(-ведро))? Набор элементов хеш-таблицы с совпадающими/близкими значением хеш-функции.
У каждого объекта в JVM, есть функция HashCode, когда мы что то добавляем в HashMap или LinkedHashMap, коллекция высчитывает хеш-код элемента и основываясь на результате, кладет его в структуру данных. При добавлении нового элемента, операция повторяется и вычисляется новый хеш, после чего определяется место для элемента.
Когда мы будем искать по ключу определенное значение из нашей коллекции, сначала для ключа просчитается хеш-код, по хещ-коду будет найден бакет, в котором лежит наш объект и дальше будет доставаться значение для этого объекта, предварительно сравнив с конкретным ключом, который лежит в этом бакете.
Что возвращает ф-я compareTo()? Функция возвращает целочисленное значение Integer. "-1" если левый объект, меньше чем правый. "1" если левый больше чем правый. "0" если они равны
(https://www.youtube.com/watch?v=6qVRci8gG-M)
(https://ru.stackoverflow.com/questions/988722/%D0%A7%D1%82%D0%BE-%D1%82%D0%B0%D0%BA%D0%BE%D0%B5-buckets-%D0%B8%D0%BB%D0%B8-%D0%B1%D0%B0%D0%BA%D0%B5%D1%82)
(https://medium.com/@vaibhav0109/https-medium-com-vaibhav0109-java-hashcode-collision-how-uniform-is-its-distribution-ee4e5e8dc894)