Всем привет, я третий.

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

1. Можете ли вы рассказать о структуре данных HashMap?

Структура данных JDK1.7 такова数组+链表, JDK1.7 все еще используется? Ни за что……

Давайте поговорим о структуре данных JDK1.8:

Структура данных - JDK1.8数组+链表+红黑树.

Схема структуры данных выглядит следующим образом:

Среди них массив бакетов используется для хранения элементов данных, связанный список используется для разрешения конфликтов, а красно-черное дерево используется для повышения эффективности запросов.

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

2. Как много вы знаете о красно-черных деревьях? Почему бы не использовать бинарное дерево/сбалансированное дерево?

Красно-черное дерево по сути является бинарным деревом поиска, для сохранения баланса оно добавляет к бинарному дереву поиска некоторые правила:

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

Почему бы не использовать бинарное дерево:

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

Почему бы не использовать сбалансированное бинарное дерево:

Сбалансированное бинарное дерево является более строго сбалансированным деревом, чем красно-черное дерево.Для поддержания баланса требуется больше поворотов, а это означает, что сбалансированное бинарное дерево менее эффективно для поддержания баланса, поэтому эффективность вставки и удаления у сбалансированного бинарного дерева выше, чем у красно-черного дерева.

3. Знаете ли вы, как красно-черное дерево сохраняет равновесие?

Красно-черные деревья сбалансированы двумя способами:旋转и染色.

• Вращение: есть два типа вращения, левостороннее и правостороннее.

• Краситель:

4. Знаете ли вы процесс установки HashMap?

Давайте начнем с диаграммы потока:

1. Во-первых, значение хеш-функции искажается для получения нового значения хеш-функции.(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. Определите, пуста ли вкладка или длина равна 0, и если да, выполните операцию раскрытия.

   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;
   

3. Рассчитать индекс в соответствии с хеш-значением.Если соответствующий индекс не хранит данные, его можно вставить напрямую, в противном случае его необходимо перезаписать.tab[i = (n - 1) & hash])

4. Определить, является ли tab[i] узлом дерева, иначе вставить данные в связанный список, и если да, то вставить узел в дерево.

5. Если длина связанного списка больше или равна 8 при вставке узла в связанный список, связанный список необходимо преобразовать в красно-черное дерево.treeifyBin(tab, hash);

6. Наконец, после обработки всех элементов определите, превышен ли порог;thresholdПревзойти, расширить его.

5. Как Hashmap находит элементы?

Сначала посмотрите на блок-схему:

Поиск HashMap намного проще:

1. Используйте функцию возмущения, чтобы получить новое значение хеш-функции.
2. Вычислить индекс массива, получить узел
3. Текущий узел соответствует ключу и возвращается напрямую
4. В противном случае, является ли текущий узел узлом дерева, найти красно-черное дерево
5. В противном случае пройдитесь по связанному списку, чтобы найти

6. Как устроена функция хеширования/возмущения HashMap?

Хэш-функция HashMap заключается в том, чтобы сначала получить хэш-код ключа, который является 32-битным значением типа int, а затем XOR над старшими 16 битами и младшими 16 битами хэш-кода.

    static final int hash(Object key) {
        int h;
        // key的hashCode和key的hashCode右移16位做异或运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Это сделано для уменьшения вероятности коллизий хэшей.

7. Почему функция хеширования/возмущения уменьшает коллизии хэшей?

Поскольку функция Key.HashCode () вызывает функцию хешей, которая поставляется с типом значения ключа клавиш и возвращает значение int Hash. Диапазон значений INT-2147483648~2147483647, что в сумме составляет около 4 миллиардов картографических пространств.

До тех пор, пока хэш-функция отображается равномерно и нечетко, для обычных приложений трудно столкнуться. Но проблема в том, что массив длиной 4 миллиарда не помещается в память.

Если начальный размер массива HashMap составляет всего 16, вам нужно использовать операцию по модулю над длиной массива до этого, а остаток можно использовать для доступа к индексу массива.

Операция по модулю в исходном коде состоит в том, чтобы сделать "与&", побитовые операции выполняются быстрее, чем операции с остатком %.

bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
     return h & (length-1);
}

Кстати, это также точно объясняет, почему длина массива HashMap возводится в степень двойки. Потому что это (длина массива - 1) точно эквивалентно "младшей битовой маске".与Результатом операции является то, что все старшие биты хеш-значения обнуляются, и только младшие биты сохраняются для доступа к индексу массива. Возьмите начальную длину 16 в качестве примера, 16-1 = 15. Двоичное представление 0000 0000 0000 0000 0000 0000 0000 1111. делать с некоторым хеш-значением与Операция выглядит следующим образом, и результатом является усечение самого младшего четырехбитового значения.

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

В этот момент扰动函数Значение отражено, посмотрите на принципиальную диаграмму функции возмущения:

Сдвиньте вправо на 16 бит, что составляет ровно половину битов 32. Цель операции XOR над старшей и младшей половиной исходного хэш-кода состоит в том, чтобы смешать старшие и младшие биты исходного хэш-кода, чтобы увеличить случайность младших битов. Более того, смешанные младшие биты дополняются некоторыми свойствами старших битов, так что старшие биты также сохраняются в замаскированном виде.

8. Почему емкость HashMap кратна 2?

• Первая причина заключается в облегчении хеш-остатка:

Помещение элемента в массив таблицы означает использование хеш-значения % размера массива для определения позиции, в то время как HashMap использует хэш-значение & (размер массива -1), но он может достичь того же эффекта, что и раньше, благодаря размеру HashMap кратен 2, кратность 2 означает, что только одна из двоичных цифр числа равна 1, а число -1 может привести к тому, что 1 в двоичной цифре станет 0, а следующий 0 станет 1 , а затем через операцию & можно получить тот же эффект, что и %, а битовые операции намного эффективнее, чем %

Когда емкость HashMap равна n-й степени числа 2, двоичный код (n-1) имеет вид 1111111***111, так что при выполнении битовой операции с хеш-значением добавляемого элемента можно достаточно хеширован, чтобы добавленные элементы были равномерно распределены в каждой позиции HashMap, уменьшая коллизии хэшей.

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

Мы можем просто посмотреть на механизм расширения HashMap, элементов в HashMap больше, чем负载因子*HashMapРасширение возникает, когда размер увеличивается.

9. Если HashMap инициализирован, передайте значение 17.new HashMap<>, что он будет делать?

Проще говоря, при инициализации, когда проход не кратен 2, HashMap будет искать.离得最近的2的倍数, поэтому передается 17, но фактическая емкость HashMap равна 32.

Давайте посмотрим на детали В инициализации HashMap есть такой метод;

public HashMap(int initialCapacity, float loadFactor) {
 ...
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}

• Пороговое значение , по методу tableSizeForРасчет выполняется по параметрам, переданным при инициализации.
• В то же время этот метод также должен найти наименьшее двоичное значение, которое больше начального значения. Например, если 17 передано, я должен найти 32.

static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

• MAXIMUM_CAPACITY = 1
• Процесс вычисления состоит в том, чтобы сдвинуться вправо на 1, 2, 4, 8, 16 и сделать то же самое, что и исходное число.|Операция, это в основном для заполнения 1 в каждой позиции двоичного файла.Когда каждая позиция двоичного файла равна 1, это стандартное кратное 2 минус 1, и, наконец, добавить 1 к результату и вернуть его.

Взяв за пример 17, рассмотрим процесс инициализации емкости расчетной таблицы:

10. Какие еще способы построения хеш-функций вы знаете?

Метод конструктора хеша в HashMap называется:

