HashMap может разговаривать с интервьюером полчаса
обрати внимание наБлог Анджелы 1. ОтветитьинтервьюПолучить материалы интервью 2. ОтветитькнигиПолучайте технические электронные книги 3. ОтветитьобщатьсяПрисоединяйтесь к группе технических коммуникаций
предисловие
HashMap должен быть обязательным атрибутом для интервью с Java-инженером, потому что в нем слишком много знаний, что очень подходит для изучения основы Java интервьюируемого.
открытие
интервьюер: Сначала представьтесь!
Анджела: Я Анджела, одна из трех сучек в траве, сильнейший мидлейнер (Чжун Куи не согласен)! О, нет, я на месте, я **, сейчас работаю в -- компании -- по разработке систем.
интервьюер: Увидев в резюме, что вы знакомы с коллекциями Java, использовали ли вы HashMap?
Анджела: использовал. (до сих пор знакомый вкус)
интервьюер: Тогда расскажи мне о внутренней структуре данных HashMap?
Анджела: В настоящее время я использую версию JDK1.8, которая использует красно-черное дерево массива + связанного списка;
Анджела: Позвольте мне нарисовать для вас схему структуры данных:
интервьюер: Вы знаете принцип вставки данных HashMap?
Анджела: Эээ [делает задумчивый жест]. Думаю, лучше нарисовать картинку, чтобы было понятнее, вот так:
Определить, пуст ли массив, инициализировать его, если он пуст;
не пусто, вычислить хэш-значение k, передать(n - 1) & hashВычислить индекс индекса, который должен храниться в массиве;
Проверить, есть ли данные в таблице[индекс], если данных нет, создать узел Node и сохранить его в таблице[индекс];
Если данные есть, значит, произошел конфликт хэшей (значения хэшей ключей двух узлов совпадают), продолжаем судить, равны ли ключи или нет, и заменяем исходные данные на новые значение (onlyIfAbsent равно false);
Если они не равны, определить, является ли текущий тип узла узлом дерева.Если это узел дерева, создать узел дерева и вставить его в красно-черное дерево;
Если это не узел дерева, создайте обычный Node и добавьте его в связанный список, определите, больше ли длина связанного списка 8, если больше, связанный список преобразуется в красно-черное дерево;
После завершения вставки оценивается, превышает ли текущее количество узлов пороговое значение.
интервьюер: Вы только что упомянули об инициализации HashMap.Как HashMap устанавливает начальную емкость?
Анджела: [Это проблема? ?] Обычно, еслиnew HashMap()Если значение не передано, размер по умолчанию равен 16, а коэффициент загрузки равен 0,75.Если вы передаете начальный размер k, начальный размер представляет собой целочисленную степень 2, большую, чем k, например, если вы передаете 10, размер 16. (Дополнительное примечание: код реализации выглядит следующим образом)
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;
}
Дополнительное пояснение: на следующем рисунке показан подробный процесс Алгоритм состоит в том, чтобы сдвинуть исходный двоичный файл вправо на 1, 2, 4, 8 и 16 бит и выполнить операцию XOR с самим собой соответственно и переместить первое число старшего разряда. 1 вправо, непрерывно перемещая старший разряд вправо Последние несколько цифр 1 становятся 1, 111111 + 1 = 1000000 =(Соответствует целочисленным степеням больше 50 и степеням числа 2)
интервьюер: Вы упомянули хэш-функцию, знаете ли вы, как устроена хеш-функция HashMap?
Анджела: [Вопрос довольно тонкий] Хеш-функция состоит в том, чтобы сначала получить хэш-код, переданный через ключ, который является 32-битным значением int, а затем XOR над старшими 16 битами и младшими 16 битами хэш-кода.
интервьюер: Вы знаете, почему он разработан таким образом?
Анджела[Это также спрашивает], это также называется функцией беспокойства, поэтому она предназначена для двух причин:
Убедитесь, что коллизии хэшей максимально уменьшены, чем больше разбросанных, тем лучше;
Алгоритм должен быть максимально эффективным, потому что это высокочастотная операция, поэтому используются побитовые операции;
интервьюер: Почему использование XOR старших 16 бит и младших 16 бит хэш-кода уменьшает коллизии хэшей? Может ли хэш-функция напрямую использовать хэш-код ключа?
[Этот вопрос немного каверзный], Анжела почти стояла 💥, не могу дождаться комбо biubiubiu 213.
Анджела: потому что функция key.hashCode() вызывает хеш-функцию, которая поставляется с типом значения ключа и возвращает хэш-значение типа int. Диапазон значений int составляет **-2147483648~2147483647**, что в сумме составляет около 4 миллиардов пробелов отображения до и после. До тех пор, пока хэш-функция отображается равномерно и нечетко, для обычных приложений трудно столкнуться. Но проблема в том, что массив длиной 4 миллиарда не помещается в памяти. Думаете, если начальный размер массива HashMap всего 16, то перед использованием нужно провести операцию по модулю над длиной массива, а остаток можно использовать для доступа к индексу массива. (от Чжиху-толстяк)
Операция по модулю в исходном коде заключается в выполнении операции «И» между хеш-значением и длиной массива -1, а битовая операция выполняется быстрее, чем операция %.
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
}
Кстати, это также точно объясняет, почему длина массива HashMap берется как целая степень числа 2. Потому что это (длина массива - 1) точно эквивалентно "младшей битовой маске". Результатом операции «И» является то, что все старшие биты хеш-значения обнуляются, и только младшие биты сохраняются для доступа к индексу массива. В качестве примера возьмем начальную длину 16, 16-1 = 15. Двоичное представление: 00000000 00000000 00001111. Операция И с хэш-значением выглядит следующим образом, и в результате усекается самое низкое четырехбитное значение.
Но здесь возникает проблема, так что даже если мое распределение значений хеш-функции будет свободным, если будут взяты только последние несколько битов, коллизия будет очень серьезной. Что еще более ужасно, так это то, что если сам хэш не очень хорошо сделан, распределение лазеек в арифметической последовательности, если последние несколько младших битов просто регулярно повторяются, будет крайне болезненным.
В это время отражается значение «функции возмущения», и здесь каждый должен ее угадать. Посмотрите на картинку ниже,
Правый сдвиг составляет 16 бит, что составляет ровно половину битов 32. Старшая и младшая половина собственной области подвергаются операции XOR, чтобы смешать старшие и младшие биты исходного хэш-кода, чтобы увеличить случайность младших битов. Более того, смешанные младшие биты дополняются некоторыми свойствами старших битов, так что старшие биты также сохраняются в замаскированном виде.
Наконец, давайте взглянем на эксперимент в колонке Питера Лоули «Введение в оптимизацию стратегии хеширования»: он случайным образом выбирает 352 строки, и, исходя из того, что их хэш-значения вообще не конфликтуют, выполните самые низкие -order mask и взять индекс массива.
Результаты показывают, что при длине массива HashMap 512 (), то есть при использовании маски для взятия младших 9 бит без функции возмущения произошло 103 коллизии, что близко к 30%. А после использования функции возмущения всего 92 столкновения. Столкновения были уменьшены почти на 10%. Кажется, что функция возмущения все еще действует.
Кроме того, Java 1.8 была скорректирована по сравнению с 1.7.1.7 сделал четыре сдвига и четыре XOR, но, очевидно, Java 8 считает, что одного возмущения достаточно.Если вы сделаете 4 раза, предельная полезность может быть невелика.Так называемая ради эффективности он был изменен на один раз.
Вот хеш-код для 1.7:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
интервьюер: Кажется, я сделал домашнее задание, и это немного предсказуемо! Вы заглянули в него?Блог Анджелы, Вы только что упомянули, что 1.8 оптимизирует хэш-функцию.Есть ли в 1.8 другие оптимизации?
Анджела: 1.8 также имеет три основные оптимизации:
Массив + связанный список меняется на массив + связанный список или красно-черное дерево;
Метод вставки связанного списка был изменен с метода вставки головы на метод вставки хвоста.Короче говоря, при вставке, если в позиции массива уже есть элемент, 1.7 помещает новый элемент в массив, а исходный узел используется в качестве узла-преемника нового узла 1.8 Пройдите по связанному списку, поместите элемент в конец связанного списка;
При расширении 1.7 необходимо повторно хэшировать элементы в исходном массиве и найти их в новом массиве.1.8 использует более простую логику оценки, позиция остается неизменной или индекс + старый размер емкости;
При вставке 1.7 сначала решает, требуется ли расширение, а затем вставляет, 1.8 сначала вставляет, а затем оценивает, требуется ли расширение после завершения вставки;
интервьюер: Расскажите о том, зачем вам нужно делать эти оптимизации;
Анджела: [кашель, это действительно серийная пушка]
1.8 Использовать красно-черное дерево: предотвращение конфликтов хэшей, слишком большая длина связанного списка, изменение временной сложности сO(n)сокращено доO(logn);
1.8 Используйте метод вставки хвоста: поскольку метод вставки заголовка перевернет связанный список в 1.7, когда метод вставки заголовка будет развернут, в многопоточной среде будет создано кольцо;
Поток A вставляет узел B, а также вставляет поток B. Когда емкости недостаточно, он начинает расширяться, перехешировать, размещать элементы, использовать метод вставки головы, а затем перемещать узел B в голову, таким образом образуя кольцо, как показано на следующем рисунке:
Расширение 1.7 вызывает код передачи следующим образом:
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; //A线程如果执行到这一行挂起，B线程开始进行扩容
newTable[i] = e;
e = next;
}
}
}
Почему при расширении емкости 1.8 может напрямую определить местоположение исходного узла в новых данных без повторного хеширования?
Это связано с тем, что расширение должно удвоить размер исходного массива, а маска, используемая для вычисления позиции массива, представляет собой просто дополнительную 1 в старшем разряде.Как это понять?
До расширения длина равна 16, а двоичный код n-1, используемый для вычисления (n-1) и хэша, равен 0000 1111. После расширения 32 старший бит равен 1, то есть 0001 1111.
Поскольку это операция &, 1 и любое число & являются самими собой, поэтому есть два случая, как показано на следующем рисунке: случай, когда старший 4-й бит исходного хэш-кода данных равен 0, а старший бит 1;
Старший бит четвертой цифры равен 0, значение повторного хеширования остается неизменным, четвертая цифра равна 1, а значение повторного хеширования больше исходного на 16 (емкость старого массива)
интервьюер: Является ли HashMap потокобезопасным?
Анджела: Нет, в многопоточной среде у 1.7 будут проблемы с бесконечным циклом, потерей данных и покрытием данных, а у 1.8 будут проблемы с покрытием данных.Возьмите 1.8 в качестве примера, см. код в 👇, когда поток A считает, что позиция индекса пуста Затем он просто зависает, и поток B начинает записывать данные узла в позицию индекса.В это время поток A возобновляет сцену и выполняет операцию присваивания, которая перезапишет данные потока A; и + +size также вызовет многопоточность, расширение и другие проблемы.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //多线程执行到这里
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 多个线程走到这，可能重复resize()
resize();
afterNodeInsertion(evict);
return null;
}
интервьюер: Итак, как вы обычно решаете эту проблему небезопасности потоков?
Анджела: Java имеет HashTable, Collections.synchronizedMap и ConcurrentHashMap для реализации поточно-ориентированной карты.
HashTable напрямую добавляет ключевое слово synchronized в метод операции, блокирует весь массив, а степень детализации блокировки относительно велика. Collections.synchronizedMap — это внутренний класс, использующий инструмент сбора коллекций. Он инкапсулирует объект SynchronizedMap, передавая его в Map, и определяет внутренняя блокировка объекта. , этот метод обеспечивает безопасность потоков за счет блокировок объектов; ConcurrentHashMap использует блокировки сегментов, что уменьшает детализацию блокировок и значительно улучшает параллелизм.
интервьюер: Вы знаете принцип реализации сегментной блокировки ConcurrentHashMap?
Анджела:[Tianlalu!Русские матрешки,по одной на каждую]Переменные-члены ConcurrentHashMap модифицируются с помощью volatile, что позволяет избежать переупорядочивания инструкций и обеспечивает видимость памяти.Кроме того, для реализации операции присваивания используются операции CAS и synchronized.Многопоточные операции будут только lock Удерживает узел индекса текущей операции.
Как показано на рисунке ниже, поток A блокирует связанный список, в котором находится узел A, а поток B блокирует связанный список, в котором находится узел B, и операции не мешают друг другу.
интервьюер: Вы упоминали ранее, что связанный список преобразуется в красно-черное дерево, когда длина связанного списка достигает порога.Какой порог?
Анджела: Пороговое значение равно 8, а пороговое значение красно-черного дерева для связанного списка равно 6.
интервьюер: Почему 8, а не 16, 32 или даже 7? Почему порог связного списка красно-черного дерева равен 6, а не 8?
Анджела: [Иди спроси у автора! Боже, biubiubiu очень хочу 213 комбо] потому что автор так спроектировал, о нет, потому что после расчета, при условии, что хэш-функция спроектирована разумно, вероятность 8-ми хеш-коллизий составляет 6 на миллион, а вероятность сказать. . Потому что 8 достаточно, а почему отдача 6, потому что если количество коллизий хэшей колеблется около 8, то всегда будет происходить взаимное преобразование между связным списком и красно-черным деревом.Чтобы этого не произошло, установите это до 6.
интервьюер: Упорядочены ли внутренние узлы HashMap?
Анджела: неупорядочено, вставляется случайным образом в соответствии с хеш-значением
интервьюер: Есть заказанная Карта?
Анджела: LinkedHashMap и TreeMap
интервьюер: Расскажите, как упорядочивается LinkedHashMap?
Анджела: LinkedHashMap внутренне поддерживает односвязный список с головными и конечными узлами.В то же время запись узла LinkedHashMap не только наследует свойство узла HashMap, но также до и после идентификации переднего узла и заднего узла. Возможна сортировка по порядку вставки или порядку доступа.
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
//链接新加入的p节点到链表后端
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
//LinkedHashMap的节点类
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
интервьюер: Расскажите, как упорядочивается TreeMap?
Анджела: TreeMap сортируется в соответствии с естественным порядком Key или порядком функции сравнения реализованного интерфейса Comprator, который внутренне реализуется красно-черным деревом. Таким образом, либо класс, которому принадлежит ключ, реализует интерфейс Comparable, либо пользовательский компаратор, реализующий интерфейс Comparator, передается в TreeMap для сравнения ключей.
интервьюер: Как упоминалось ранее, уменьшение детализации блокировки достигается за счет комбинации CAS и синхронизированного.Можете ли вы рассказать мне о реализации CAS и принципе реализации синхронизированного?
Анджела: Давай договоримся о следующем выпуске, хорошо?
В будущем будут обновлены некоторые наиболее часто задаваемые вопросы об основных производителях, в основном для серверной части Java. Вы также можете отвечать на ключевые слова в фоновом режиме публичной учетной записи.интервьюЗаранее получите материалы для интервью.
1. ОтветитьинтервьюПолучить материалы интервью
2. ОтветитькнигиПолучайте технические электронные книги
3. ОтветитьобщатьсяВойдите в группу технического обмена
(Соответствует целочисленным степеням больше 50 и степеням числа 2)
), то есть при использовании маски для взятия младших 9 бит без функции возмущения произошло 103 коллизии, что близко к 30%. А после использования функции возмущения всего 92 столкновения. Столкновения были уменьшены почти на 10%. Кажется, что функция возмущения все еще действует.