Серия "Войдём на большой завод вместе"-HashMap

Чем больше вы знаете, тем больше вы не знаете

Ставьте лайки и смотрите снова, формируйте привычку

эта статьяGitHub github.com/JavaFamilyЭто было включено в вышеперечисленное, есть интеллект-карты точек интервью фабрик первого уровня, а также было организовано много моих документов. Добро пожаловать в Звезду и совершенство. Вы можете обратиться в тестовый центр для ознакомления во время интервью Я надеюсь, что у нас есть что-то вместе.

текст

Грациозная дама в рубашке, держащая изящный блокнот, подошла прямо ко мне и села передо мной.

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

Но кажется, что такой молодой не должен быть в состоянии задать какую-либо глубину, хи-хи. (О? Правда 😏)

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

Здравствуйте, красивый и очаровательный интервьюер, вы смеетесь, это зависит от чтения серии Ао Бина «Повешение и избиение интервьюера», иначе я действительно не могу ответить на многие белые пятна оригинальных знаний, у него действительно что-то есть.

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

Что ж, Xiaoshuaibi, хотя предыдущий стек технологий не имеет особых недостатков, но в будущем я научу вас, как быть человеком с основами, вы должны быть готовы!

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

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

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

Таким образом, в каждом месте массива хранятся экземпляры Key-Value, которые называются Entry в Java7 и Node в Java8.

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

Например, если я поставил («Шуай С», 520), я вставил элемент «Шуай С». В это время мы вычислим позицию вставки с помощью хеш-функции. Вычисленный индекс равен 2, а результат будет следующим следует.

хеш ("Шуай С") = 2

Вы упомянули, что есть еще связанный список, зачем вам связанный список и как выглядит связанный список?

Мы все знаем, что длина массива ограничена.В ограниченной длине мы используем хэш, а сам хеш имеет вероятность, то есть «Шуай Бинг» и «Цин Шуай», у нас обоих есть определенная вероятность хэш, как в приведенном выше случае, я снова хеширую «Bing Shuai», а в крайних случаях он также будет хэшироваться до значения, которое образует связанный список.

Каждая нода сохранит свой хэш, ключ, значение и следующую ноду Я смотрю исходный код Node.

Говоря о связанном списке, я хотел бы спросить, знаете ли вы, как вставляется новый узел Entry, когда он вставляется в связанный список?

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

но,После java8 вставляются все используемые хвосты.

Зачем переходить на хвостовую вставку?

Этот! ! ! Этот вопрос, интервьюер действительно спросит! ! ! К счастью, я читал сборники стихов, иначе я умру!

Некоторые думают, что автор делает это наугад, и это не полезно для луана, но это не так, в этом скрыта тайна

Во-первых, давайте посмотрим на механизм расширения HashMap:

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

Когда изменить размер?

Есть два фактора:

• Емкость: Текущая длина HashMap.
• LoadFactor: коэффициент нагрузки, значение по умолчанию 0,75f.

  

Как вы это понимаете?Например текущая ёмкость 100.При сохранении 76-ой вы решаете что нужно изменить размер,потом расширить ёмкость.Однако расширение HashMap не так просто, как просто расширение ёмкости .

Расширение? Как это масштабируется?

в два шага

• Расширение: создайте новый пустой массив Entry, длина которого в два раза превышает размер исходного массива.
• ReHash: пройтись по исходному массиву Entry и повторно хэшировать все Entry в новый массив.

Зачем вам нужно перехешировать его, разве не хорошо копировать прошлое напрямую?

К черту этот вопрос! Немного слепого пятна знаний!

1x1 получает 1 1x2 получает 2... Теперь я вспоминаю, что сказал мне Ао Бин в ту ночь: Если бы я не чувствовал себя хуже, когда был молод, и знал, что дорого, мне было бы стыдно, что я не дал тебе эти сладкие мечты... какого черта!

Мисс: Это потому, что правила Hash также меняются после увеличения длины.

Формула хеша ---> index = HashCode(Key) & (Length - 1)

Исходная длина (длина) равна 8, а значение, полученное вашей битовой операцией, равно 2. Новая длина равна 16, и значение, полученное вашей битовой операцией, очевидно, отличается.

До расширения:

После расширения:

После разговора о механизме расширения, давайте перейдем к делу: почему раньше вы использовали метод вставки головы, а после java8 изменили его на вставку хвоста?

Черт, я думал, она забыла! Еще спрашивают!

Позвольте мне сначала привести пример.Сейчас мы помещаем два значения в емкость 2, а коэффициент загрузки составляет 0,75.Изменится ли размер, когда мы поставим второе?

2 * 0,75 = 1, поэтому для вставки второго требуется изменить размер

Теперь мы хотим оказаться внутри контейнера вместимостью 2с разными нитямиInsert A, B, C, если мы делаем короткую точку перед изменением размера, это означает, что данные вставлены, но может быть так, прежде чем расширение не будет изменено.

Мы видим, что связанный список указывает на A->B->C

Совет: следующий указатель A должен указывать на B

Из-за метода назначения изменения размера, то есть с использованиемМетод вставки заголовка односвязного списка, новый элемент в той же позиции всегда будет помещаться в позицию заголовка связанного списка., элементы одной и той же цепочки Entry в старом массиве могут быть помещены в разные позиции в новом массиве после пересчета позиции индекса.

Могут возникнуть следующие ситуации: Вы нашли проблему?

Следующий указатель B указывает на A

После настройки нескольких тем может появиться круговой связанный список.

Если значение будет взято в это время, появится трагедия - Infinite Loop.

О дерьмо, парень не может победить его!

