Предварительные знания

Знание битовых операций

Битовые операции — это базовые операции, поддерживаемые процессором, а базовое оборудование поддерживает только такие числа, как 01, поэтомубитовая операцияОн работает быстро. Хотя современные компьютерные процессоры имеют более длинные конвейеры команд и лучшую архитектуру, операции сложения и умножения выполняются почти так же быстро, как битовые операции, но битовые операции потребляют меньше ресурсов. Обычно используются следующие битовые операции:

1. Бит И &

(1&1=1 1&0=0 0&0=0)

2. бит или |

(1|1=1 1|0=1 0|0=0)

3. немного не ~

( ~1=0 ~0=1)

4. Побитовое исключающее ИЛИ ^

(1^1=0 1^0=1 0^0=0)

5. Подпись правая смена >>

При выполнении операции сдвига вправо, если число, участвующее в операции, является положительным числом, к старшему разряду добавляется 0, если отрицательное число, к старшему разряду добавляется 1.

6. беззнаковый сдвиг вправо >>>

Независимо от того, является ли число, участвующее в операции, положительным или отрицательным числом, при выполнении операции к старшему биту будет добавлен 0.

7. сдвиг влево

Не существует такой вещи, как положительные и отрицательные числа для сдвига влево, потому что отрицательные числа представлены процессором.дополнятьХранится в виде , для положительных чисел сдвиг влево эквивалентен умножению на 2 в степени N.

Постучите по ключевым моментам: все вышеизложенное просто, чтобы привести к следующим выводам:

a % (Math.pow(2,n)) Эквивалентно a&( Math.pow(2,n)-1)

Напримерa%16Конечный результат должен быть0～15числа между, в то время какa&1111Тот факт, что остаток после деления а на 16 действителен, выявляется, потому что если это 1 1111, то первая цифра на самом деле представляет 16, то есть до тех пор, пока 1 появляется в двоичном коде с пятой последней цифры, это определенно представляет собой 16. кратное.в заключении: Битовая операция более эффективна, чем операция деления, старайтесь максимально использовать остаток числа.a&二进制数Это может ускорить лучше.

ArrayList

мы знаемArrayListпредставляет собой очередь массива, эквивалентнуюдинамический массив. По сравнению с базовыми массивами в Java его емкость может динамически расти. Он имеет следующие ключевые моменты.

1. ArrayList фактически передаетсямножестводля сохранения данных. Когда мы создаем ArrayList; если используется конструктор по умолчанию, размер емкости ArrayList по умолчанию равен10.
2. Когда емкости ArrayList недостаточно для хранения всех элементов, ArrayList сбрасывает емкость: в 1,5 раза больше исходной емкости.
3. Функция клонирования ArrayList, то есть все элементыклонв массив.
4. Нижний слой клона — System.arraycopy(0,oldsrc,0,newsrc,length);
5. Способ, которым ArrayList реализует java.io.Serializable. При записи в выходной поток сначала пишется «емкость», а затем по очереди пишется «каждый элемент»; при чтении входного потока сначала считывается «емкость», а затем по очереди считывается «каждый элемент».

преимущество:

1. Более эффективно перемещаться по элементам на основе индексов.
2. Более эффективно получать доступ к элементам на основе индексов.
3. На основе массива он инкапсулирует метод работы с элементами.
4. Такие динамические массивы пространственно непрерывны по внутренним адресам.
5. Может быть автоматически расширен.

недостаток:

1. Вставка и удаление относительно неэффективны.
2. Поиск элементов по содержанию менее эффективен.
3. Правила расширения: каждый раз расширяется 50% существующей емкости.

LinkedList

Двусвязный списокКаждый узел содержит три части (данные, предыдущая, следующая), что не требует непрерывности пространства. Аналогично связи между узлами и узлами через две линии до и после.

Сводка ArrayList и LinkedList:

