Самые распространенные вопросы для собеседований можно собрать в группы. И одной из самых частых групп являются вопросы о Collection framework. Об одном из аспектов этого фреймворка мы сегодня и поговорим.
Говорить о классах Collections framework, как и о сортировке и поиске данных можно много, поэтому давайте организуем пост в виде вопросов и ответов. А вопросы постараемся задать такие же, как это делают интервьюеры.
Что такое Map и для чего он нужен?
Map - интерфейс, описывающий классы, предназначенные для хранения пар объектов. Один из объектов пары должен быть уникальным - называется "ключом" (key), второй объект, необязательно уникальный, называется "значением" (value). Всю пару называют "записью" (entry).
Как определить уникальность ключа?
Вспомним предыдущий абзац. Уникальный - значит не равный другим ключам. Как определить "равность"? По функции equals(), определяемой в классе Object, а потому доступной для всех объектов. Про тонкости equals() и ее переопределения в другом посте, а пока для нас достаточно знать, что ключи в Map сравниваются по методу equals(), и при попытке добавить в Map запись с не уникальным ключом предыдущая запись будет затерта новой.
Какие реализации Map вы знаете?
HashMap, TreeMap, LinkedHashMap
Поговорим теперь конкретно о HashMap
Как HashMap устроен внутри?
Внутри HashMap - это массив. Элементы массива в документации называются бакетами (buckets). Будем следовать этому наименованию и мы. В бакете хранится первый элемент связанного списка. Вообще связанные списки можно обсудить в другом посте, главное, что нужно знать, связанный список - это цепочка объектов, каждый из которых имеет ссылку на следующий объект из цепочки. Имея первый элемент, можно по цепочке добраться до всех элементов списка. Таким образом, HashMap внутри - массив связанных списков. Элемент связанного списка - объект класса Entry, содержит ключ, значение и ссылку на следующий Entry.
Что происходит при добавлении записи?
Сначала вычисляется hashcode() ключа. Функция hashcode() определена в классе Object, так что даже если вы не переопределите ее в своем классе ключа, она все равно сработает. Выдаст адрес обьекта в памяти или еще какое-нибудь случайное число (int). Затем из двух значений - hashcode и размер массива - математически вычисляется индекс бакета, соответствующего hashcode. Главное, что нужно тут знать - соответствие между ключом и бакетом не хранится, оно вычисляется.
Далее, найдя нужный бакет, запись помещается в соответствующий связанный список.
А как искать элемент?
Поиск производится по ключу (ключ для поиска). Опять же по hashcode() ключа находим нужный бакет. Нашли бакет - значит нашли нужный нам связанный список. Далее проходим по списку и сравниваем ключи элементов списка с нашим ключом для поиска. Сравнение производим по функции equals(). Вернула функция true - значит нашли.
И для чего все это нужно?
Для ускорения работы. В первую очередь ускорение поиска. Напомню, соответствие между hashcode ключа и бакетом не хранится, а вычисляется. Математические вычисления - это быстро. Далее, сравнивать объекты по equals() все же придется, но количество этих объектов ограничено.
А недостатки?
Во-первых, потребляемая память. Не все бакеты заполнены списками, на нулевые бакеты тоже тратится место. Во-вторых, при росте таблицы растет и количество элементов в связанных списках. Это замедляет работу. Для оптимизации приходится увеличивать объем массива и заново перераспределять записи по бакетам. Этот процесс называется "рехешинг" (rehashing)
Что такое capacity?
Capacity - размер массива, количество бакетов. Initial capacity - начальный размер массива при создании объекта HashMap. Задается в конструкторе.
Что такое load_factor?
Предельно допустимое отношение заполненных бакетов к общему количеству бакетов, после превышения которого начинается рехешинг. Значение по умолчанию - 0.75. То есть, допустим у Вас массив на 128 ячеек и из них занято 96. load_factor здесь 96/128=0.75. Если при добавлении записи будет занят еще один бакет, запустится процесс рехешинга, будет создан массив большего объема (обычно в 2 раза) и значении load_factor снизится.
У меня пока все. Осталось ответить на несколько вопросов, но это в другом посте.
P.S. Так как же все-таки правильно написать hashcode()?
Говорить о классах Collections framework, как и о сортировке и поиске данных можно много, поэтому давайте организуем пост в виде вопросов и ответов. А вопросы постараемся задать такие же, как это делают интервьюеры.
Что такое Map и для чего он нужен?
Map - интерфейс, описывающий классы, предназначенные для хранения пар объектов. Один из объектов пары должен быть уникальным - называется "ключом" (key), второй объект, необязательно уникальный, называется "значением" (value). Всю пару называют "записью" (entry).
Как определить уникальность ключа?
Вспомним предыдущий абзац. Уникальный - значит не равный другим ключам. Как определить "равность"? По функции equals(), определяемой в классе Object, а потому доступной для всех объектов. Про тонкости equals() и ее переопределения в другом посте, а пока для нас достаточно знать, что ключи в Map сравниваются по методу equals(), и при попытке добавить в Map запись с не уникальным ключом предыдущая запись будет затерта новой.
Какие реализации Map вы знаете?
HashMap, TreeMap, LinkedHashMap
Поговорим теперь конкретно о HashMap
Как HashMap устроен внутри?
Внутри HashMap - это массив. Элементы массива в документации называются бакетами (buckets). Будем следовать этому наименованию и мы. В бакете хранится первый элемент связанного списка. Вообще связанные списки можно обсудить в другом посте, главное, что нужно знать, связанный список - это цепочка объектов, каждый из которых имеет ссылку на следующий объект из цепочки. Имея первый элемент, можно по цепочке добраться до всех элементов списка. Таким образом, HashMap внутри - массив связанных списков. Элемент связанного списка - объект класса Entry, содержит ключ, значение и ссылку на следующий Entry.
Что происходит при добавлении записи?
Сначала вычисляется hashcode() ключа. Функция hashcode() определена в классе Object, так что даже если вы не переопределите ее в своем классе ключа, она все равно сработает. Выдаст адрес обьекта в памяти или еще какое-нибудь случайное число (int). Затем из двух значений - hashcode и размер массива - математически вычисляется индекс бакета, соответствующего hashcode. Главное, что нужно тут знать - соответствие между ключом и бакетом не хранится, оно вычисляется.
Далее, найдя нужный бакет, запись помещается в соответствующий связанный список.
А как искать элемент?
Поиск производится по ключу (ключ для поиска). Опять же по hashcode() ключа находим нужный бакет. Нашли бакет - значит нашли нужный нам связанный список. Далее проходим по списку и сравниваем ключи элементов списка с нашим ключом для поиска. Сравнение производим по функции equals(). Вернула функция true - значит нашли.
И для чего все это нужно?
Для ускорения работы. В первую очередь ускорение поиска. Напомню, соответствие между hashcode ключа и бакетом не хранится, а вычисляется. Математические вычисления - это быстро. Далее, сравнивать объекты по equals() все же придется, но количество этих объектов ограничено.
А недостатки?
Во-первых, потребляемая память. Не все бакеты заполнены списками, на нулевые бакеты тоже тратится место. Во-вторых, при росте таблицы растет и количество элементов в связанных списках. Это замедляет работу. Для оптимизации приходится увеличивать объем массива и заново перераспределять записи по бакетам. Этот процесс называется "рехешинг" (rehashing)
Что такое capacity?
Capacity - размер массива, количество бакетов. Initial capacity - начальный размер массива при создании объекта HashMap. Задается в конструкторе.
Что такое load_factor?
Предельно допустимое отношение заполненных бакетов к общему количеству бакетов, после превышения которого начинается рехешинг. Значение по умолчанию - 0.75. То есть, допустим у Вас массив на 128 ячеек и из них занято 96. load_factor здесь 96/128=0.75. Если при добавлении записи будет занят еще один бакет, запустится процесс рехешинга, будет создан массив большего объема (обычно в 2 раза) и значении load_factor снизится.
У меня пока все. Осталось ответить на несколько вопросов, но это в другом посте.
P.S. Так как же все-таки правильно написать hashcode()?
Хотелось бы задать вопрос к теме данного поста, а все же что такое HashSet и с чем его едят?
ОтветитьУдалитьИли я что-то пропустил :) ?.
Скорее это мы пропустили :) поправимся. Но если вкратце. то HashSet - это реализация интерфейса Set, который позволяет в себя размещать только уникальные элементы. Внутренняя же структура HashSet совершенно совпадает с описанным тут HashMap
УдалитьНу правильно, когда на Хабре появится статься про HashSet - он появится и здесь. Какой толк называть статью HashMap и HashSet, если в ней не будет ни доли информации про HashSet??
УдалитьИнтересно иногда про азы почитать. Освежает, спасибо :)
ОтветитьУдалитьСо своей колокольни хочу добавить - забудьте о теоретических недостатках. Если для вашего приложения критична производительность операций которые происходят в памяти локальной машины или используемая память, то весь пакет java.util не особо эффективен. В таких случаях люди опускаются до JNI и даже специфических команд процессора (типа всяких SSE). И я знавал такие проекты. Но такие проблемы чрезвычайно редки. Обычное EE приложение узким местом имеет сеть и базу данных а вовсе не скорость обмолачивание индексов в памяти и количество этой самой памяти (которой в наше время во-первых дофига - спасибо 64bit, во-вторых стоит копейки)
У меня процессы есть которые мэпы тягают в миллионы элементов с другой мэпами или массивами в качестве ключей :) ) и всё летает даже на железе многолетней давности.
Гму, ты совершенно прав - основные тормоза, в большинстве своем в базе и/или сетевом взаимодействии. Хотя, вот предыдущий проект был на Oracle SOA/OSB. Так вот OSB тормозила как зараза (то бишь вызов сервисов). Хотя, о внутреннем устройстве лучше все-таки знать - если используется некий Set, Map или List с миллионами записей, то лучше все-таки продумать, какой именно лучше подойдет. Ну и методы equals и hashCode
Удалить...не забыть переопределить. Комент отправил раньше, чем дописал :)
УдалитьЯ уже давным давно при выборе коллекций не думаю о них с точки зрения какая из них производительный, или там экономней. Скорее с точки зрения какая из них даст мне более короткий и понятный код в конкретном случае.
ОтветитьУдалить"ключи в Map сравниваются по методу equals(), и при попытке добавить в Map запись с не уникальным ключом предыдущая запись будет затерта новой."
ОтветитьУдалитьМожет я что-то не так понимаю, но при попытке добавить запись с не уникальным ключом никакого equals() не вызывается, а просто при определении индекса массива, куда будет размещаться данная запись, индекс совпадет, и в этом случае новая пара ключ\значение перезапишет старую.
h & (length - 1) - это формула, по которой вычисляется индекс.
h = hash(key.hashCode()) - стандартный hashCode(), который определён в классе Object, загоняется в метод hash где ещё раз обрабатывается, возвращая на выходе новый хеш код, который будет иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении loadFactor).
length - длина массива.
Получается, что если один и тот-же ключ перегнать в хэш-код, и подставить в формулу, то при условии, что длина массива одинаковая -- они будут указывать на один и тот-же индекс массива, и просто новая запись перезапишет старую.
Знаю я это из статьи http://habrahabr.ru/post/128017
Я только начинаю изучать Java, поэтому пишу не с целью затеять холивар -- просто хочется глубже понять тему.
Забыл написать.
ОтветитьУдалитьВ формуле h & (length - 1), & -- служит для того, что бы привести длинный хэш-код к значению меньшему или равному длине массива.
И ещё вопрос к вам. Получается, что все эти цепочки (связные списки) это побочный эффект? Ведь чем их меньше, тем быстрее будет поиск по коллекции?
Разобрался. То что я писал полный бред. После того как мы определили бакет, в который будет положено наше значение, вызывается метод put, а уже в этом методе идёт проверка, есть ли в данном связном списке такой элемент. Если есть -- перезапишем, если нет, добавим новый.
ОтветитьУдалитьВернее не вызывается, а просто проводится проверка. Все вышеописанные действия и так из put() выполняются.
УдалитьПривет:) Я снимаю ролики про вопросы на собеседовании
ОтветитьУдалитьТут по ссылке можно про HashMap посмотреть. Надеюсь будет полезно!
https://www.youtube.com/watch?v=Z0JMABjXnww
Полагаю, стоит еще добавить информацию о порядке вывода всех элементов из коллекции (мапы).
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьfor(Map.Entry entry : map.entrySet()){
ОтветитьУдалитьK key = entry.getKey();
V val = entry.getValue(); - Это встроенный функционал
}
Вроде бакет, где хранится элемент определяется так: int bucket = (n - 1) & hash; где n-количество бакетов и hash-вычисленный хэш ключа. В итоге бакет равен числу от 0 до n(изначально 16, так как вначале у хэшмапа 16 элементов).
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьПро HashSet хочу добавить, что если взглянуть в исходники, то в основе HashSet стоит HashMap. У которого вместо пары "ключ-значение" остался только "ключ".(HashSet-урезанная версия HashMap). Отсюда вытекает идентичность методов, за исключением того, что HashSet предполагает хранение уникальных объектов. Это достигается за счет того, что после вычисления хэша объекта и определения места в связанном бакете, объект помещается в определенное место, хотя то место могло быть занято идентичным объектом. В итоге новый объект затирает старый (хотя они и одинаковые) и остаются только уникальные объекты в HashSet.
ОтветитьУдалить