Визуализация TreeMap и LinkedHashMap в Java

Я пытаюсь понять, как эти структуры данных на самом деле визуализируются. Он сказал, что TreeMap помещает записи в естественном порядке [ключей] и LinkedHashMap помещает записи в том порядке, в котором они вставлены.

Мой вопрос заключается в том, означает ли итерация для каждой из этих структур данных обход всех элементов, распределенных по всем сегментам (или внутреннему массиву)?

Насколько я понимаю, что, например, в случае TreeMapэлементы с одинаковым хеш-кодом помещаются в древовидную структуру [некоторого рода]. Следовательно, если TreeMap имеет элементы в 6 из 16 индексов [в своем массиве сегментов], он будет содержать 6 Treeх - по одному на каждого.

Точно так же в случае LinkedHashMap (который в действительности должен был называться DoublyLinkedHashMap), у каждого сегмента был бы свой двусвязный список.

Итак, как же происходит итерация? Это происходит по всем элементам во всех сегментах или только по элементам одного сегмента? Я ошибаюсь в своем предположении?

PS И похоже на Java 8, HashMap реализация использует Tree или же LinkedList в зависимости от количества элементов для каждого ведра, содержащего более 8 или менее 6 элементов, соответственно!

Источник

2 ответа

Решение

Исходный код для нормальных реализаций находится в файле src.zip, который поставляется с установками Oracle JDK.

TreeMap: Как указано в документации, это красно-черное дерево. Критическим кодом для простой итерации вперед по ключам является метод static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t), Он рекурсивно сканирует дерево в порядке left-parent-right. Это зависит от порядка расположения узлов в дереве в соответствии с их порядком ключей.

LinkedHashMap: У него есть двусвязный список в порядке поступления, наложенный поверх хеш-структуры с сегментами. Вложенный класс Entry продолжается HashMap.Node добавить before а также after Рекомендации. Обычная прямая итерация следует за after цепь.

Источник

Чтобы дополнить ответ @patricia-shanahan:

Чтобы добавить визуализацию в LinkedHashMap (это для Java 7 и старше, так как Java 8 отличается), предполагая, что элементы были добавлены в порядке A, B,..., E (и при условии A имеет хэш-код, который заставляет его упасть в ведро 0 или D имеет хэш-код, который помещается в корзину 3), HashMap с 4 ячейками будет иметь следующий макет ("|" представляет следующую переменную свойства в HashMap.Entry<K, V> в списке связанных ссылок):

║ 0 ║ 1 ║ 2 ║ 3 ║ 
╠═══╬═══╬═══╬═══╬
║ A ║   ║ B ║ D ║
╠═|═╬═══╬═|═╬═|═╬
║ E ║   ║ C ║nul║
╠═|═╬═══╬═|═╬═══╬
║nul║   ║nul║   ║    
╠═══╬═══╬═══╬═══╬

Кроме того, каждый из элементов, A...E, будет иметь две дополнительные ссылки (LinkedHashMap.Entry<K, V> после и до):

A---->B---->C---->D---->E      
^____|^____|^____|^____|

В общем, каждый LinkedHashMap.Entry<K, V> будет иметь 3 ссылки: next, after, а также before, Следовательно, существует один элемент, т.е. A (типа LinkedHashMap.Entry<K, V>), с тремя ссылками. TreeMap также имеет три ссылки, но они ссылаются на другие TreeMap.Entry<K, V>По разному для разных целей: parent, left, а также right,

Источник
Другие вопросы по тегам