HashMap интервью должно задать 6 баллов, сколько вы знаете?

1. Принцип реализации HashMap?

Этот вопрос можно задать в следующей серии пушек

• Вы читали исходный код HashMap, знаете принцип?
• Зачем использовать массив + связанный список?
• Какие еще решения вы знаете о хэш-конфликтах?
• Могу ли я использовать LinkedList вместо структуры массива?
• Если это возможно, то почему HashMap использует массив вместо LinkedList?

1. Вы видели исходный код HashMap, знаете принцип?

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

HashMap использует массив Entry для хранения пар "ключ-значение". Каждая пара "ключ-значение" представляет собой объект Entry. Класс Entry на самом деле является структурой одностороннего связанного списка. Он имеет указатель Next и может подключаться к следующему объекту Entry.

Только в JDK1.8, когда длина связанного списка больше 8, связанный список будет преобразован в красно-черное дерево!

2. Зачем использовать массив + связанный список?

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

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

3. Какие еще решения вы знаете о хэш-конфликтах?

Существует четыре наиболее известных из них: (1) метод открытой адресации (2) метод цепной адресации (3) метод повторного хэширования (4) метод общедоступной области переполнения.

ps: Если вы заинтересованы в расширении, вы можете понять это, выполнив поиск самостоятельно, это не будет расширено!

4. Могу ли я использовать LinkedList вместо структуры массива?

Здесь я немного поясню, смысл этого вопроса в том, что исходный код такой

Entry[] table = new Entry[capacity];

ps: Entry является узлом связанного списка.

Тогда я выражаю это так

List<Entry> table = new LinkedList<Entry>();  

Возможно ли это?

Ответ очевиден, это должно быть возможно.

5. Если это возможно, то почему HashMap использует массив вместо LinkedList?

Потому что использование массивов является наиболее эффективным!

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

(Когда брат Ян писал это, он не мог отделаться от ощущения, что у него действительно есть идея, и он задал себе вопрос до смерти. К счастью, я придумал ответ.)

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

Механизм расширения ArrayList расширяется в 1,5 раза, поэтому в этой статье не объясняется, почему ArrayList расширяется в 1,5 раза.

2. При каких условиях HashMap расширяется?

Этот вопрос можно задать в следующей серии пушек

• В каких условиях расширяется Hashmap?
• Почему масштабируется до N-й силы 2?
• Почему вам нужно сначала выполнить XOR над старшими 16 битами, а затем выполнить операцию по модулю?

1. При каких условиях HashMap расширяется?

Если ковш заполнен (превышает коэффициент загрузки * текущая вместимость), требуется изменение размера.

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

текущая емкость - это текущий размер массива.

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

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

Однако известно, что эта операция не такая быстрая, как операция сдвига.

Поэтому оптимизированный хэш&(длина-1) выполняется в исходном коде.

Это hash%length==hash&(length-1)

Тогда почему 2 в энной степени?

Потому что энная степень числа 2 на самом деле на n нулей меньше 1, а энная степень числа 2 -1 на самом деле равна n единицам.

Например, длина равна 8, 3 и (8-1) = 3 2 и (8-1) = 2, в разных положениях, коллизии нет.

5 и промежуток времени и 3 (5-1) = 0 2 (5-1) = 0, 0 во всем, возникает столкновение.

Поэтому гарантия того, что объем равен n-й степени 2, состоит в том, чтобы при выполнении (length-1) каждый бит мог быть &1, то есть и 1111...1111111.

3. Почему вам нужно сначала выполнить XOR над старшими 16 битами, а затем выполнить операцию по модулю?

Позвольте мне сначала показать вам метод хеширования в jdk1.8. 1.7 сложнее, поэтому читать не будем.

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

Например, когда наша длина равна 16, хеш-код (хэш-код, соответствующий ключу строки «abcabcabcabcabc») соединяется с (16-1) и операцией. Для хэш-кода, сгенерированного несколькими ключами, пока хэш-код Последние 4 бита кода равны 0, независимо от того, как меняются старшие биты, окончательный результат равен 0.

