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

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

ПОХОЖИЕ ПУБЛИКАЦИИ

35846
29/04/2014

12 комментариев к статье "HashMap и HashSet. Что это на самом деле?"

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

  2. так и не ясно из статьи в корзину ложится толи ключ толи хешкод тоже самое и с хешсетом ключем является сам объект а ключ объэкта куда девается. Автор сам не понял о чем пишет

  3. в хеш мапе в качестве ключа что используется?

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

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