У парня что-то есть, а вы все говорили, что головка JDK1.7, а хвост 1.8 вроде?

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

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

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

То есть изначально это был A->B, а после расширения связанный список по-прежнему A->B.

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

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

Означает ли это, что Java8 может использовать HashMap в многопоточности?

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

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

Собеседник отстой, если бы не тыкрасивый как божествоИнтервьюер брал у меня интервью, я, наверное, не помню.

Я*, вы поставили почти?

Младшая сестра поджала губы и улыбнулась, мальчик, у тебя есть предложение, и Иисус не может забрать тебя, я сказал!

Затем я спрашиваю вас, какова длина инициализации HashMap по умолчанию?

Я помню, что начальный размер был 16, когда я смотрел исходный код

Знаешь почему 16?

Ложь*, в чем проблема? Почему ему 16, откуда я знаю? ? ? Ты уверен, что не шутишь?

Я изо всех сил старался вспомнить исходный код. Не знаю, пропустил ли я какие-то детали. В голове пронеслись сцены допоздна в школе и просмотра исходного кода. Я вспомнил ту ночь на детской площадке,Маленький Грин, который был со мной полмесяцаОн взял меня за руку и сказал: «Ты станешь отцом».

Подождите, что это за черт, о, о, о, вспомнил! ! !

В строке 236 JDK1.8 1, Зачем использовать побитовые операции? Плохо ли писать 16 напрямую?

Я снова погрузился в глубокие размышления, сумасшедший мозговой штурм, динь!

Понятно!

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

Это сделано для удобства работы с битами,Операции с битовым И намного эффективнее, чем арифметические вычисления., причиной выбора 16 является обслуживание алгоритма, который сопоставляет ключ с индексом.

Я говорил ранее, что мы получим его хеш для всех ключей, но как нам получить хеш, который будет максимально равномерно распределен?

Да, мы выполняем побитовые операции через значение HashCode ключа.

Например, если ключ "Shuai C", десятичное число равно 766132, то двоичное число равно 10111011000010110100.

Давайте посмотрим на формулу расчета индекса: index = HashCode (Key) & (Length-1)

Двоичное число 15 равно 1111, тогда 10111011000010110100 и 1111 равно 4 в десятичной системе.

Причина использования операции побитового И та же, что и при использовании по модулю, и производительность также значительно улучшена!

Так зачем использовать 16 и ничего больше?

Потому что при использовании числа, являющегося степенью 2, значение Length-1 состоит в том, что все двоичные биты равны 1. В этом случае результат index эквивалентен значению последних нескольких битов HashCode.

Пока сам входной HashCode равномерно распределен, результат алгоритма Hash является однородным.

это длядобиться равномерного распределения.

Эй, малыш, я много знаю, поэтому позвольте задать вам вопрос: зачем нам переписывать метод hashCode, когда мы переписываем метод equals?

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

Это можно спросить у него.К счастью, я смотрел сериал Ао Бина, а то уж точно конец! ! !

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

Я помню интервьюера!

Потому что в java все объекты наследуются от класса Object. В классе Ojbect есть два метода equals и hashCode, оба из которых используются для сравнения того, равны ли два объекта.

Не переопределяя метод equals, мы наследуем метод equals объекта,где equals сравнивает адреса памяти двух объектов, очевидно, адреса памяти двух новых объектов должны быть разными

• Для объектов-значений == сравнивает значения двух объектов
• Для эталонных объектов сравниваются адреса двух объектов.

Вы еще помните, что я сказал, что HashMap ищет индекс через hashCode ключа, затем индекс формирует связанный список, то есть индекс «Шуай Бинг» и «Бинг Шуай» может быть равен 2, что находятся в связанном списке.

Когда мы идем получать, он просто идет в хеш по ключу и потом вычисляет индекс, и находит 2, тогда как мне найти конкретное "Чунай" или "Чунай"?

equals! Да, поэтому, если мы перепишем метод equals, рекомендуется переписать метод hashCode, чтобы один и тот же объект возвращал одно и то же хеш-значение, а разные объекты возвращали разные хеш-значения.

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

Все в порядке, мальчик, я помню, вы сказали выше, что он небезопасен для потоков, так что можете ли вы рассказать мне, как вы справляетесь с безопасным для потоков сценарием HashMap?

Интервьюер, в таком случае мы обычно используемHashTableилиConcurrentHashMap, а потому что бывшаяпараллелизмПричина в том, что в основном нет сценариев использования, поэтому мы все используем ConcurrentHashMap в сценариях, небезопасных для потоков.

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

Итак, вы можете поговорить со мной о ConcurrentHashMap?

Хорошо, но сегодня уже поздно, я думаю, мы должны назначить встречу в другой день?

Кроме того, Ао Бин, кажется, в последнее время занят Двойной Двенадцатью, как он может драться так много одновременно?

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

Суммировать

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

Из соображений экономии места и энергии я представил некоторые из основных моментов знаний. Я обобщил некоторые распространенные вопросы интервью о HashMap. Вы можете спросить себя, можете ли вы на них ответить. Если вы не можете, проверьте это.

Общие вопросы интервью HashMap:

• Базовая структура данных HashMap?

• Принцип доступа к HashMap?

• Разница между Java7 и Java8?

• Почему поток небезопасен?

• Есть ли вместо этого какой-либо потокобезопасный класс?

• Каков размер инициализации по умолчанию? Почему их так много? Почему размеры всегда равны степени 2?

• Как расширить HashMap? Что такое коэффициент нагрузки? Почему так много?

• Каковы основные параметры HashMap?

• Как HashMap обрабатывает коллизии хэшей?

• Правила расчета хеша?