HashMap

Вопросы на собеседовании. HashMap. Часть 1

Почему я выбрал эту тему? Ее нужно знать обязательно если Вы пришли на собеседование. Не знаете = не готовы!
Ниже я перечислил наиболее популярные вопросы по этой теме. Для тех кому лень читать – можно посмотреть видос.

Расскажите про устройство HashMap?

Во-первых что такое HashMapHashMap – это ассоциативный массив. Если вкратце, то ассоциативный массив – это структура данных, которая хранит пары ключ-значения.

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

Рис. 1. HashMap

Как по ключу можно определить положение искомого объекта? Для этого нам нужно знать hashCode ключа. Где же его взять? Все очень просто, если понимать, что в качестве ключа, может выступать любой объект в java. Все знают что класс Object реализует метод hashCode(), это означает что он будет унаследован или переопределен самим “ключом”. Т.к. все в java наследуются от класса Object. Теперь понятно откуда у ключа берется hashCode!

После того как в hashMap, был передан ключ + сохраняемый объект, специальная hash-функция вычисляет то в какую корзину отнести наши данные.

Как вы понимаете, никаких корзинок в HashMap-е нет. Вместо них есть массив, который хранит ссылки на связанные списки в которых хранятся наши данные. Каждому элементу массива соответствует один список.

Какое начальное количество корзин в HashMap?

Данный вопрос мне ни разу не задавали я его нашел на хабре. Ответ – 16. Но как и с ArrayList-ом в конструкторе можно задать другое количество.

Что такое коллизия? Способ решения коллизий.

Этот вопрос так же часто встречается. Коллизия это когда два разных объекта попадают в одну корзинку(связанный список). Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы с HashMap, hashcode не должен повторяться для не эквивалентных объектов.

Как я уже упомянул выше, все данные хранятся в списках. Почему так? Почему не хранить всего один объект? Ответ прост. Все потому, что это способ разрешения коллизий. Как происходит добавление? Смотр код 1

  • Первое – мы выясняем то какая корзина соответствует ключу объекта. Затем проверяем, есть ли в ней уже какие-то объекты, если нет – то добавляем текущий. Если да, то это случилась коллизия.
  • Тогда мы начинаем сравнивать ключ и hashcode текущего объекта и тех которые внутри (если конечно их там несколько).
  • Сначала проверяем равны ли hashcode ключей.
  • Если да, то сравниваем их ключ методом equals.
  • Если equals возвращает true, значит ключи совпадают по “значению” и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом,
  • Если hashcode и “значение” ключа неравны – новый объект добавляется в конец списка.

Как и когда происходит увеличение количества корзин в HashMap?

HashMap имеет поле loadFactor. Оно может быть задано через конструктор. По умолчанию равняется 0.75.  Для чего оно нужно? Его произведение на количество корзин дает нам необходимое число объектов, которое нужно добавить, чтобы состоялось удвоение количества корзин. Например, если у нас мапка с 16-ю корзинами, а loadFactor равняется 0.75, то расширение произойдет когда мы добавим 16 * 0.75 = 12 объектов. Мапка увеличивается вдвое.

Какая оценка временной сложности операций с HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?

Рассмотрим сначала случай в котором нет коллизий. В этом случае добавление, удаление и поиск объектов по ключу выполняется за константное время O(1). Разумеется, не учитывается случай с расширением количества элементов. Вообще говоря, когда Вы работаете с HashMap, лучше сразу указать в конструкторе, сколько корзин нужно для работы и хорошо если оно равняется числу уникальных объектов с которыми Вы будите работать. В таком случае не придется тратить время и ресурсы на создание нового HashMap с удвоенным количеством bucket-ов. Почему такая хорошая производительность? Тут все просто. Повторюсь что коллизий нет – в таком случае нет никакой зависимости от других элементов из этой мапки. Удаление, Вставка, Поиск выполняются примерно по одной схеме. Берется HashCode ключа, вычисляется корзинка, и производится удаление, вставка или поиск. Все! Нигде не встречаются другие объекты. Но это лишь в том случае, если нет коллизий.

Теперь поговорим о случае когда коллизии все-таки присутствуют. Теоретически работая с HashMap в котором могут присутствовать коллизии, мы получаем временную сложность O(log(n)) на операции вставки, сохранения и удаления. В самом худшем случае, когда все объекты возвращают один и тот же HashCode, а значит попадают в одну корзину. На самом деле это связный список и тогда временная сложность как у LinkedList O(n).

На этом пока все. Удачи.

Некоторые источники:

Продолжение

Знай сложности алгоритмов

Структуры данных в картинках. HashMap

5 Комментарии “Вопросы на собеседовании. HashMap. Часть 1

  1. Статья сама по себе хороша для любознательного программиста. Но скажите, зачем на собеседовании задавать такие вопросы по внутренней реализации того или иного класса? Я могу задать любому, кто будет меня таким образом опрашивать сотню вопросов, на которые он не ответит. Думаю Вы тоже знаете такие вопросы. Руководителям компании следует не допускать таких людей в качестве экзаменаторов. Исключеним, может быть разве что компания, разрабатывающая компиляторы или библиотеки.

    1. Для того, чтобы понять что человек действительно знает как это работает. То как работает HashMap знать нужно обязательно и не потому, что это спрашивают на интервью.

      1. Знать как работвет HashMap ? Программисту надо знать , что собой представляет Map интерфейс. И как этот интерфейс реализован Sun /Oracle – это лишь вопрос любознательности. Есть масса реализаций интерфейса Map (Google, Apache etc. ) И что, надо останавливаться на том как изнутри это делает Oracle? Гораздо важнее программисту знать, что в конечном счете для реализации используются native методы. А то многие считают, что используются массивы java. А уж как там Oracle строит какие-то внутренние структуры совершенно не важно.

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

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

*

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">