В данном уроке, я попробую копнуть в теме коллекций и рассказать о двух реализациях построенных на хэш коде.
Шаг 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 – внутри состоит с так званых корзин и списка элементов, на которые ссылаются корзины.
Корзины – массив
Элементы – связной список. (это рассмотрим дальше)
Добавление
Когда приходит новый элемент, хэш-код ключа определяет корзину, для элемента. В корзине идет проверка, есть ли у нее элементы. Если нету, то корзина получает ссылку нового элемента, если есть, то происходит прохождение по списку элементов и сравнивание элементов в списке. Проверяется равенство hashcode. Так как мы не можем однозначно судить на счет эквивалентности, зная о случаях коллизии, проводится еще сравнивание ключей методом equals.
Если оба равны: идет перезапись
Если не равен equals: добавляется элемент в список
По этому:
1. Если у нас плохой алгоритм расчета хэш-кода, то мы получим обычный связной список и потеряем все преимущества данной структуры. (Добавление, поиск и удаление элементов выполняется за константное время)
2. Важно переопределять метод hashCode & equals для корректной работы.
Получение
Получение объекта происходит по тому же принципу. Приходит ключ, берется его хэш-код и вычисляется номер корзины, потом, с этой корзины, проходя по списку элементов, находится наш и возвращается ссылка на него.
Предостережение!
Не используйте в качестве ключа массивы. Их хэш код зависит от ссылки. Если даже будете использовать массив с такими ж данными, чтобы получить свое значение, ссылка будет другая и вы не получите свой объект.
Шаг 4. Организация работы HashSet
Почему мы сразу рассмотрели HashMap? Это поможет с пониманием работы следующей коллекции. Здесь все происходит также, единственное отличие здесь в том, что ключом является сам объект.
Предостережение!
Будьте аккуратны в работе с объектом. Если вы поменяете вычисляемые поля объекта, то вы можете навеки потерять его в коллекции.
ПОХОЖИЕ ПУБЛИКАЦИИ
- None Found
14 комментариев к статье "HashMap и HashSet. Что это на самом деле?"