1. Введение в карту
1.1 Зачем нужна карта
Коллекция, которую мы узнали ранее, называется коллекцией, и она может быстро находить существующие элементы.
И Map вызывается в "Core Java" --> mapping..
Граф сопоставленной модели выглядит следующим образом:
Итак, зачем нам нужна эта структура хранения данных? ? ? Например
- Будучи студентами, мы различаем разных студентов по их количеству студентов.Пока мы знаем номер студента, мы можем получить соответствующую информацию о студенте.. Вот что делает картографирование!
Есть много других примеров этого в жизни:Пока вы вынимаете свое удостоверение личности (ключ), вы можете доказать, что это вы сами (значение)
1.2 Разница между картой и коллекцией
1.3 Функция карты
Давайте посмотрим на исходный код Map:
Вот простые и часто используемые функции Map:
Далее обведено краснымКарта примечательных подкатегорий:
Во-вторых, введение в хэш-таблицу
Будь то Set или Map, мы обнаружим, что будут соответствующие -->HashSet,HashMap
Сначала мы должныПросмотр данных и связанных списков:
- Как связанные списки, так и массивы могут располагать элементы в том порядке, в котором хотят люди.аккуратный(Последовательное хранение и последовательное извлечение одинаково)
- Но в то же время это приносит и недостатки:Чтобы получить элемент, вам нужно посетить все элементы, пока не найдете его.
- Это заставит нас провести в нем много времени, обходя и получая доступ к элементам~
И есть другие структуры хранения:Не заботится о порядке элементов, может быстро найти данные элементов
- Один из них очень распространен:Хеш-таблица
2.1 Как работает хеш-таблица
хеш-таблицаДля каждого объекта вычисляется целое число, называемое хэш-кодом..в соответствии сЭти расчетыЦелое число (хэш-код) хранится в соответствующем месте!
В Java хеш-таблицы реализованы с использованием массивов связанных списков.Каждый список называется ведром.[Я написал это раньшеСортировка ведра так же проста, как это, который можно пересматривать и пересматривать]
на ведро можетВ случае занятых (хешкодный хэш-код одинаково, он хранится в том же месте), эта ситуация неизбежна, и это явление называется:хэш-коллизия
- В это время нужноИспользуйте этот объект, чтобы сравнить объект в корзине, чтобы увидеть, существует ли объект в корзине.~Если он существует, он не будет добавлен, если нет, он будет добавлен в корзину
- Конечно, если хэш-функция спроектирована достаточно хорошо, а количество сегментов достаточно, то такие сравнения редки~
- существуетJDK1.8середина,Когда ведро полноебудет отСвязанный список становится сбалансированным бинарным деревом
Если хеш-таблица переполнена,Необходимо повторно хешировать хеш-таблицу, создать хэш-таблицу с большим количеством сегментов, вставить исходные элементы в новую таблицу и отбросить исходную таблицу.~
- коэффициент нагрузкиОпределить, когдаПовторно хэшируйте хеш-таблицу~
- Коэффициент заполнения по умолчанию равен 0,75, если таблицаболее 75% позицийэлементы уже заполнены, то таблица будет использоватьУдвоить количество бочекАвтоматический повторный хэш
Конечно, будет продолжать объяснять при чтении исходного кода позже, теперь вы можете просто понять ~
Дальнейшее чтение:
3. Знакомство с красно-черным деревом
В приведенной выше хэш-таблице было упомянуто: если количество сегментов заполнено, JDK8Преобразование связанного списка в красно-черное дерево~. Более того, нижние слои наших TreeT и Treemap все реализуются красными черными деревьями.
Итак, узнайте, что такое волна красно-черных деревьев здесь.
Предыдущие статьи о бинарных деревьях:
Прежде чем учиться, мы, возможно, слышали о типе структуры данных, таком как красно-черное дерево и другие деревья B/B+ и т. д. В любом случае, этоболее сложные структуры данных~~~
Различные распространенные виды использования дерева:
источник:Ууху. Call.com/question/30…
3.1 Обзор бинарных деревьев поиска
Во-первых, давайте повторим: используя характеристики бинарных деревьев поиска, мы обычно можем очень быстро найти соответствующие элементы.
Но бинарные деревья поиска также имеют **случаи (наихудшие)** случаи (линейные):
Вышеизложенное соответствует характеристикам бинарного дерева, но оно линейно и не имеет никакого отношения к дереву~
Дерево должно быть «сбалансировано», чтобы показать его преимущества~, например:
Следовательно, естьСбалансированное деревоТакая концепция ~ Красно-черное дерево — это своего рода сбалансированное дерево, которое можетУбедитесь, что бинарное дерево в основном соответствует короткой и толстой (равновесной) структуре.
3.2 Знакомство с новым деревом 2-3
Говорил о сбалансированном дереве, который я должен был сказатьсамый простой2-3 дерева, 2-3 дереваЭто выглядит так:
В бинарном дереве поиска процесс вставки узла выглядит следующим образом: если значение узла меньше значения узла, продолжить сравнение с левым дочерним узлом справа, а если больше значение узла, продолжайте сравнивать с правым дочерним узлом, пока левый или правый дочерний узел узла не станет пустым, поставьте значение Insert it.Это не может избежать проблемы предвзятости
И дерево 2-3 уже не то:Он удерживает дерево сбалансированным при вставке!
Вставка дерева 2-3 может быть просто сведена к двум операциям:
- Объединить 2 узла в 3 узла, расширить 3 узла в 4 узла
- Разложить 4-узел на 3-узел, узел 3-узел на 2-узел
- ........сделать дерево сбалансированным~
Операция слияния и разложения по-прежнемуБолее сложные, есть несколько случаев, объем кода очень большой~ Я не буду его здесь представлять, потому что его сложно выучить~
3.3 От 2-3 деревьев к красно-черным деревьям
Из-за дерева 2-3 для поддержания баланса требуется большое количество обменов узлами во время обслуживания! Эти преобразования очень сложны в реальном коде, большие ребята.Красно-черное дерево было изобретено на основе теории 2-3 деревьев.(Дерево 2-3-4 то же самое, но дерево 2-3 — самый простой случай, поэтому я не буду говорить о дереве 2-3-4).
- Красно-черное дерево — это улучшение дерева поиска 2-3, которое может использоватьЕдиный способ полной конвертации всех.
Красно-черное дерево – этоСбалансированное бинарное дерево, поэтому у него нет 3-узлов. Как красно-черное дерево превращает 3-узлы в бинарные деревья?
Красно-черное дерево буквально означает,Есть красные узлы, есть черные узлы:
Мы можем поместить красный узеллевая ссылкаВзгляните на рисунок:
Типичное бинарное дерево:
После выравнивания левого звена красного узла: получаем сбалансированное дерево 2-3:
3.4 Базовые знания о красно-черных деревьях
Как упоминалось ранее, красное дерево гемо-дерево представляет собой дерево, реализуемое на основе 2-3, что может завершить все преобразования в единой способ. Очень хорошо понимать: красное черное дерево также является деревом баланса. Когда он вставлен в элемент, он должен держать баланс деревьев. Что такое красное черное дерево, чтобы сохранить баланс дерева?
Красно-черное дерево использует два метода замены постоянной операции обмена узлами дерева 2-3:
- вращать: Вращение по часовой стрелке и против часовой стрелки
- обратный цвет: поменять местами красный и черный цвета
- Эти две реализации удобнее, чем 2-3 узла обмена деревом (слияние, разделение)
Для сохранения баланса красно-черное дерево также имеет некоторые ограничения, и способность соблюдать эти ограничения называется красно-черным деревом:
- Красно-черное дерево - это двоичное поиск.
- Корневой узел черный.
- Каждый листовой узел представляет собой черный пустой узел (узел NIL)..
- Оба потомка каждого красного узла черные. (Не может быть двух последовательных красных узлов на всех путях от каждого листа к корню)
- Все пути от любого узла к каждому его листу содержат одинаковое количество черных узлов (количество черных узлов (называемых «черными высотами») в каждой цепочке дерева должно быть одинаковым)..
3.5 резюме красно-черного дерева
Красно-черное дерево можно сказать очень сложное.Когда я учился, я не вникал в детали обработки, я просто прошел его примерно и знал все~
С большим количеством высококачественных материалов от пожилых людей, я считаю, что если вы хотите понять детали, вы все равно можете освоить один или два, приложив немного усилий и времени.
Ссылки на красно-черное дерево:
- blog.CSDN.net/Chen_Zhang_…
- Особый день.GitHub.IO/blog/2016-3…
- woohoo.SOHU.com/ah/201923614…
- Эй. Краткое введение .com/fear/37 из 845 ах 5 ...
- Блог Woohoo.cn на.com/null these/afraid/61…
- blog.CSDN.net/non-33423/AR…
4. Резюме
Эта статья в основном знакомит с базовыми знаниями о коллекции Map и понимает общие подклассы Map~
Кратко представлены хеш-таблица и красно-черное дерево.Как нижний слой Hashxxx и Treexxx, они не будут так смущены, чтобы понять их общие идеи и связанные с ними основы при последующем просмотре исходного кода~
Последующие действия увидят исходный код Карта часто используемых подклассов, статьи, так что следите за обновлениями ~ ~ ~ ~
Проект с открытым исходным кодом, охватывающий все точки знаний о бэкэнде Java (уже 6 тысяч звезд):GitHub.com/Zhongf UC очень…
если ты хочешьв реальном времениЕсли вы обратите внимание на мои обновленные статьи и галантерейные товары, которыми я делюсь, поищите в WeChat.Java3y.
Содержимое PDF-документоввсе вручную, если вы ничего не понимаете, вы можете напрямуюспросите меня(В официальном аккаунте есть мои контактные данные).