Map. Внутреннее устройство реализаций

В рамках данного урока мы разберем, как реализованы три основные Map’ы, доступные в рамках java.util: HashMap, LinkedHashMap и TreeMap.

С HashMap постараемся разобраться подробнее, с остальными – в общих чертах. Связано это с тем, что именно вопрос о внутреннем устройстве HashMap можно встретить на большинстве собеседований для Java-разработчиков. Особенно для junior и middle позиций.

Кроме того, затронем основные реализации Set’ов – ведь они работают именно на базе Map.

HashMap

Несмотря на то, что вопрос популярен и, в сущности, не слишком сложен (по крайней мере, в тех рамках, в которых ожидают владение им от джуна), многие кандидаты валятся именно на нем. Почему – большой-большой секрет.

Данный пункт представлен как краткое описание внутренней структуры коллекции от меня и две сторонние статьи, подходящие к описанию реализации HashMap с разных сторон.

Итак, HashMap как структура данных представляет собой массив бакетов (от англ. bucket – ведро). Также можно иногда услышать о корзинах или нодах (от англ. – Node) – это все о том же, но последний термин я не рекомендую. Чуть ниже станет понятна причина.

Каждый бакет является объектом вложенного класса Node или его наследника – TreeNode. По крайней мере, если речь идет именно о HashMap.

В свою очередь, каждый бакет (каждый объект Node в массиве), является точкой входа в одну из структур данных – односвязный список (если элементов меньше 8), либо красно-черное дерево (если элементов 8 и более). RB-tree актуально только начиная с Java 8. В более старых версиях – только односвязный список.

Интересный факт. Бакет превращается из односвязного списка в дерево при добавлении в него 8го элемента (можете обратить внимание на метод treeifyBin()). Но в дальнейшем такой бакет может вновь превратиться в односвязный список (метод untreeify()) при выполнении ряда условий, где обязательным но недостаточным будет наличие в бакете лишь 6 или менее элементов. Т.е., теоретически, можно встретить бакет из 7 элементов, представленный в виде дерева.

Для отсутствия путаницы, предлагаю бакетом считать структуру данных целиком (список или дерево), а нодами – элементы этих структур. К тому же, бакет (как элемент массива бакетов) может быть null. Нода в нем будет создана лишь при добавлении первого значения.

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

По умолчанию, в HashMap создается 16 бакетов (если в конструкторе явно не указан параметр capacity). В течении жизни объекта это число может быть увеличено, в зависимости от размера коллекции, точнее, в зависимости от значения поля threshold.

Определение значения threshold, какую роль в этом играет loadFactor и как это все отражается на числе бакетов в мапе – несложная, но отдельная тема, которая поверхностно будет затронута в рамках одной из статей ниже. Пока лишь скажу, что если объект HashMap был создан конструктором по умолчанию – количество бакетов (размер массива бакетов) будет как минимум на четверть превышать количество элементов в мапе до тех пор, пока число бакетов не достигнет максимального – 2³°.

Таким образом, добавление новой пары «ключ-значение» в HashMap сводится к:

1.    Определению ее бакета на основании хэш-функции, которая работает на основании хэш-кода ключа. Подробнее – см. метод hash() в HashMap;

2.    Последующему добавлению ноды в рамках бакета или изменению значения существующей, если ключ равен по equals() какому-то из ключей уже существующих нод в этом бакете.

Вместе с этим бакет может быть превращен из списка в дерево, если добавляемая нода – 8я в рамках этого бакета. А размер массива бакетов может быть увеличен, если, с учетом нового значения, размер мапы превысил значение threshold.

Получение же значения по ключу, в свою очередь, сводится к:

1.    Нахождению бакета на основании хэш-функции (снова hash());

2.    Поиску нужной ноды по equals(), если бакет не пуст.

3.    Если подходящая нода найдена – будет возвращено значение, которое в ней хранится. В противном случае вернется null.

!NB: если объект ключа был изменен после вызова put() – операция get() по этому же ключу ничего не найдет. В целом, не рекомендую использовать мьютабельные объекты в качестве ключа.

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

Теперь, как и обещал, две статьи. Рекомендую изучить обе.

Более подробное объяснение с картинками, примерами и фрагментами кода. На мой взгляд, очень хорошая для новичков: https://habr.com/ru/post/421179/

Очень интересная статья, с более глубоким погружением в кодовую базу и с достаточно любопытными замерами для разных операций, рекомендую смотреть после изучения предыдущей: https://habr.com/ru/post/128017/

