Методы объектов Java: Хэш-код()

Вступление

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

Струна
в класс
равняется
Хэш-код (вы здесь)
клон
завершать
ждать и уведомлять

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

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

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

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

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

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

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

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

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

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

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);
    }
}

import java.time.LocalDate;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map 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 не равны, даже если пользовательская реализация равно(объект) указывает, что они логически одинаковы. Это приводит к двум различным записям в хэш-таблице, хотя вы ожидали бы только одну, что открывает двери для некоторых неприятных ошибок в программе, если бы она реализовывала этот код.

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

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

public class Person {
    // omitting all other stuff for brevity

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

public class Main {
    public static void main(String[] args) {
        Map 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

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

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

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

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

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Ниже приведена программа, которая создает две коллекции одинакового размера, Список людей и Карта людей , экземпляров Человек с выбранными случайными именами и днями рождения одинакового размера. Я измерю количество времени, необходимое для создания коллекций для первого сравнительного измерения. Далее я измерю количество времени, необходимое для поиска в каждой коллекции на наличие одинаково размещенного известного экземпляра 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 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 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 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. Хэш-код() вручную

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

i) введите хэш первого поля детерминированного класса, используемого в реализации equals(Объект) , и назначьте его переменной, которую я назову результат . ii) для каждого оставшегося детерминированного поля используется равно(Объект) реализация, умножьте результат на 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;
    }
}

Теперь, если я повторю ту же программу, которая создает Список и Хэш-карту , измеряющую время выполнения, я увижу существенную разницу.

Выход:

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

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

B. Использование Объекты.хэш(…)

Если вы ищете более простой способ реализации пользовательского хэш-значения и не очень против того, чтобы не иметь наиболее эффективной реализации, тогда рекомендуется обратиться к утилите 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

Как вы можете видеть, он по сути идентичен реализации с ручным скручиванием.

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

Мой предпочтительный метод реализации обоих методов equals(объект) и hashCode() на самом деле заключается в использовании функции автогенерации в моей среде разработки Java по выбору 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(Объект) для эффективной работы со структурами данных, которые применяют понятие хэш-таблицы. В дополнение к объяснению того, почему важно реализовать метод hashCode () , я также продемонстрировал, как реализовать несколько достаточно эффективных и надежных алгоритмов хеширования.

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

Вступление

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

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

Git Essentials

Вывод

Читайте ещё по теме: