31 серийная пушка HashMap, я упал 5-го

обрати внимание на"Полный стек серверной технологии Java«Ответьте «000», чтобы получить много электронных книг

написать впереди

На собеседовании в основном нужно задавать HashMap, но метод опроса другой. Я также разговаривал со многими интервьюерами о HashMap, и с помощью HashMap можно проверить многие знания интервьюеров. К сожалению, многие люди попадают под гранатовую юбку HashMap..

Почему HashMap так популярен среди интервьюеров?

Я думаю, что на это есть 4 причины:

HashMap довольно часто используется в нашей работе.
Основы Java (доступно в этой коллекции Java)
Проблемы безопасности потоков (через эту проблему могут возникнуть проблемы, связанные с многопоточным параллельным программированием)
Большие фабрики спрашивают, как же им не спрашивать? (Если не спрашивать, кажется, что интервьюер не квалифицирован)

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

Вот 25 цепных пушек HashMap:

1: Какова основная структура данных HashMap?

2: Расскажите о характеристиках HashMap?

3: Что делать, если при использовании HashMap хэш-код двух объектов одинаков?

4: Как устроена хэш-функция HashMap?

5: Сколько способов обойти HashMap?

6: Почему XOR старших 16 бит и младших 16 бит хэш-кода уменьшает коллизии хэшей? Может ли хэш-функция напрямую использовать хэш-код ключа?

7: Сколько способов разрешить хеш-конфликт?

8: Зачем использовать оператор XOR?

9.: Как определить емкость таблицы HashMap?

10: Пожалуйста, объясните параметр loadFactor HashMap, какова его функция

11: Расскажите о процессе метода put в HashMap

12: Когда длина связанного списка >= 8, почему связанный список должен быть преобразован в красно-черное дерево?

13: новый HashMap(18); Какова начальная емкость HashMap в настоящее время?

14: Расскажите о процессе изменения размера

15: Как реализовать get in hashMap?

16: Почему бы не использовать бинарное дерево поиска вместо красно-черного дерева вместо глубоко связанного списка, вызванного методом застежки-молнии? Почему бы просто не использовать красно-черные деревья все время?

17: Расскажите нам, что вы знаете о красно-черных деревьях

18: Какие изменения были внесены в HashMap в JDK8?

19: Ключ в HashMap Можем ли мы использовать любой класс в качестве ключа?

20: Почему длина HashMap 2 указана в N-й степени?

21: В чем разница между HashMap, LinkedHashMap, TreeMap?

22: Что такое безотказность?

23: В чем разница между HashMap и HashTable?

24: Является ли HashMap потокобезопасным?

25: Как обойти небезопасность потока HashMap?

26: В чем разница между HashMap и ConcurrentHashMap?

27: Почему ConcurrentHashMap более эффективен, чем HashTable?

28: Расскажите о механизме блокировки в ConcurrentHashMap.

29: Почему в JDK 1.8 ConcurrentHashMap использует встроенную синхронизированную блокировку вместо реентерабельной блокировки ReentrantLock?

30: Можете ли вы дать краткое введение в ConcurrentHashMap?

31: Вы знакомы с параллелизмом ConcurrentHashMap?

....

Сводка знаний о коллекции Java

(Если вам нужна карта разума, добавьте меня в WeChat tj20120622, бесплатный подарок)

Теперь мы официально запускаем серийную пушку

1. Какова основная структура данных HashMap?

Нижний слой HashMap реализуется хэш-массивом и односвязным списком.После jdk8 принимается структура данных массив + связанный список + красно-черное дерево.

2. Расскажите о принципе работы HashMap

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

Нижний слой HashMap реализуется хэш-массивом и односвязным списком.После JDK8 принята структура данных массив + связанный список + красно-черное дерево.

Мы храним и получаем объекты через put и get. Когда мы передаем ключ и значение методу put(), мы сначала выполняем вычисление hashCode() для ключа, чтобы получить его позицию в массиве сегментов для хранения объекта Entry. Когда объект получен, местоположение ведра получается с помощью get, а правильная пара ключ-значение находится с помощью метода equals() ключевого объекта, а затем возвращается объект-значение.