Как показано ниже

И после добавления «функции возмущения» старшего 16-битного эксклюзива или младшего 16-битного результат выглядит следующим образом.

Видно: До оптимизации функции возмущения: 1954974080 % 16 = 1954974080 & (16 - 1) = 0 После оптимизации функции возмущения: 1955003654 % 16 = 1955003654 & (16 - 1) = 6 Очевидно, вероятность столкновения уменьшается.

3. Расскажите о процессе получения/установки hashmap?

Этот вопрос можно задать в следующей серии пушек

• Вы знаете, на что похож процесс помещения элементов в hashmap?
• Вы знаете, на что похож процесс получения элементов в hashmap?
• Какие еще алгоритмы хэширования вы знаете?
• Поговорим о реализации Hashcode в строке? (Есть много больших растений в этом вопросе)

1. Вы знаете, на что похож процесс помещения элементов в hashmap?

Выполните хеш-операцию с hashCode() ключа и рассчитайте индекс;

Если столкновения нет, положите его прямо в ведро;

Если есть коллизия, после того, как ведра существуют в виде связанного списка;

Если конфликт приводит к тому, что связанный список становится слишком длинным (больше или равен TREEIFY_THRESHOLD), преобразуйте связанный список в красно-черное дерево (изменения в JDK1.8);

Если узел уже существует, заменить старое значение (гарантировать уникальность ключа)

Если ковш заполнен (превышает коэффициент загрузки * текущая вместимость), требуется изменение размера.

2. Знаете ли вы, на что похож процесс получения элементов в hashmap?

Выполните хеш-операцию с hashCode() ключа и рассчитайте индекс;

Если первый узел в ведре попал напрямую, он вернется напрямую;

Если есть конфликт, найдите соответствующую запись с помощью key.equals(k);

• Если это дерево, оно ищется по ключу.equals(k) в дереве, O(logn);
• Если это связанный список, он ищется в связанном списке с помощью key.equals(k), O(n).

3. Какие еще алгоритмы хэширования вы знаете?

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

Наиболее известные из них — MurmurHash, MD4, MD5 и т. д.

4. Говорите о реализации хеш-кода в String? (Частота этого вопроса очень высока)

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

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