Единственный серьезный недостаток второй статьи – она была написана до выхода Java 8 и, соответственно, не учитывает добавленную возможность превращения списка нод в RB-tree. В остальном, она все еще достаточно актуальна.

LinkedHashMap

LinkedHashMap, являясь прямым наследником HashMap, почти не отличается от предка в плане устройства. Единственным важным нюансом является собственный потомок класса HashMap.Node – вложенный класс Entry, имеющий два новых поля – before и after – для хранения ссылок на следующий и предыдущий элементы, на основании которых и достигается сохранение порядка элементов. Первый и последний элементы мапы (в порядке добавления) хранятся в полях LinkedHashMap – head и tail соответственно.

Весь остальной код LinkedHashMap так или иначе связан с тем, чтобы учесть и использовать вышеописанную надстройку на HashMap, не дублируя описание логики самой HashMap. В целом, я склонен считать этот класс очень хорошим примером наследования. По крайней мере, если не касаться вложенных классов в (Linked)HashMap и их иерархии.

Интересный факт: если вы смотрели исходный код HashMap, то могли заметить, что HashMap.TreeNode наследуется именно от LinkedHashMap.Entry, что позволяет не дублировать подобный вложенный класс в самой LinkedHashMap.

TreeMap

Данная реализация, как вы помните, не имеет отношения к рассмотренным выше. Она является полностью самостоятельной и реализует собой красно-черное дерево.

Но поскольку реализация стандартных операций (put(), remove() и get()) сводится к реализации операций RB-tree (вставка, удаление и поиск соответственно) и не представляет особого интереса (то, что вы увидите в исходном коде этой коллекции не будет кардинально отличаться от описания алгоритма операций с бинарным деревом поиска на условной Википедии), я предлагаю более подробно изучить то, как реализована перекраска (и балансировка) дерева в TreeMap при вставке и удалении элементов. По крайней мере, эти алгоритмы сложнее, чем вставка, удаление и поиск сами по себе.

Перекраска и балансировка тоже мало чем отличаются от своих описаний в любой статье об RB-tree, но это лаконичная и понятная реализация данных операций. Оборачиваясь назад, мне этот код дал намного больше для понимания данных операций в красно-черном дереве, чем уроки и статьи. Для заинтересовавшихся:

·      Удаление – от deleteEntry() дальше в fixAfterDeletion();

·      Добавление – fixAfterInsertion() – непосредственно перекраска узлов после вставки нового элемента.

·      Балансировка после перекраски – rotateLeft() и rotateRight() для поворота влево и вправо соответственно. Могут быть вызваны как из fixAfterDeletion(), так и из fixAfterInsertion().

Это, кажется, первый раз, когда я в рамках статьи явно призываю к просмотру исходного кода. Если вам интересна тема деревьев – не стоит игнорировать, вам понравится.

HashSet, LinkedHashSet, TreeSet

Все три указанные реализации строятся на соответствующих им HashMap, LinkedHashMap и TreeMap.

Вне зависимости от того, о каком именно классе идет речь – он имеет поле, хранящее соответствующую Map’у (но не всегда имеет к нему доступ). Элементы сета – ключи данной мапы, а значения представлены константным объектом – значением static final поля PRESENT, которое инициировано как new Object().

В свою очередь, любая операция по добавлению/удалению элементов представляет соответствующую операцию для мапы. Ключ – добавляемый объект, значение (если требуется) – PRESENT.

Метод contains() сводится к вызову containsKey() у мапы, а методы TreeSet, возвращающие новые Set’ы – сводятся к вызову конструктора TreeSet с параметром Map, где Map – результат аналогичной операции в рамках TreeMap.

Интересный факт: LinkedHashSet, не считая метода spliterator(), содержит лишь конструкторы. Все они ведут к вызову конструктора суперкласса – HashSet, сделанному специально для LinkedHashSet – лишь он инициирует внутреннюю мапу как LinkedHashMap, а не как HashMap. Таким образом, на уровне LinkedHashMap отсутствует доступ даже к собственной внутренней мапе (поле map у HasheSet имеет модификатор private), хранящей значения этой коллекции. Что, к слову, является достаточно интересный примером инкапсуляции.

С теорией на сегодня все!

Учитывая тему урока, я не вижу возможности дать по нему практику. Однако могу посоветовать покопаться в исходниках HashMap. Качество кода отвратительное, зато можно открыть для себя много нового.

Если что-то непонятно или не получается – welcome в комменты к посту или в лс:)

Канал: https://t.me/+relA0-qlUYAxZjI6

Мой тг: https://t.me/ironicMotherfucker

Дорогу осилит идущий!