3. Что делать при использовании HashMap, если хэш-код двух объектов одинаков?

Поскольку HashCode один и тот же, он не обязательно равен (метод equals сравнивает), поэтому индексы массивов, в которых расположены два объекта, совпадают, и происходит «столкновение». А поскольку HashMap использует связанный список для хранения объектов, этот узел будет храниться в связанном списке.

4. Как устроена хэш-функция HashMap?

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

Обязательно максимально уменьшите коллизии хэшей, чем более децентрализовано, тем лучше;
Алгоритм должен быть максимально эффективным, потому что это высокочастотная операция, поэтому используются битовые операции;

5. Сколько способов обойти HashMap?

Итератор итератор
Самый распространенный способ его использования, вы можете получить ключ и значение одновременно.
Использовать метод foreach (только JDK1.8)
Перебрать набор ключей

6. Почему XOR старших 16 бит и младших 16 бит хэш-кода уменьшает коллизии хэшей?

Потому что функция key.hashCode() вызывает хеш-функцию, которая поставляется с типом значения ключа и возвращает хэш-значение типа int. Диапазон значений int составляет **-2147483648~2147483647**, что в сумме составляет около 4 миллиардов пробелов отображения. До тех пор, пока хэш-функция отображается равномерно и нечетко, для обычных приложений трудно столкнуться. Но проблема в том, что массив длиной 4 миллиарда не помещается в память.

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

7. Сколько способов разрешения хеш-конфликтов?

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

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

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

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

4.Метод связанного адреса:Сохраните хеш-значение, вызывающее конфликт хэшей, в позиции индекса в виде связанного списка. HashMap использует этот метод. Преимущество в том, что нет необходимости открывать новое пространство, данные не будут потеряны, а адресация относительно проста. Но по мере того, как хэш-цепочка становится все длиннее и длиннее, адресация также требует больше времени. Хороший алгоритм хеширования должен поддерживать как можно более короткую цепочку, предпочтительно только одно значение индекса. То есть сделать так, чтобы распределение хеш-адресов было как можно более равномерным, и в то же время расчет был простым.

8. Зачем использовать оператор XOR?

Гарантируется, что при изменении одного бита 32-битного значения hashCode объекта будет изменяться все возвращаемое значение hash(). Максимально сведите к минимуму столкновения.

9. Как определить емкость таблицы HashMap?

1. Размер табличного массива определяется параметром емкости.Значение по умолчанию 16. Его также можно передать при построении.Максимальное ограничение 1

②, loadFactor — это коэффициент загрузки, основная цель которого — подтвердить необходимость динамического расширения массива таблиц, значение по умолчанию — 0,75, например, когда размер массива таблиц равен 16, а коэффициент загрузки — 0,75, порог равен 12, когда фактический размер таблицы превышает 12, таблицу необходимо динамически расширять;

3. При расширении вызовите метод resize(), чтобы удвоить длину таблицы (обратите внимание, что это длина таблицы, а не порог);

④ Если объем данных велик, расширение приведет к потере производительности.В местах с высокими требованиями к производительности эта потеря может быть фатальной.

10. Пожалуйста, объясните параметр loadFactor HashMap, какова его функция

loadFactor представляет степень скученности HashMap, которая влияет на вероятность операций хеширования в одной и той же позиции массива.

Значение loadFactor по умолчанию равно 0,75. Когда элементы, содержащиеся в HashMap, достигают 75% длины массива HashMap, это означает, что HashMap слишком переполнен и нуждается в расширении. LoadFactor можно настроить в конструкторе HashMap. .

11. Расскажите о процессе метода put в HashMap

Из-за различий в дизайне HashMap в версиях JDK, вот различия между JDK7 и JDK8:

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

12. Если длина связанного списка >= 8, почему связанный список должен быть преобразован в красно-черное дерево?

