HashMap и HashSet. Что это на самом деле?

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

 

Шаг 0. Введение

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

 

Шаг 1. Что такое хэш-код?

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

Есть несколько правил по переопределению данного метода:

1. Это не должна быть константа. Иначе все будет равным, даже если это не так.

2. Метод генерации должен быть хорошо продуман, иначе могут часто попадаться ситуации коллизии.

3. В генерации желательно использовать именно те поля, которые идентифицируют объект, его уникальность.

Пример того как это все выглядит:

 

 

У нас есть 2 объекта с двумя полями. Поля одинаковые, значит их хэш-код должен совпадать и указывать на равенство. Создадим генерацию нашего кода на обычной сумме атрибутов:

1 + 2 = 1 + 2 — равенство верно.

Но что будет если у нас такие объекты:

 

 

Здесь поменялся только порядок значений для второго объекта. Эти объекты уже не могут быть равны, но…

1 + 2 = 2 + 1 — равенство осталось верно.

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

Можем сделать вывод:

Для одного и того ж объекта хэш-код всегда один(если не изменять вычисляемые поля)

Если хэш-коды равны, то это не значит что и объекты равны.

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

Рассмотрим теперь это на примере. Создадим 2 класса, переопределим вычисление хэш-кода и докажем наши выводы.

public class A {
    private int a;
    private int b;

    public A() {
    }

    @Override
    public int hashCode() {
        return a + b;
    }
//getters & setters
}

И методы main где мы сделаем простую проверку вышесказанного.

A o1 = new A();
A o2 = new A();
o1.setA(1);
o1.setB(2);

o2.setA(1);
o2.setB(2);

/*
* Объекты одинаковые, ожидаем true
* */
System.out.println(o1.hashCode() == o2.hashCode());

o2.setA(2);
o2.setA(1);

 /*
* Зесь мы иммем 2 объекта которые имеют разные значение,
* то есть и объекты являются разными. Ожидаем false
* Получаем коллизию, хэш код одинаковый
* */
System.out.println(o1.hashCode() == o2.hashCode());

/*
* Объект имеет всегда один хэш-код. Равен сам себе
* */
System.out.println(o1.hashCode() == o1.hashCode());

o2.setA(25);
o2.setB(100);

/*
* Пример того, что разные хэш-кода, указывают на разные
* объекты.
* */
System.out.println("o1="+o1.hashCode() + " o2="+o2.hashCode());

 

Шаг 2. Что тогда такое equals()?

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

 

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

Используем для примера предыдущий класс и реализуем проверку эквивалентности.

A o1 = new A();
A o2 = new A();

o1.setA(1);
o1.setB(2);

o2.setA(1);
o2.setB(2);

/*
* Проверка на эквивалентность.
* Должно быть true
* */
System.out.println(o1.equals(o2));

/*
* Меняем значения местами, как с хэш-кодом
* и проверяем...
* */
o2.setA(2);
o2.setB(1);
System.out.println(o1.equals(o2));

Как вы заметили, эти два понятия тесно связаны и указывают на равенство объектов. Теперь, разобравшись с этим, перейдом непосредственно к коллекциям.

 

Шаг 3. Организация работы HashMap

<Hash> — это число, как мы говорили выше.

<Map> — коллекция которая состоит с пар «ключ»-«значение».

HashMap — внутри состоит с так званых корзин и списка элементов, на которые ссылаются корзины.

 

5_4385

 

Корзины — массив
Элементы — связной список. (это рассмотрим дальше)

Добавление

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

Если оба равны: идет перезапись

Если не равен equals: добавляется элемент в список

По этому:
1. Если у нас плохой алгоритм расчета хэш-кода, то мы получим обычный связной список и потеряем все преимущества данной структуры. (Добавление, поиск и удаление элементов выполняется за константное время)

2. Важно переопределять метод hashCode & equals для корректной работы.

Получение

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

Предостережение!

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

 

Шаг 4. Организация работы HashSet

Почему мы сразу рассмотрели HashMap? Это поможет с пониманием работы следующей коллекции. Здесь все происходит также, единственное отличие здесь в том, что ключом является сам объект.

 

6_4385

 

Предостережение!
Будьте аккуратны в работе с объектом. Если вы поменяете вычисляемые поля объекта, то вы можете навеки потерять его в коллекции.

Урок создан: 29 апреля 2014 | Просмотров: 26801 | Автор: Олег Криль | Правила перепечатки


Добавить комментарий

Добавить комментарий

Ваш e-mail не будет опубликован.

Комментарии:

  • 17 июня 2014 в 13:11

    Игорь

    Почему при выполнении System.out.println(o1.equals(o2)); получаю false?
    Код напрямую скопирован.

    • 17 июня 2014 в 20:26

      Олег Криль

      Вы переопределили метод equals?
      «Запомните: изначально, в классе Object идет сравнивание по ссылке, что значит без переопределения данного метода, все ваши объекты будут считаться разными, если только их ссылки не указывают на один и тот же объект.»

      • 26 сентября 2014 в 09:50

        Nick

        Как переопределить метод equals?

        • 28 мая 2015 в 16:00

          Donnie

          @Override
          equals( other ){
          return (this.a == other.a);
          }

        • 28 марта 2016 в 13:57

          Аноним

          Eclipse и Idea сами сгенерируют код при переопеределени hashCode() и equals().