Статья для выяснения внутренней структуры HashMap и TreeMap

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

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

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

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

Количество сегментов в HashMap — это длина массива 0-n на рисунке ниже.Место, где хранится первая запись, называется сегментом, и в сегменте может храниться только одно значение, которое является головным узлом. связанного списка.Узел является добавленной стоимостью (какие свойства экземпляра Entry внутреннего класса HashMap будут подробно описаны позже).

Это также можно понимать таким образом, массив хранения связанных списков типа записи. Индексная позиция массива — это индексный адрес каждого сегмента.

Из приведенного выше рисунка видно, что хэш-таблица состоит из массива + связанный список, В массиве длиной 16 каждый элемент хранит головной узел связанного списка. Итак, по каким правилам эти элементы хранятся в массиве?

В общем случае получается по hash(key)%len, то есть хэш-значение ключа элемента является по модулю длины массива. Например, в приведенной выше хеш-таблице 12%16=12, 28%16=12, 108%16=12, 140%16=12. Таким образом, 12, 28, 108 и 140 хранятся в индексе 12 в массиве.

1. HashMap — это цепочный массив (массив, в котором хранится связанный список), который может достигать скорости запроса и может быстро получить значение, соответствующее ключу;

2. Факторами, влияющими на скорость запросов, являются емкость и коэффициент загрузки.Большая емкость и малый коэффициент загрузки приводят к более высокой скорости выполнения запросов, но к потере места, и наоборот;

3. Значение индекса массива (ключевое слово, hashcode — хеш-значение ключа, len — размер массива): определяется значением hashcode%len, если емкость большая, а коэффициент загрузки small, индекс тот же (один и тот же индекс означает, что он указывает на Вероятность одного и того же сегмента) мал, и скорость запроса выше, если длина связанного списка мала.

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

5. Каждое ведро в HashMap хранит только один элемент (объект Entry) в любой момент времени. Поскольку объект Entry может содержать ссылочную переменную, указывающую на следующую Entry, может быть только одна Entry в корзине (bucket) HashMap, но эта Entry указывает на другую Entry, образуя таким образом цепочку Entry.

6. В приведенном выше исходном коде обнаружено, что HashMap обрабатывает пары ключ-значение как единое целое на нижнем уровне (объект Entry). Это целое является объектом Entry. Когда система решает сохранить пары ключ-значение в HashMap, она не учитывает значение в Записи вообще, а только Место хранения каждой Записи определяется в соответствии с хэш-значением ключа.

будь осторожен

JDK1.8 использует массив Node для хранения данных, но этот Node может быть структурой связанного списка или красно-черной древовидной структурой.Если хэш-код вставленных ключей одинаков, то эти ключи также будут расположены в одной сетке массива узлов. .

Если в одной сетке не более 8 ключей, используйте для хранения структуру связанного списка. Если их больше 8, будет вызвана функция treeifyBin для преобразования связанного списка в красно-черное дерево. Таким образом, даже если хэш-коды точно такие же, из-за характеристик красно-черного дерева для поиска определенного элемента требуется только O (log n) служебных данных.

Другими словами, наихудшая временная сложность операции put/get составляет всего O(log n).

1. Красно-черное дерево — это приблизительно сбалансированное бинарное дерево поиска, обеспечивающее, чтобы разница высот между левым и правым поддеревьями любого узла не превышала в два раза меньшего. В частности, красно-черное дерево — это бинарное дерево поиска, удовлетворяющее следующим условиям:

При изменении структуры дерева (вставка или удаление) вышеприведенное условие 3 или условие 4 часто нарушается, и приходится настраивать дерево поиска для повторного удовлетворения условий красно-черного дерева.

2. Нижний слой TreeMap реализуется красно-черным деревом.Например, при помещении пары ключ-значение в объект TreeMap будет сгенерирован объект Entry.Этот объект является узлом красно-черного дерева. черное дерево.По сути, это то же самое, что и HashMap.Точно так же объект Entry используется в качестве узла, но способ хранения этих узлов отличается.

3. При сохранении каждого объекта Entry он будет храниться в соответствии с размером ключевого ключа согласно спецификации бинарного дерева, поэтому данные в TreeMap сортируются по ключу от меньшего к большему.

Когда программа добавляет новый узел, она всегда начинает сравнение с корневого узла дерева, то есть корневой узел рассматривается как текущий узел. Если новый узел больше текущего узла и правый узел текущего узла существует, правый узел используется в качестве текущего узла; если новый узел меньше текущего узла и существует левый дочерний узел текущего узла левый дочерний узел используется как текущий узел;

Если новый узел равен текущему узлу, перезапишите текущий узел новым узлом и завершите цикл до тех пор, пока левый и правый дочерние узлы определенного узла не перестанут существовать, и добавьте новый узел в качестве дочернего узла этого узла. узел. Если новый узел больше этого узла, добавьте его как правого дочернего элемента. Если новый узел меньше этого узла, добавьте его в качестве левого дочернего элемента.

Прошу всех обратить внимание на мой официальный аккаунт [Программист в погоне за ветром], в нем будут обновляться статьи, а также размещаться отсортированная информация.