Поскольку средняя длина поиска красно-черного дерева равна log(n), при длине 8 средняя длина поиска равна 3. Если вы продолжите использовать связанный список, средняя длина поиска будет 8/2=4, поэтому, когда длина связанного списка >= 8 , необходимо преобразовать связанный список в красно-черное дерево.

13. новый HashMap(18): Какова начальная емкость HashMap в настоящее время?

Вместимость 32.

В HashMap есть статический метод tableSizeFor, который гарантирует, что возвращаемое значение функции больше или равно значению минимальной степени 2 заданного параметра initialCapacity.

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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

14. Расскажите о процессе увеличения размера

Создайте новый массив с удвоенной емкостью старого массива и пересчитайте места хранения узлов в старом массиве. В новом массиве есть только две позиции узла: исходная позиция нижнего индекса или исходный нижний индекс + размер старого массива.

15. Как реализовать get in hashMap?

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

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

Причина, по которой выбрано красно-черное дерево, заключается в том, чтобы устранить дефекты двоичного дерева поиска.Двоичное дерево поиска в особых случаях станет линейной структурой (это то же самое, что исходное использование структуры связанного списка, вызывающее глубокие проблемы), поиск будет очень медленным. После вставки новых данных красно-черное дерево, возможно, потребуется сделать левым, правым и обесцветить для сохранения баланса.Красно-черное дерево вводится для быстрого поиска данных и решения проблемы глубины запроса связанного список. Мы знаем, что красно-черное дерево принадлежит сбалансированному бинарному дереву. Тем не менее, есть цена, которую нужно заплатить, чтобы сохранить «баланс», но потребление ресурсов при этой стоимости меньше, чем при обходе линейного связанного дерева. списка, поэтому при длине больше 8 будет использоваться красно-черное дерево.Если длина связного списка очень мала, то его не будет вообще.Красно-черное дерево нужно вводить, но введение будет медленным.

17. Расскажите о своем понимании красно-черных деревьев

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска и эффективное дерево поиска.

Красно-черное дерево достигает самобалансировки за счет следующих определений свойств:

Узлы красные или черные.
Корни черные.
Все листья черные (листья — узлы NIL).
У каждого красного узла должно быть два черных потомка. (Не может быть двух последовательных красных узлов на всех путях от каждого листа к корню.)
Все простые пути от любого узла к каждому его листу содержат одинаковое количество черных узлов (для краткости черных высот).

18. Какие изменения были внесены в HashMap в JDK8?

1. В java 1.8, если длина связанного списка превышает 8, связанный список будет преобразован в красно-черное дерево. (Количество ведер должно быть больше 64, когда меньше 64, оно будет только увеличиваться)

2. При возникновении коллизии хэшей java 1.7 будет вставляться в начало связанного списка, а java 1.8 — в конец связанного списка.

3. В java 1.8 Entry заменили на Node (с жилеткой).

19. Ключ в HashMap. Можем ли мы использовать любой класс в качестве ключа?

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

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

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

20. Почему длина HashMap 2 указана в N-й степени?

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

В операции остатка (%), если делитель является степенью числа 2, она эквивалентна операции и (&) вычитания единицы из делителя (то есть хэш % длина == хэш &(длина - 1) предпосылка состоит в том, что длина равна 2 в n-й степени). А использование двоичной битовой операции & может повысить эффективность работы по сравнению с %.

Вот почему длина HashMap должна быть равна 2 в степени N.

21. В чем разница между HashMap, LinkedHashMap и TreeMap?

LinkedHashMap унаследован от HashMap и реализован на основе HashMap и двусвязного списка.
HashMap неупорядоченный; LinkedHashMap упорядоченный, который можно разделить на порядок вставки и порядок доступа. Если это порядок доступа, то при работе с существующей записью запись будет перемещена в конец двусвязного списка (фактически она сначала удаляется, а затем вставляется).
LinkedHashMap обращается к данным так же, как Entry[], используемый в HashMap.Двунаправленный список служит только для обеспечения порядка.
LinkedHashMap небезопасен для потоков.

22. Что такое отказоустойчивость?

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

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

Решение