• Разделить с остатком: H(key)=key%p(p

Кроме того, существует несколько распространенных методов построения хэш-функции:

• прямая адресация

  непосредственно на основеkeyДля сопоставления с соответствующей позицией массива, например, 1232 помещается в позицию нижнего индекса 1232.

• цифровой анализ

  Выбиратьkeyнекоторые цифры (например, десятки и сотни) в качестве местоположения отображения

• квадратный метод

  ВыбиратьkeyСредние биты квадрата используются в качестве местоположения отображения.

• метод складывания

  будетkeyРазделите на несколько сегментов с одинаковым количеством цифр, а затем используйте их сумму суперпозиции в качестве местоположения карты

11. Каковы способы разрешения коллизий хэшей?

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

• метод цепного адреса: Вытащите связанный список из конфликтующей позиции и поместите в него конфликтующие элементы.

Кроме того, есть несколько распространенных способов разрешения конфликтов:

• открытая адресация: Метод открытой адресации заключается в поиске вниз от конфликтующей позиции, чтобы найти место для конфликтующего элемента.

  Есть также много способов найти свободное местоположение:

  • Зона LAN: начиная с позиции конфликта, определите, простаивает ли следующая локация, пока не найдете свободную локацию.
  • Метод квадратного щупа: начните с конфликтующей позиции x и увеличьте в первый раз1^2положение, второе повышение2^2... пока не найдется свободное место
  • ...

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

12. Почему порог преобразования связанного списка HashMap в красно-черное дерево равен 8?

Дерево возникает, когда длина массива таблиц больше 64, а длина связанного списка больше 8.

Почему 8? Комментарии в исходном коде также дают ответ.

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

Почему для порога выбрано 8? связанные со статистикой. В идеале, используя случайный хеш-код, узлы в связанном списке соответствуют распределению Пуассона, а вероятность появления количества узлов уменьшается.Когда количество узлов равно 8, вероятность появления равна только0.00000006.

Что касается перехода красно-черного дерева обратно в связанный список, то почему порог 6 вместо 8? Это связано с тем, что если этот порог также установлен на 8, если произойдет коллизия, а увеличение или уменьшение узла составляет около 8, произойдет непрерывное преобразование связанного списка и красно-черного дерева, что приведет к пустой трате ресурсов. .

13. Когда будет сделано дополнение? Почему коэффициент расширения 0,75?

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

Этот临界值thresholdОн определяется коэффициентом загрузки и вместимостью текущего контейнера.Если используется метод строительства по умолчанию:

Порог (threshold) = емкость по умолчанию (DEFAULT_INITIAL_CAPACITY) * коэффициент расширения по умолчанию (DEFAULT_LOAD_FACTOR)

это больше, чем16x0.75=12, будет запущена операция расширения.

Так почему же вы выбрали 0,75 в качестве коэффициента загрузки по умолчанию для HashMap?

Проще говоря, это空间стоимость и时间Учет баланса затрат.

В HashMap есть такой комментарий:

Все мы знаем, что метод построения хэша HashMap заключается в том, чтобы взять оставшуюся часть хэша, а коэффициент загрузки определяет, когда количество элементов достигает расширения.

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

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

14. Вы понимаете механизм расширения?

HashMap реализован на основе массива + связанного списка и красно-черного дерева, но длина массива сегментов, используемого для хранения значения ключа, фиксирована и определяется параметром инициализации.

Затем, с увеличением количества вставок данных и коэффициента загрузки, необходимо расширить емкость для хранения большего количества данных. Очень важным моментом в расширении является операция оптимизации в jdk1.8, избавляющая от необходимости пересчитывать хэш-значение каждого элемента.

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

Посмотрите на эту картинку, n — длина стола, на картинкеaУказывает, что два ключа, key1 и key2 перед расширением, определяют положение индекса.bУказывает, что два ключа, key1 и key2, определяют позицию индекса после раскрытия.

После того, как элемент пересчитает хэш, поскольку n удваивается, диапазон маски n-1 на 1 бит больше в старшей позиции (красный), поэтому новый индекс изменится следующим образом:

Поэтому при расширении емкости нужно только посмотреть, является ли новая цифра исходного хеш-значения 0 или 1. Если это 0, то индекс не изменится, а если 1, то станет原索引+oldCap, посмотрите принципиальную схему расширения 16 до 32:

Основная логика миграции узла расширения:

15. Какие оптимизации сделал jdk1.8 для HashMap? Зачем?

HashMap jdk1.8 имеет пять основных оптимизаций:

1. структура данных: Массив + связанный список меняется на массив + связанный список или красно-черное дерево

   原因: при возникновении конфликта хэшей элемент будет сохранен в связанном списке.Если связанный список слишком длинный, он будет преобразован в красно-черное дерево, а временная сложность будет изменена сO(n)сокращено доO(logn)

2. Метод вставки связанного списка: метод вставки связанного списка изменен с метода вставки заголовка на метод вставки хвоста.

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

   原因: Поскольку метод вставки заголовка 1.7 приведет к обращению связанного списка, когда для расширения используется метод вставки заголовка, и в многопоточной среде возникнет петля.

3. Рефанте: при расширении 1.7 необходимо повторно хешировать элементы в исходном массиве и размещать их в новой позиции массива, 1.8 использует более простую логику оценки, не нужно пересчитывать позицию с помощью хеш-функции, новая позиция остается неизменной или индекс + новый размер емкости.

   原因：Повысьте эффективность расширения и расширяйтесь быстрее.

4. Время расширения: При вставке 1.7 сначала определяет, требуется ли расширение, а затем вставляет, 1.8 сначала вставляет, а затем определяет, требуется ли расширение после вставки;

5. хэш-функция: 1.7 сделал четыре сдвига и четыре XOR, а jdk1.8 сделал это только один раз.

   原因: Если вы сделаете это 4 раза, предельная полезность будет небольшой. Измените ее на один раз, чтобы повысить эффективность.

16. Можете ли вы разработать и реализовать HashMap самостоятельно?

этот вопросбыстрый работникЧастые экзамены.

Не паникуйте, красно-черная версия дерева более написана, но версия массива + связанная невелика, и ее можно увидеть в деталях:Рукописный HashMap, интервьюер Kuaishou назвал эксперта!.

Общий дизайн:

• Хеш-функция: hashCode() + метод деления и остатка
• Разрешение конфликтов: метод цепных адресов
• Расширение: повторное хеширование узла для получения местоположения

Полный код:

17. Безопасна ли поток Hashmap? В чем проблема с многопотативной?

Hashmap не является безопасным потоком, и эти проблемы могут возникнуть:

• Бесконечный цикл расширения при многопоточности. HashMap в JDK1.7 использует метод вставки заголовков для вставки элементов.В многопоточной среде расширение может привести к появлению кругового связанного списка, образуя бесконечный цикл. Таким образом, JDK1.8 использует метод вставки хвоста для вставки элементов, и исходный порядок элементов связанного списка будет поддерживаться во время расширения, и проблема кругового связанного списка не возникнет.

• Многопоточная установка может привести к потере элементов. Несколько потоков выполняют операцию размещения одновременно. Если вычисленные позиции индекса совпадают, это приведет к тому, что предыдущий ключ будет перезаписан последним ключом, что приведет к потере элементов. Эта проблема существует как в JDK 1.7, так и в JDK 1.8.

• Когда put и get являются параллельными, это может привести к тому, что get будет нулевым. Когда поток 1 выполняет put, он вызывает перехеширование, поскольку количество элементов превышает пороговое значение, а поток 2 в это время выполняет get, что может вызвать эту проблему. Эта проблема существует как в JDK 1.7, так и в JDK 1.8.

18. Есть ли способ решить проблему небезопасности потока HashMap?

В Java есть HashTable, Collections.synchronizedMap и ConcurrentHashMap для реализации поточно-ориентированной карты.

• HashTable напрямую добавляет ключевое слово synchronized в метод операции, чтобы заблокировать весь массив таблиц, и степень детализации относительно велика;
• Collections.synchronizedMap — это внутренний класс, который использует средство сбора коллекций, инкапсулирует объект SynchronizedMap путем передачи Map, определяет внутреннюю блокировку объекта и реализует ее через блокировку объекта в методе;
• ConcurrentHashMap использует блокировку сегмента в jdk1.7 и CAS+synchronized в jdk1.8.

19. Можете ли вы специально говорить о реализации ConcurrenthashMap?

Безопасность потоков ConcurrentHashmap основана на версии jdk1.7.分段锁Реализация в jdk1.8 основана наCAS+synchronizedвыполнить.

1.7 Блокировка сегмента

Структурно версия 1.7 ConcurrentHashMap использует механизм сегментированной блокировки, который содержит массив сегментов. Сегменты наследуются от ReentrantLock, а сегменты содержат массив HashEntry. Сам HashEntry представляет собой структуру связанного списка, которая может хранить ключи и значения. , Укажите на Указатель на следующий узел.

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

поставить процессы

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

1. Вычислите хэш, найдите сегмент и инициализируйте сегмент, если он пуст.
2. Используйте ReentrantLock для блокировки. Если блокировка не может быть получена, попробуйте выполнить вращение. Если вращение превышает количество раз, получение будет заблокировано, чтобы гарантировать, что блокировка должна быть успешно получена.
3. Обход HashEntry аналогичен HashMap. Ключ в массиве заменяется непосредственно как хеш. Если он не существует, он вставляется в связанный список. Связанный список работает так же.

получить процесс

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

1.8 CAS+synchronized

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

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

1. Сначала вычислите хеш, пройдитесь по массиву узлов, если узел пуст, инициализируйте его с помощью CAS+spin.

 tab = initTable();

инициализация массива узлов:

    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            //如果正在初始化或者扩容
            if ((sc = sizeCtl) < 0)
                //等待
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {   //CAS操作
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

2. Если текущая позиция массива пуста, записать данные напрямую через CAS spin

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

3. Если hash==MOVED, это означает, что требуется расширение, и расширение выполняется.

else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);

    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }

4. Если они не удовлетворены, используйте синхронизированный для записи данных и записывайте данные для оценки связанного списка и красно-черного дерева.Связанный список записывается так же, как HashMap, и хэш ключа перезаписывается.В противном случае вставка хвоста используется метод красно-черного дерева

 synchronized (f){
     ……
 }

получить запрос

get очень прост, в основном такой же, как HashMap, вычисляет позицию по ключу и возвращает таблицу, если ключ тот же.

20. Упорядочены ли внутренние узлы HashMap?

HashMap неупорядочен и вставляется случайным образом в соответствии со значением хеша. Если вы хотите использовать упорядоченную карту, вы можете использовать LinkedHashMap или TreeMap.

21. Как достигается LinkedHashmap?

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

Возможна сортировка по порядку вставки или порядку доступа.

22. Расскажите о том, как устроен TreeMap?

TreeMap сортируется в соответствии с естественным порядком Key или порядком Comprator, который реализуется внутри красно-черного дерева. Таким образом, либо класс, которому принадлежит ключ, реализует интерфейс Comparable, либо пользовательский компаратор, реализующий интерфейс Comparator, передается в TreeMap для сравнения ключей.

23. Расскажите о базовой реализации HashSet?

Нижний слой HashSet основан на Hashmap. (Исходный код HashSet очень маленький, потому что, кроме клона (), resightObject (), readObject (), которое hashset должно реализовать сам по себе, другие методы напрямую вызывают методы в hashmap.

Способ добавления HashSet напрямую вызывает метод PUT метода HASHMAP, принимает добавленный элемент в качестве ключа и новый объект в качестве значения, и напрямую вызывает метод PUT HASHMAP, который будет судить о том, успешно ли элемент в соответствии с ли элемент Возвращаемое значение пусто.

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

В методе putVal HashMap делается ряд суждений, и конечным результатом является то, что если ключ существует в HashMap, будет возвращено старое значение. Метод добавления HashSet вернет false.

            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

---

Ссылаться на:

[1]. HashMap общался с интервьюером полчаса

[2]. «Интервью с Дачангом» - Java Collection Serial 30 Questions

[3]. Руководство Face Book Глава 4 "Вставка данных HashMap, поиск, удаление, обход, анализ исходного кода"

[4]. 16 вопросов о базовых основаниях Java в «Я хочу ввести большой завод»

[5]. LinkedHashMap Data Structures

[6].Руководство по классике лица, глава 3 «Основные знания HashMap, функция возмущения, коэффициент нагрузки, разделение списка расширения, глубокое обучение»

[7]. Интервьюер: Почему коэффициент загрузки HashMap равен 0,75?

[8]. Интервью со старым врагом красно-черного дерева (прямое введение и глубокое понимание)

[9]. Принцип работы и реализация Java TreeMap

[10]. Рукописный HashMap, интервьюер Kuaishou назвал эксперта!

[11].Переосмысление HashMap в серии Java 8

---

Статья впервые опубликована в личном публичном аккаунтетрехконечное зло, добро пожаловать, обратите внимание!