HashMap часть 2

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

Пару дней назад один мой друг сходил на собеседование в одну из Минских фирм. Там ему задали вопрос про HashMap, сейчас попробуем его разобрать. Кстати, прошлый выпуск про HashMap тут.

Предположим, что в мапку, созданную данным способом (Код 1), нужно добавить 1 миллион объектов. Что тут плохого? Давайте подумаем.

Как обычно, видос для ленивых:

Что произойдет, когда выполнится данный код? Создастся массив на 16 элементов с loadFactor = 0.75. Получаем, что после добавления 12 элементов произойдет удвоение длинны массива. Напомню, что это число получается перемножив loadFactor и текущее количество корзинок или длину массива.

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

Добавили 12. Потом эти 12 снова добавили, после увеличения массива. Грубо говоря добавили всего 24. Что получаем? В следующий раз, удвоение числа корзинок произойдет после добавления 24-го элемента, а в мапке уже 12.

Добавили еще 12 + снова перераспределение и еще 24, получаем 36.
Представляете сколько нужно будет выполнить работы, пока мы не закончим добавлять все 1 миллион объектов. Нарисовал небольшой график внизу 18 столбиков высота каждого равняется количеству добавлений и перераспределений по корзинкам при добавлении объекта под номером, который указан под столбиком.

Рис. 1. График добавления 1М объектов.

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

В каком случае может быть потерян элемент в HashMap?

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

На этом все!

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

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

Ваш 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="">