Рекомендуется использовать «классы из пакета java.util.concurrent» вместо «классы из пакета java.util». Это можно понять так: перед обходом запишите modCount expectModCount, а потом сравните expectModCount с modCount, если он не равен, то доказывает, что он был параллельным и был модифицирован, поэтому выбрасывается ConcurrentModificationException.

23. В чем разница между HashMap и HashTable?

①, HashMap является потокобезопасным, HashTable является потокобезопасным;

2. Из-за безопасности потоков HashTable не так эффективен, как HashMap;

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

④ Размер инициализированного массива HashMap по умолчанию равен 16, а размер HashTable — 11. При расширении первого он удваивается, а второй удваивается +1;

⑤, HashMap необходимо пересчитать хеш-значение, а HashTable напрямую использует хэш-код объекта;

24. Является ли HashMap потокобезопасным?

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

25. Как избежать небезопасности потоков HashMap?

В однопоточных условиях, чтобы избежать ConcurrentModificationException, необходимо убедиться, что для модификации данных используется только сама HashMap или только Iterator, а метод самой HashMap не может использоваться для модификации данных перед Iterator используется. Потому что, когда данные удаляются через Iterator, modCount HashMap и ожидаемый ModCount Iterator автоматически увеличиваются, что не влияет на их равенство. Если нужно добавить данные, это можно сделать только с помощью самого метода HashMap. В настоящее время, если вы хотите продолжить просмотр данных, вам нужно снова вызвать метод iterator(), чтобы восстановить новый итератор, поэтому что ожидаемое значение ModCount нового Iterator совпадает с значением modCount обновленного HashMap.

В многопоточных условиях можно использовать два метода:

Метод Collections.synchronizedMap создает синхронизированную карту.
Используйте потокобезопасный ConcurrentHashMap напрямую.

26. В чем разница между HashMap и ConcurrentHashMap?

Все данные хранятся в виде ключ-значение;
HashMap является потокобезопасным, ConcurrentHashMap является потокобезопасным в JUC;
Базовая структура данных HashMap представляет собой массив + связанный список (до JDK 1.8). После JDK 1.8 это массив + связанный список + красное черное дерево. Когда количество элементов в связанном списке достигает 8, скорость запроса связанного списка не такая высокая, как у красно-черного дерева, связанный список будет преобразован в красно-черное дерево, а скорость запроса красно-черное дерево быстрее;
Начальный размер массива HashMap равен 16 (по умолчанию), когда происходит расширение, он будет увеличен на 0,75 * размер массива;
До JDK 1.8 ConcurrentHashMap использовал блокировку сегмента для реализации Segment + HashEntry Размер массива Segment по умолчанию равен 16, 2 в n-й степени, после JDK 1.8 для обеспечения безопасности параллелизма используется Node + CAS + Synchronized.

27. Почему ConcurrentHashMap эффективнее HashTable?

HashTable: используйте блокировку (блокировку всей структуры связанного списка) для решения проблем параллелизма Несколько потоков конкурируют за блокировку, которую легко заблокировать;

ConcurrentHashMap:

Блокировки сегментации используются в JDK 1.7 (ReentrantLock + Segment + HashEntry), что эквивалентно разделению HashMap на несколько сегментов и назначению блокировки каждому сегменту, что поддерживает многопоточный доступ. Детализация блокировки: на основе сегмента, включая несколько HashEntry.
Используется в JDK 1.8CAS + synchronized + Node + 红黑树. Степень детализации блокировки: узел (первый узел) (реализующий Map.Entry). Детализация блокировки снижена.

28. Расскажите о механизме блокировки в ConcurrentHashMap

В JDK 1.7 механизм блокировки сегментов используется для реализации параллельных операций обновления.Нижний уровень использует структуру хранения массив + связанный список, включая два основных статических внутренних класса Segment и HashEntry.

① Сегмент наследует ReentrantLock (блокировка повторного входа), чтобы действовать как блокировка, и каждый объект сегмента защищает несколько сегментов каждой таблицы сопоставления хэшей;

②, HashEntry используется для инкапсуляции пары ключ-значение таблицы сопоставления;