Формула расчета хэша может быть рассчитана какs[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

Так почему же 31 — простое число?

Основная причина в том, что 31 — нечетное простое число, поэтому 31*i=32*i-i=(i

4. Почему хеш-карта меняется на красно-черное дерево, когда количество элементов связанного списка превышает 8?

Этот вопрос можно задать в следующей серии пушек

• Знаете ли вы, что изменилось в hashmap в jdk1.8?
• Почему бы напрямую не использовать красно-черное дерево при разрешении хеш-конфликтов, а вместо этого выбрать сначала использовать связанный список, а затем переключиться на красно-черное дерево?
• Мне не нужно красно-черное дерево, можно ли использовать бинарное дерево поиска?
• Так почему порог 8?
• Когда связанный список преобразуется в красно-черное дерево, когда он вырождается в связанный список?

1. Знаете ли вы, что изменилось в hashmap в jdk1.8?

• Зависит отмассив + связанный списокСтруктура изменена наМассив + связанный список + красное черное дерево.
• Оптимизированный хэш-алгоритм для операций высокого порядка: h^(h>>>16)
• После расширения элемент либо находится в исходной позиции, либо перемещается в степени 2 на позицию в исходной позиции, а порядок связанного списка остается неизменным.

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

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

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

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

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

3. Красно-черное дерево мне не нужно, можно ли использовать бинарное дерево поиска?

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

4. Почему порог 8?

Не знаю, дождитесь ответа автора jdk.

Ответы на этот вопрос, которые можно найти в Интернете, — полная ерунда.

Я только что опубликовал ответ от Niuke.com, как показано на рисунке ниже.

Видите ошибку? Пересечение 6,64? Перекресток явно 4, хорошо?

log4=2, 4/2=2.

Автор jdk выбрал 8, что, должно быть, подверглось строгим вычислениям.Он посчитал, что при длине 8 вместо обеспечения стоимости поиска структуры связанного списка лучше преобразовать его в красно-черное дерево и сохранить его вместо этого балансовая стоимость.

5. Когда связанный список преобразуется в красно-черное дерево, когда он вырождается в связанный список?

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

5. Проблемы параллелизма HashMap?

Этот вопрос можно задать в следующей серии пушек

• Что не так с HashMap в среде параллельного программирования?
• Есть ли еще эти проблемы в jdk1.8?
• Как вы вообще решаете эти проблемы?

• (1) Многопоточное расширение, вызывающее проблемы с бесконечным циклом
• (2) Многопоточная установка может привести к потере элементов
• (3) После помещения ненулевого элемента get становится нулевым

В jdk1.8 проблема бесконечного цикла была решена. Две другие проблемы все еще существуют.

Такие как ConcurrentHashmap, Hashtable и другие потокобезопасные классы коллекций.

6. Что вы обычно используете в качестве ключа HashMap?

Этот вопрос можно задать в следующей серии пушек

• Может ли здоровье быть нулевым?
• Что вы обычно используете в качестве ключа HashMap?
• Что не так с использованием изменяемого класса в качестве ключа HashMap?
• Как реализовать собственный класс в качестве ключа HashMap?

1. Может ли здоровье быть нулевым?

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

2. Что вы обычно используете в качестве ключа HashMap?

Как правило, неизменяемые классы, такие как Integer и String, используются в качестве ключей HashMap, и чаще всего используется String.

• (1) Поскольку строка является неизменной, хэш-код кэшируется при создании и не требует пересчета. Это делает строки очень подходящими в качестве ключей в Картах, а строки обрабатываются быстрее, чем другие ключевые объекты. Вот почему ключи в HashMap обычно используют строки.
• (2) Поскольку методы equals() и hashCode() используются при получении объектов, очень важно, чтобы ключевой объект правильно переопределял эти два метода.Эти классы уже стандартизированно переопределяют hashCode() и equals.( ) метод.

3. Что плохого в использовании изменяемого класса в качестве ключа HashMap?

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

HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode发生了改变
System.out.println(changeMap.get(list));

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

java.lang.Object@74a14482
null

4. Как реализовать собственный класс в качестве ключа HashMap?

Этот вопрос исследует две точки знаний

• На что следует обратить внимание при переписывании методов hashcode и equals?
• Как спроектировать неизменяемый класс

Что касается вопроса 1, запомните следующие четыре принципа.

(1) Два объекта равны, хэш-код должен быть равен

(2) Два объекта не равны, и хэш-код не обязательно равен

(3) Хэш-код равен, и два объекта не обязательно равны

(4) Хэш-код не равен, два объекта должны быть разными

Для вопроса два, помните, как написать неизменяемый класс

(1) Модификатор final добавляется к классу, чтобы гарантировать, что класс не унаследован.

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

(2) Убедитесь, что все переменные-члены должны быть закрытыми, и добавьте окончательное изменение

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

(3) Не предоставляет методы для изменения переменных-членов, включая сеттеры.

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

(4) Инициализировать все члены через конструктор и выполнить глубокую копию (глубокую копию)

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

public final class ImmutableDemo {  
    private final int[] myArray;  
    public ImmutableDemo(int[] array) {  
        this.myArray = array; // wrong  
    }  
}

Этот метод не может гарантировать неизменность. MyArray и массив указывают на один и тот же адрес памяти. Пользователи могут изменить значение внутри myArray, изменив значение объекта массива вне ImmutableDemo.

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

public final class MyImmutableDemo {  
    private final int[] myArray;  
    public MyImmutableDemo(int[] array) {  
        this.myArray = array.clone();   
    }   
}

(5) В методе получения не возвращайте сам объект напрямую, а клонируйте объект и возвращайте копию объекта.

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

7. Наконец

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