1. ArrayList — это структура данных, основанная на динамических массивах, а LinkedList — на основе структуры связанного списка.
2. Для методов получения и установки произвольного доступа ArrayList лучше, чем LinkedList, потому что LinkedList должен перемещать указатель.
3. Для операций добавления и удаления добавление и удаление LinkedList является более доминирующим, поскольку ArrayList необходимо перемещать данные.
4. ArrayList используется вЗапросБольше, но меньше вставок и удалений, и LinkedList используется, когда меньше запросов и больше вставок и удалений.

RedBlackTree

Сначала вам нужнобинарное деревоИмейте понимание, знайте, что это такое, как комбинация данных, а затем знайте недостатки поиска по бинарному дереву, данные могут встречатьсянаклон. поэтому введенСбалансированное бинарное дерево, разница между глубинами левого и правого узлов сбалансированного бинарного дерева не превысит 1, а найти легко и строить хлопотно, поэтому снова появляетсякрасно-черное дерево. Красно-черное дерево представляет собой сбалансированное бинарное дерево поиска и является широко используемой структурой данных в информатике. Наиболее типичным применением является реализация ассоциации данных, например реализация структур данных, таких как карта. Важные характеристики красно-черное дерево (левый узел

1. Узлы должны быть красными или черными
2. Корневой узел черный
3. Все листовые узлы черные.
4. Два дочерних узла каждого красного узла черные, то есть не может быть родительских и дочерних узлов, которые все красные.
5. Количество черных узлов одинаково на всех простых путях от любого узла к каждому из его листовых узлов.

Если вы мало что знаете о красно-черных деревьях, то рекомендуется прочитать, что ранее писал блогерRBT

HashTable

Хеш-таблица — это особая структура данных, которая явно отличается от массивов, связанных списков и бинарных деревьев сортировки.В ней можно быстро найти записи, которые вы хотите найти, а не ключ к записям, существующим в таблице.Сравниваются слова для поиска их. Это происходит из-за особенностей дизайна хеш-таблицы, в котором используется идея == сопоставления функций == для связывания места хранения записи с ключом записи, чтобы ее можно было найти очень быстро. Ключ к производительности функции оценки заключается в ==коэффициенте загрузки== и в том, как разумно разрешать хеш-коллизии. Подробнее см. в том, что ранее писали блоггеры.Заполнить хеш-таблицу

Анализ исходного кода HashMap

Обзор

Обычно, с предвосхищением некоторых предыдущих пунктов знания, объяснение HashMap может быть хорошо проведено.ArrayList,LinkedList,Red Black TreeУ каждой есть свои преимущества и недостатки. Можем ли мы объединить сильные стороны сотен школ для получения комплексного продукта? === >HashMap, все объяснения в этой статье основаны на JDK8.

HashMapКомпоненты: массив + связанный список + красно-черное дерево.HashMapКостяк представляет собойNodeмножество.NodeдаHashMapосновные строительные блоки каждогоNodeсодержитkey-valueпара ключ-значение.HashMapК временной сложности чтения можно приблизиться почтиO(1)(может колебаться, если есть коллизия хэшей), иHashMapКоэффициент использования пространства обычно составляет около 40%.HashMapОбщая схема выглядит следующим образом: PS: несколько важных взаимосвязей узлов:

1. java.util.Map.Entry этоinterfaceОпределены некоторые интерфейсные функции для сравнения.
2. java.util.HashMap.Node это мыHashMapБазовый KV хранится в формате .
3. java.util.LinkedHashMap.Enrty EnrtyЭтот класс наследуется отHashMap.Nodeэтот класс,EnrtyдаLIinkedHashMapвнутренний класс ,
4. java.util.HashMap.TreeNode TreeNodeКонструктор отслеживает наследованиеLinkedHashMap.Entry, который, в свою очередь, унаследовалHashMap.Node. такTreeNodeкак естьNodeсвойства, добавляяprevЭтот указатель-предшественник делает == связанный список == == двунаправленным ==. Первые три узла относятся к пятому красно-черному дереву, а четвертый — кnextОтносится к двусвязным спискам. Есть три основных шага к хранению данных.
5. Каждый проход данныхHashTableФункция сопоставления, чтобы решить, куда поместить данные в массиве.Когда массив инициализируется, он должен быть степенью 2. Значение по умолчанию равно 16. Любое число, переданное во время инициализации, пройдетtableSizeForС поправкой на степень 2.
6. Используйте, если в одном и том же массиве выделено слишком много данныхметод связанного спискадля разрешения хэш-коллизий.
7. Если количество узлов данных связанного списка одного и того же узла >TREEIFY_THRESHOLD=8и длина массива >=MIN_TREEIFY_CAPACITY=64, связанный список будет развиватьсяRedBlackTree,еслиRedBlackTreeЧисло средних узлов меньшеUNTREEIFY_THRESHOLD=6превратится в связанный список.

специальное напоминание: Прежде чем читать исходный код HashMap, вам необходимо знать, что его общие характеристики таковы:

1. Доступ к HashMap не является последовательным
2. KV может быть NULL
3. В случае многопоточности этот класс безопасен, и можно рассматривать HashTable.
4. Нижний слой JDK8 — это массив + связанный список + красно-черное дерево, а нижний слой JDK7 — это массив + связанный список.
5. Начальная грузоподъемность и коэффициент загрузки являются ключевыми моментами, определяющими производительность всего класса, и их нелегко изменить.
6. HashMap этоленивыйСоздан, строится только при размещении данных
7. Когда односвязный список преобразуется в красно-черное дерево, он сначала изменится наДвусвязный списокнаконец-то превратился вкрасно-черное дерево, двусвязный список и красно-черное дерево共存Да, помните.
8. для входящих двухkey, он будет вынужден судить об уровне, а уровень суждения в основном заключается в том, чтобы решить, идти ли влево или вправо.
9. После преобразования связанного списка в красно-черное дерево он попытается преобразовать красно-черное дерево.rootУзлы и заголовки связанных списков, за которыми следуетtable[i]Узлы сливаются в один.
10. При удалении сначала определяют, нужно ли перенести в связанный список количество красно-черных деревьев удаляемого узла.RBTАналогичным образом найдите подходящий узел для заполнения удаленного узла.
11. красно-черное деревоrootузел不一定иtable[i]То есть головной узел связанного списка один и тот же, а синхронизация трех зависит отMoveRootToFrontосуществленный. иHashIterator.remove()буду звонитьremoveNodeкогдаmovable=false.

Важные параметры

статические параметры

1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4

Начальная емкость, емкость по умолчанию = 16, количество ящиков не может быть слишком большим или слишком маленьким. Если их слишком мало, легко вызвать расширение, если их слишком много, то обход хэш-таблицы будет медленнее.

2. static final int MAXIMUM_CAPACITY = 1 << 30

Максимальная емкость массива.В общем, пока памяти достаточно, хеш-таблица не будет иметь проблем.

3. static final float DEFAULT_LOAD_FACTOR = 0.75f

дефолткоэффициент нагрузки. Следовательно, изначально, когда количество всех сохраненных узлов > (16 * 0,75 = 12), будет запущено расширение. Коэффициент нагрузки по умолчанию (0,75) составляетстоимость времени и местаобеспечивает хороший компромисс. Более высокие значения уменьшают накладные расходы на пространство, но увеличивают стоимость поиска (отражено в большинстве операций, подобных HashMap, включая get и put). При задании начального размера следует учитывать ожидаемое количество записей в карте и коэффициент ее загрузки, а также минимизировать количество операций перехеширования. Если начальная емкость больше, чем максимальное количество записей, деленное на коэффициент загрузки, операция повторного хеширования не будет выполняться.

Как видно из приведенной выше таблицы, когда количество элементов в корзине достигает 8, вероятность становится очень маленькой, то есть при коэффициенте загрузки 0,75 это практически невозможно для длины связанного списка. каждой позиции столкновения, чтобы превысить 8. 4. статический финал int TREEIFY_THRESHOLD = 8

Это значение указывает, что когда длина связанного списка >= 8 в поле (элемент массива),возможныйпревратится в дерево. Установите на 8, это система в соответствии сраспределение ПуассонаДиаграмма распределения данных настроена.

5. static final int UNTREEIFY_THRESHOLD = 6

Если во время расширения хэш-таблицы длина связанного списка компромисс

Когда длина связанного списка равна 6, средняя длина запроса равна n/2=3, а log(6) красно-черного дерева = 2,6. Когда оно равно 8: связанный список 8/2=4, журнал красно-черного дерева(8)=3

6. static final int MIN_TREEIFY_CAPACITY = 64

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

Динамические параметры

1. transient Node<K,V>[] table

Массив связанных списков HashMap. Независимо от того, передаем ли мы параметры во время инициализации, при саморасширении это всегда степень числа 2.

2. transient Set<Map.Entry<K,V>> entrySet

Установить коллекцию Entry в экземпляре HashMap

3. transient int size

Количество экземпляров KV, хранящихся в таблице HashMap.

4. transient int modCount

что бы мы ни делалиДобавления, удаления и модификациивызоветmodCountИзменение значения, аналогично функции контроля версий, можно понимать какversion, при конкретной операции необходимоversionпроверить, подать заявкуFai-Fastмеханизм.

В java есть класс коллекцииFail-FastизМеханизм обнаружения ошибок, этот тип исключения может возникнуть, когда несколько потоков работают с содержимым одной и той же коллекции. Например, когда A проходит коллекцию через итератор, другие потоки модифицируют коллекцию, и она выдаетConcurrentModificationExceptionаномальный. Такие механизмы черезmodCountРеализовано, при инициализации итератора ему будет присвоено значениеexpectedModCount, оцениваемый в итеративном процессеmodCountиexpectedModCountЯвляется ли это последовательным.

5. int threshold

Пороговое значение расширения емкости = емкость * коэффициент нагрузки

6. final float loadFactor

Настраиваемый коэффициент нагрузки, но обычно используется системный коэффициент 0,75.

Четыре метода строительства

1. конструктор по умолчанию
2. Передайте начальный размер емкости
3. Размер входящей начальной емкости и коэффициент загрузки==tableSizeFor==: функция возвращает число, большее, чем входной параметр, и наименьшую целочисленную степень числа 2. Например, 10 вернет 16.Подробности следующие:

Давайте сначала проанализируем n-битную операцию: предположим, что двоичный код n равен 01xxx...xxx. тогда Сдвинуть n вправо на 1 бит: 001xx...xxx, ИЛИ: 011xx...xxx Сдвиг вправо n на 2: 00011...xxx, затем ИЛИ: 01111...xxx В этот момент перед ним уже четыре единицы, а затем сдвинем 4 бита вправо и бит ИЛИ может получить 8 единиц Точно так же, если есть 8 единиц, сдвиг вправо на 8 бит определенно сделает последние восемь бит также равными 1.

Подводя итог, этот алгоритм делает все биты после старшей 1 равными 1. Наконец, пусть получен результат n+1, то есть значение целой степени числа 2. Теперь вернемся к первому утверждению:

int n = cap - 1;

Цель переназначения cap-1 на n состоит в том, чтобы найти целевое значение, большее или равное исходному значению. Например, 1000 в двоичном формате, 8 в десятичном. Если вы не уменьшите его на 1 и будете действовать напрямую, вы получите ответ 10000, что равно 16. Явно не результат. После вычитания 1 двоичное значение равно 111, а путем повторной операции будет получено исходное значение 1000. Этот двоичный метод очень эффективен.

4. Конструктор переходит в карту используйте коэффициент нагрузки по умолчанию, затем в соответствии с текущимmapразмер, чтобы изменить требуемыйthreshold, а также может включатьresize, тогда живиputв контейнер.

Хэш-значение

ли мыputданные ещеgetДанные должны сначала получить соответствующую позицию данных в этой хеш-таблице. Напримерputданные, его процесс делится на 2 этапа.

1. Сначала получите хеш-значение, соответствующее ключу. 2. После хэш-значения A данных переместите A вправо без знака на 16 бит, а затем^чтобы получить окончательное значение. Эта операция называется扰动, причина в том, что вероятность того, что младшие цифры окажутся одинаковыми, слишком велика, и данные должны быть максимально реализованы.Равномерно распределены.

Возмущение JDK8 и JDK7 одновременнота же цель, но сложностьРазные.

1. get

Условно говоря, это очень просто, для удобства понимания поговорим об общем процессе написания кода.

1. Получите хеш ключа и потом ищите по хешу и ключу по идее вставкиget.
2. Если позиция массива равна NULL, верните NULL напрямую.
3. Если позиция массива не равна NULL, проверьте напрямую, соответствует ли позиция массива.
4. Если позиция массива имеет тип красно-черного дерева, она будет найдена и возвращена в соответствии с красно-черным типом дерева.
5. Если в массиве есть следующий, он ищется и возвращается в соответствии со способом обхода связанного списка.

1.1 getNode

Детали функции поиска макросов:

1.3 getTreeNode

Красно-черное дерево для поиска сведений об узле:

1. Сначала получите корневой узел, левый узел, правый узел.
2. Выполните пошаговый сужающий поиск данных в соответствии с левым узлом
3. Если реализован метод Comparable, он сравнивается напрямую.
4. В противном случае, если корневой узел не совпадает, функция поиска вызывается рекурсивно.

1.4 ComparableClassFor:

Запрос, реализован ли ключComparableинтерфейс.

1.5 compareComparables:

Теперь, когда интерфейс Comparable реализован, используйте реализацию для сравнения и определения направления.

2. положить процесс

Следуйте исходному коду, чтобы разобраться в общем процессе операции put.Общий процесс ввода данных выглядит следующим образом:

1. на данныхHashрасчет стоимости.
2. Перед вставкой данных проверьте текущуюtableгосударство, еслиtableпуст и должен быть вызванresizeдля инициализации.
3. Получено битовой операциейkeyцелевое местоположение. и определить текущее местоположение.
4. Если текущая позиция пуста, она будет размещена напрямую, а если она совпадает с текущей клавишей, она будет перезаписана.
5. Если в данный момент есть данные, посмотрите, является ли текущий тип данных красно-черным деревом, если да, то вам нужно вызватьputTreeVal.
6. В противном случае он считается связанным списком, а затем цикл ищет tail==insertion==. При этом необходимо считать текущий связанный список красно-черным деревом.

Найдите точку, которую нужно вставить в JDK8eЭто через == хвостовая вставка == (аналогично организации очереди в конце), а в JDK7 это == передняя вставка == (аналогично подключению спереди, причина этого в том, что изобретатель HashMap считает, что раздел вставляется после Вероятность доступа выше), и соответствующий код выглядит следующим образом.

7. для старых найденных узловeсудить

1. Если старое значение, соответствующее oldValue, равно NULL, то решает ли onlyIfAbsent заменить его или нет. будет заменен.
2. Если старое значение, соответствующее oldValue, не равно NULL, оно будет заменено, если onlyIfAbsent равно false.
3. onlyIfAbsent: Заменить, только если он отсутствует, без замены, если не отсутствует. поговорить с редисомSetnxТа же функция.

8. После того, как данные окончательно добавлены, необходимо исправить измененные переменные.modCountДобавьте 1 и посмотрите, нужно ли увеличить последнее общее количество узлов, и если да, то увеличьте емкость.

2 put

2.1 putTreeVal

1. Сначала найдите корневой узел, а затем определите, нужно ли искать ключ слева или справа.
2. Если он найден, он напрямую вернет найденный узел.
3. Если он не найден, новый узел будет помещен в соответствующую позицию, и будет рассмотрена ситуация вставки узла красно-черного дерева и двусвязного списка.

2.2 treeifyBin

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

2.3 treeify

Для создания двусвязного списка и красно-черного дерева основные шаги разбиты на 3 шага.

1. Найдите первый узел из двусвязного списка какrootузел.
2. Каждый узел двусвязного списка находит позицию в корневом узле как корень бинарного дерева, а затем вставляет данные в красно-черное дерево.При этом обратите внимание наbalance.
3. Наконец, обратите внимание на корневой узел с текущимtable[i]Соответствует хорошо.

2.4 moveRootToFront

убедитесь, чтоrootУзел перемещается вtable[first]На вышеизложенном, если красно-черное дерево будет успешно построено, а задача не будет выполнена успешно, это приведет кtablle[first]Соответствующий узел не является красно-черным деревомrootузел. При обычном выполнении основные шаги делятся на 2 шага.

1. Найдите замыкающий узел и поместитеrootУзел помещается в узел-последователь, и работа красно-черного дерева завершается.
2. Оригинальный заголовок цепочкиfirstузлы, которые теперь, вероятно, будут промежуточными узламиrootУзел перемещен вfirstперед узлом.вcheckInvariantsРоль функции: проверкаTreeNodeУдовлетворяет ли объект свойствам красно-черных деревьев и двусвязных списков. Потому что в параллельных ситуациях может возникнуть множество исключений.

3 resize

1. Получите данные старой таблицы.Если старая таблица достаточно велика, она не будет расширена, а будет скорректирован только порог.
2. Диапазон старой таблицы после расширения такжеудовлетворять потребностиНепосредственно расширить размер контейнера и порог.
3. Если это конструктор с параметрами, пороговое значение необходимо скопировать в емкость контейнера.
4. В противном случае считается, что контейнер был инициализирован без параметров и нуждается в инициализации.
5. Если в старой таблице есть данные, новая изменила размер и установила его, но порог не был успешно установлен. В этот момент устанавливается новый порог.
6. Создайте новый контейнер.
7. Старая таблица успешно расширяется в новую таблицу, что предполагает перенос данных.

1. Если данные не пусты и это отдельный узел, они будут напрямую повторно хешированы для назначения нового местоположения.
2. Если данные не пусты, за которыми следует связанный список, данные связанного списка должны быть дифференцированы, чтобы увидеть те, которые идут в старое место, и те, которые идут в новое место.
3. Если тип узла — красно-черное дерево, то вызывается разделение.

Перераспределение в форме связанного списка объясняется следующим образом: Примечание: не(e.hash & (oldCap-1))но(e.hash & oldCap), Последнее получается нужно ли перемещать позицию элемента в массиве, пример такой

Пример 1: е.хэш= 10 0000 1010 старыйCap=16 0001 0000 & =0 0000 0000 Сравнить первый бит старшего разряда 0в заключении: Позиция элемента в массиве не изменилась после расширения Пример 2: е.хэш= 17 0001 0001 старыйCap=16 0001 0000 & =1 0001 0000 Сравнить первый бит старшего разряда 1в заключении: положение элемента в массиве изменилось после расширения, и новая позиция нижнего индекса равна исходной позиции нижнего индекса + исходной длине массива.

3.1 split

Как быть с оригинальным после расширенияtable[i]Для красно-черного дерева выше общая идея кода аналогична коду при работе со связанными списками.Пока вы понимаете отношения узлов и сохраняете красно-черное дерево, вы также можете сохранить дважды связанный список.

4. find

Функция состоит в том, чтобы взять указанный узел в качестве корневого узла в соответствии с указаннымkeyиvalueнайти его.

1. Определите, следует ли искать слева или справа по хеш-значению.
2. Если он найден, его легко вернуть напрямую.
3. Могут быть одинаковые хэш-значения, ноkeyНе то же самое, продолжить поиск делится на три случая.

1. Если левый узел пуст, найдите правый узел
2. Если правый узел пуст, найдите левый узел
3. Левый и правый узлы не будут пустыми, попробуйте пройтиComparableНужно ли смотреть влево или вправо на данные.
4. Невозможно сравнить по сопоставимым или все еще равным после сравнения.

4. Поиск непосредственно из правого узла рекурсивно.
5. В противном случае посмотрите вверх слева.

4.1 tieBreakOrder

При сравнении двух объектов обязательно будет высокое и низкое сравнение.

1. Если a и b являются обеими строками, соревнование сразу завершается в решении if.
2. Если a и b оба являются объектами, непосредственно проверьте хэш-адрес объекта в JVM, а затем сравните.

4. remove

Только запись функции:

4.1 removeNode

removeNodeЭто не что иное, как проверить, существует ли table[i], а затем находится ли он на первом узле, находится ли он в красно-черном дереве или в связанном списке. В этих случаях, если он найден, удалите его напрямую и обратите внимание на баланс.

4.2 removeTreeNode

Цель этой функции - убрать вызов этого методаузел, который является узлом this в методе. удалить включаетсвязанный списокобработка икрасно-черное деревообработка. Вы можете увидеть, что было написано ранееRBT, идея примерно такая же при удалении, которое примерно разделено на 3 шага.

1. Красно-черное дерево также является двусвязным списком.Узел удаляется с точки зрения связанного списка, а затем оценивается, должен ли он выродиться в связанный список.
2. Согласно текущемуpузел пытаетсяprнайти больше всегомаленькийиз или изplнайти больше всегоБольшойцелевой узелs, преобразуйте две точки.
3. найтиreplacementприходи и следуйpсделать замену.
4. Реализовать замену.
5. После замены может потребоваться сохранение красно-черных характеристик дереваbalance.

4.3 untreeify

Красно-черное дерево вырождается в связанный список

4.4 balanceDeletion

Что касается этой проблемы, вы можете непосредственно увидеть добавление и удаление дяди Красного и Черного, написанное блогером ранее.RBT

Проблема с мертвой петлей JDK7

JDK7 против старогоtableданные перенесены на новыйtableФункцияtransferТаким образом, отмечены ключевые точки интереса.

1. пробка для головыПри нормальных обстоятельствах:
2. Параллельно Поток 1 выполняется толькоEntry<K,V> next = e.nextОн приостанавливается, и поток 2 выполняется нормально.В результате получается следующее:Затем поток 1 продолжает выполнение следующим образом:Благодаря пошаговому анализу и рисунку можно узнать, что будет цикл.

Метод удаления HashIterator

7vs8

1. найти в 7HashИспользовался 4 раза, только 1 раз из 8.
2. 7 = массив + связанный список, 8 = массив + связанный список + красно-черное дерево
3. 7 — метод вставки головы, многопоточность легко вызывает петли, а 8 — метод вставки хвоста.
4. Расширение 7 заключается в перемещении всех данных, а в 8 позиция остается неизменной + старый размер перемещается для достижения лучшего.
5. 7 — сначала решить, следует ли расширять, а затем вставлять, а 8 — сначала вставлять, а затем смотреть, следует ли расширять.
6. HashMapНезависимо от 78, это небезопасно на сайте, не забывайте использовать его в многопоточных ситуациях.ConcurrentHashmap.ConcurrentHashmapВ следующей статье говорится.

Общая проблема

Случайно собрал некоторые общиеHashMapПроблема в том, что если вы понимаете приведенный выше код, то разобраться с ним не составит труда.

1. Принцип HashMap, внутренняя структура данных.
2. Общий процесс размещения, получения и удаления в HashMap.
3. Реализация хеш-функции в HashMap.
4. Как расширить HashMap.
5. Почему несколько важных параметров HashMap заданы именно так.
6. Почему HashMap не является потокобезопасным и как его заменить.
7. Разница между HashMap в JDK7 и JDK8.
8. Связанный список и красно-черное дерево переключают идеи в HashMap.

Ссылаться на

Объяснение HashMap Подробное объяснение HashMap Бесконечный цикл вакцины JAVA HASHMAP

В этой статье используетсяmdniceнабор текста