3. Каждое ведро представляет собой связанный список, связанный несколькими объектами HashEntry.

В JDK 1.8 используется Node + CAS + Synchronized для обеспечения безопасности параллелизма. Отмените класс Segment и напрямую используйте массив таблиц для хранения пар ключ-значение; когда длина связанного списка, состоящего из объектов HashEntry, превышает TREEIFY_THRESHOLD, связанный список преобразуется в красно-черное дерево для повышения производительности. Нижний слой изменен на массив + связанный список + красно-черное дерево.

29. Почему в JDK 1.8 ConcurrentHashMap использует встроенную синхронизированную блокировку вместо реентерабельной блокировки ReentrantLock?

①, размер частиц уменьшается;

② Команда разработчиков JVM не отказалась от синхронизации, и пространство оптимизации синхронизации на основе JVM больше и естественнее.

3. При большом количестве операций с данными ReentrantLock на основе API будет потреблять больше памяти из-за нехватки памяти JVM.

30. Можете ли вы кратко рассказать о ConcurrentHashMap?

①, важные константы:

частный переходный volatile int sizeCtl;

При отрицательном значении -1 означает инициализацию, -N означает расширение N-1 потоков;

Когда он равен 0, это означает, что таблица не была инициализирована;

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

②, структура данных:

Узел является базовой единицей структуры хранилища, наследует Entry в HashMap и используется для хранения данных;

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

TreeBin — это контейнер, который инкапсулирует TreeNode, предоставляя некоторые условия и управление блокировкой для преобразования красно-черных деревьев.

3. При хранении объектов (метод put()):

Если не инициализирован, вызовите метод initTable() для инициализации;
Если нет конфликта хэшей, прямая вставка без блокировки CAS;
Если вам нужно расшириться, сделайте это в первую очередь;
При конфликте хэшей добавляются блокировки для обеспечения потокобезопасности, есть два случая: первый — связанный список, который просматривается до конца и вставляется напрямую, другой — красно-черное дерево, которое вставляется согласно красно-черная структура дерева;
Если номер связанного списка больше порогового значения 8, он должен быть преобразован в красно-черную древовидную структуру, и break снова входит в цикл.
Если добавление выполнено успешно, вызовите метод addCount(), чтобы подсчитать размер и проверить, требуется ли расширение.

④.Передача метода расширения емкости(): емкость по умолчанию равна 16. При расширении емкости емкость становится вдвое больше исходной емкости. helpTransfer(): вызовите несколько рабочих потоков, чтобы увеличить емкость, что будет более эффективно.

⑤ При получении объекта (метод get()):

Вычислите хеш-значение, найдите позицию индекса таблицы и верните значение, если первый узел совпадает;
Если он сталкивается с расширением, он вызывает метод ForwardingNode.find(), чтобы пометить узел, который расширяется, найти узел и вернуться, если он соответствует;
Если ничего из вышеперечисленного не соответствует, пройдите по узлу вниз и вернитесь, если он совпадает, в противном случае верните null в конце.

31. Знакомы ли вы с параллелизмом ConcurrentHashMap?

Максимальное количество потоков, которые могут одновременно обновлять ConccurentHashMap во время работы программы без конфликта блокировок. По умолчанию 16 и может быть установлено в конструкторе. Когда пользователь устанавливает степень параллелизма, ConcurrentHashMap будет использовать минимальную степень степени 2, большую или равную этому значению, в качестве фактической степени параллелизма (если пользователь устанавливает степень параллелизма на 17, фактическая степень параллелизма составляет 32). ).

Ссылаться на:ii081.cn/gFInl

Суммировать

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

Так называемый гений просто превращает усилия других, пьющих кофе, в работу.

—— Лу Синь

Рекомендуемое чтение

25 последовательных пушек MySQL

12 последовательных пушек пула потоков

12 основ параллельного программирования

18 цепных пушек JVM

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

Жду ваших пересылок, лайков, просмотров, спасибо

В этой статье используетсяПомощник по синхронизации статейСинхронизировать