Чем больше вы знаете, тем больше вы не знаете
Ставьте лайк и смотрите снова, формируйте привычку
эта статьяGitHub github.com/JavaFamilyОн был включен, есть интеллект-карта точек интервью производителей первой линии, а также я организовал много своих документов. Добро пожаловать в Star и совершенствуйтесь. Каждый может обратиться в испытательный центр для ознакомления. Я надеюсь мы можем иметь что-то вместе.
отплатить
В последнем интервью я обнаружил, что интервьюер все еще не удовлетворен некоторыми моими ответами, а у меня все еще были некоторые сомнения, поэтому я выберу несколько ответов.
16 — это степень числа 2, так же как и 8, и 32 тоже. Почему вы выбрали 16?
Я думаю, что это эмпирическое значение. Нет особых причин для определения числа 16. Пока это степень числа 2, оно практически аналогично 8 и 32.
16 используется только потому, что автор считает, что начальная емкость 16 подходит для общего использования.
Когда размер связанного списка в Hashmap превысит восемь, он будет автоматически преобразован в красно-черное дерево.Когда размер связанного списка меньше шести, он снова станет связанным списком.Почему?
Согласно распределению Пуассона, когда коэффициент загрузки по умолчанию равен 0,75, вероятность того, что количество элементов в одном хеш-слоте равно 8, меньше одного на миллион, поэтому 7 используется как водораздел, а когда он равен 7, он не преобразуется, а если он больше или равен 8, то при выполнении преобразования он преобразуется в связанный список, когда он меньше или равен 6.
текст
Изящная дама в рубашке с изящной тетрадью в руках подошла прямо ко мне и села передо мной.
Как раз когда моя слюна была готова вытечь, слова барышни прервали мой ГГ.
Эй, малыш, ты меня кормишь!
Ба, ба, я ошибаюсь. Последний HashMap ответил хорошо, и интервью резко закончилось, потому что было слишком поздно. На этот раз я должен вас хорошо устроить.
Эй, интервьюер в прошлый раз извинялся, потому что компания должна быть на дежурстве для Double Twelve, действительно нет возможности, но в этот раз я не буду, я все отложил и приготовился посвятить себя сегодняшнему интервью, и даже отодвинул его. Получил приглашение на свидание от дяди Вана из соседнего дома.
Это лучшее.В прошлый раз мы говорили о проблеме безопасности потоков HashMap в многопоточной среде.Как вы обычно справляетесь с этой ситуацией?
Привет, красивый и очаровательный интервьюер, как правило, в многопоточных сценариях я буду использовать несколько разных способов замены:
- Используйте Collections.synchronizedMap(Map) для создания потокобезопасной коллекции карт;
- Hashtable
- ConcurrentHashMap
Однако по причине параллелизма потоков я отброшу первые два и буду использовать последний ConcurrentHashMap, производительность и эффективность которого значительно выше первых двух.
О, вы знаете, как Collections.synchronizedMap обеспечивает потокобезопасность?
Спать *!Не играйте в карты по заведенному порядку,Разве это не нормально спрашивать про HashMap и ConcurrentHashMap?Зачем вы в этот раз спросили об этой хрени?К счастью, я читал стихи и книги,и часто смотрю сериал Ао Бина "Повешение и избиение интервьюера",а то уж совсем быть законченным.
Мисс, вы такой хороший вопрос. Ни один другой интервьюер не задавал его. Честно говоря, ваш уровень должен бытьЛучшие технические экспертыБар.
Не груби, ответь на мой вопрос! натянутая улыбка 😁
Общий объект Map поддерживается внутри SynchronizedMap, а также эксклюзивный мьютекс блокировки, как показано на рисунке.
Collections.synchronizedMap(new HashMap<>(16));
Когда мы вызываем этот метод, нам нужно передать карту. Вы можете видеть, что есть два конструктора. Если вы передаете параметр мьютекса, назначьте блокировку исключения объекта переданному объекту.
Если нет, назначьте для этого монопольную блокировку объекта, то есть объект, вызывающий synchronizedMap, является Map выше.
После создания синхронизированной карты при повторном использовании карты метод будет заблокирован, как показано на картинке 🔐
Вру*, пацан, во-вторых, на самом деле я давно забыл исходники.
Хороший ответ, вы можете поговорить со мной о Hashtable?
Я жду, когда ты спросишь об этом, хе-хе!
По сравнению с HashMap, Hashtable является потокобезопасным и подходит для использования в многопоточных ситуациях, но его эффективность не очень оптимистична.
О, вы можете сказать мне причину его неэффективности?
Хм, интервьюер, я видел его исходный код, и он блокирует данные, когда работает, поэтому эффективность относительно низкая.
В дополнение к этому, можете ли вы сказать что-то другое о Hashtable и HashMap?
! какие? Что это за проблема? Это еще одно слепое пятно знаний!
э-э, интервьюер, я никогда не использовал его, дайте мне подумать о разнице и начать говоритьчесать волосы, На этот раз это не притворство, это реально!
Hashtable не позволяет ключам или значениям быть нулевыми, в то время как ключи и значения HashMap могут быть нулевыми.
Могу я прервать тебя? Почему Hashtable не позволяет KEY и VALUE быть нулевыми, а HashMap может?
Ни*, почему я чувствую, что человек передо мной некрасив в это время, даже как дьявол, глядя на моего интервьюера и думая про себя.
Потому что Hashtable напрямую генерирует исключение нулевого указателя, когда мы помещаем нулевое значение, а HashMap выполняет специальную обработку.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Но вы так и не сказали, почему Hashtable не позволяет ключам или значениям быть нулевыми, в то время как ключи и значения HashMap могут быть нулевыми?
Это потому, что Hashtable используетотказоустойчивый, этот механизм сделает данные, которые вы читаете на этот раз, не обязательно самыми последними данными.
Если вы используете нулевое значение, это сделает невозможным определение того, существует ли соответствующий ключ или он пуст, потому что вы не можете снова вызвать contains(key), чтобы определить, существует ли ключ, и то же самое верно для ConcurrentHashMap.
Ладно, давай, скажи что-нибудь другое.
-
Реализация отличается: Hashtable наследует класс Dictionary, а HashMap наследует класс AbstractMap.
Словарь был добавлен в JDK 1.0, кажется, никто им не пользовался, и я тоже.
Начальная мощность разная: начальная емкость HashMap: 16, начальная емкость Hashtable: 11, коэффициент загрузки по умолчанию для обоих: 0,75.
Различные механизмы расширения: когда существующая емкость превышает общую емкость * коэффициент загрузки, правило расширения HashMap удваивает текущую емкость, а правило расширения Hashtable удваивает текущую емкость + 1.
-
Итераторы бывают разные: Итератор Iterator в HashMap является отказоустойчивым, в то время как Enumerator в Hashtable не является отказоустойчивым.
Поэтому, когда другие потоки изменяют структуру HashMap, например добавляют или удаляют элементы, будет выброшено исключение ConcurrentModificationException, а Hashtable — нет.
Что такое отказоустойчивость?
Ложь*, разве ты сам этого не знаешь? Почему ты меня спрашиваешь! ! ! К счастью, я буду!
отказоустойчивыйЭто механизм в коллекциях Java.При использовании итератора для обхода объекта коллекции, если содержимое объекта коллекции изменяется (добавляется, удаляется, изменяется) во время процесса обхода, будет выдано исключение Concurrent Modification Exception.
Каково его обоснование?
Итератор напрямую обращается к содержимому коллекции по мере прохождения и использует переменную modCount во время обхода.
Если содержимое коллекции изменится во время ее обхода, значение modCount изменится.
Всякий раз, когда итератор использует hashNext()/next() для перехода к следующему элементу, он проверяет, является ли переменная modCount ожидаемым значением modCount, и если да, возвращает результат обхода; в противном случае генерирует исключение и завершает обход.
Tip: Это исключение возникает при обнаружении modCount! =expectedmodCount Это условие. Если измененное значение modCount оказывается равным ожидаемому значению modCount при изменении коллекции, исключение не будет выдано.
Следовательно, программирование параллельных операций не может зависеть от того, выброшено это исключение или нет.Это исключение рекомендуется только для обнаружения ошибок параллельной модификации.
Расскажите мне о его сцене?
Все классы коллекций в пакете java.util являются отказоустойчивыми и не могут быть одновременно изменены в многопоточности (изменены в процессе итерации) в качестве механизма безопасности.
Tip:отказоустойчивыйВы также можете понять, что все контейнеры в пакете java.util.concurrent безопасны для сбоев и могут использоваться и изменяться одновременно в нескольких потоках.
Хорошо? У этого ребенка есть что-то подобное? Почти все отличия уже сказаны, а про забытый Hashtable можно сказать справедливо, он вроде не простой.
Говорят, что его параллелизма не хватает и производительность очень низкая, как вы справляетесь с этим сейчас?
Он здесь, он здесь, он, наконец, здесь, после столь долгого ожидания, просто ожидая, когда вы спросите меня об этом, вы все еще попали в мою ловушку, я уже был готов похоронить его небезопасный поток в HashMap Seeds для цветения и плоды в ConcurrentHashMap!
Мисс: В таком сценарии мы используем ConcurrentHashMap в процессе разработки, и его параллелизм намного лучше, чем у двух предыдущих.
Ой? Тогда расскажите мне о его структуре данных и о том, почему у него такой высокий параллелизм?
Базовый ConcurrentHashMap основан на数组 + 链表
Он составлен, но конкретная реализация немного отличается в jdk1.7 и 1.8.
Позвольте мне сначала рассказать о его структуре данных в 1.7:
Как показано на рисунке, он состоит из массива сегментов и HashEntry.Как и HashMap, он по-прежнемуМассив плюс связанный список.
Segment — это внутренний класс ConcurrentHashMap, основными компонентами которого являются:
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样,真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败(fail—fast)么?
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}
HashEntry похож на HashMap, но разница в том, что он использует volatile для изменения своего значения данных и следующего узла.
Каковы характеристики летучих?
Это обеспечивает видимость, когда разные потоки работают с этой переменной, то есть поток изменяет значение переменной, и новое значение сразу видно другим потокам. (выполнитьвидимость)
Переупорядочивание инструкций отключено. (выполнитьупорядоченность)
volatile гарантирует атомарность только для одного чтения/записи. i++ Эта операция не гарантируетсяатомарность.
Не буду подробно рассказывать, расскажу про многопоточность, все знают, что это безопасно после использования.
Можете ли вы рассказать о причине его высокого параллелизма?
В принципе ConcurrentHashMap используетблокировка сегментатехнология, где Segment наследуется от ReentrantLock.
В отличие от HashTable, операции ввода и получения должны быть синхронизированы.Теоретически ConcurrentHashMap поддерживает параллелизм потоков CurrencyLevel (количество массивов сегментов).
Всякий раз, когда поток занимает блокировку для доступа к сегменту, он не влияет на другие сегменты.
То есть, если размер емкости равен 16, его параллелизм равен 16, что позволяет 16 потокам одновременно обрабатывать 16 сегментов и является потокобезопасным.
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();//这就是为啥他不可以put null值的原因
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
Сначала он находит сегмент, а затем выполняет операцию размещения.
Давайте посмотрим на его исходный код, и вы узнаете, как он достигает потокобезопасности Я аннотировал ключевые предложения.
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 遍历该 HashEntry,如果不为空则判断传入的 key 和当前遍历的 key 是否相等,相等则覆盖旧的 value。
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
// 不为空则需要新建一个 HashEntry 并加入到 Segment 中,同时会先判断是否需要扩容。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
Во-первых, на первом этапе он попытается получить блокировку.Если получение не удается, должны быть другие конкурирующие потоки.scanAndLockForPut()
Блокировка спина.
- Попытка вращения получить блокировку.
- Если количество попыток достигло
MAX_SCAN_RETRIES
Измените получение блокировки на блокировку, чтобы обеспечить успешное получение.
А как насчет логики его получения?
Логика get относительно проста: вам нужно только найти ключ к определенному сегменту после прохождения через хеш, а затем найти его к определенному элементу через хеш.
Поскольку атрибут value в HashEntry изменен с помощью ключевого слова volatile для обеспечения видимости памяти, это самое последнее значение каждый раз, когда оно извлекается.
Метод get ConcurrentHashMap очень эффективен,Потому что весь процесс не нужно блокировать.
Вы обнаружили, что хотя версия 1.7 может поддерживать одновременный доступ к каждому сегменту, все же есть некоторые проблемы?
Да, потому что это в основном метод добавления массива в связанный список.Когда мы переходим к запросу, мы должны пройти по связанному списку, что приведет к низкой эффективности.Это та же проблема, что и HashMap jdk1.7 , так он полностью в jdk1.8 улучшен.
Тогда вы можете поговорить со мной о структуре данных jdk1.8?
Который отказался от оригинальной блокировки сегмента сегмента и принялCAS + synchronized
для обеспечения безопасности параллелизма.
Подобно HashMap, он также изменил предыдущий HashEntry на Node, но функция осталась прежней. Значение и следующий изменены с помощью volatile для обеспечения видимости, а также введено красно-черное дерево. Когда связанный список больше, чем определенное значение будет преобразовано (по умолчанию 8).
Кроме того, вы можете поговорить со мной об операции доступа к его значению? И как обеспечить потокобезопасность?
Операция размещения ConcurrentHashMap относительно сложна, и ее можно условно разделить на следующие этапы:
- Вычислить хэш-код на основе ключа.
- Определите, требуется ли инициализация.
- Это узел, расположенный по текущему ключу. Если он пуст, это означает, что текущая позиция может записывать данные. Используйте CAS, чтобы попытаться записать, и если это не удается, спин гарантирует успех.
- если текущее местоположение
hashcode == MOVED == -1
, его необходимо расширить. - Если ни один из них не удовлетворен, используйте синхронизированную блокировку для записи данных.
- Если количество превышает
TREEIFY_THRESHOLD
Его нужно преобразовать в красно-черное дерево.
Вы упомянули выше, что такое CAS? Что такое спин?
CAS — это реализация оптимистической блокировки и облегченной блокировки.Реализация многих классов инструментов в JUC основана на CAS.
Поток операции CAS показан на рисунке ниже. Поток не блокируется при чтении данных. При подготовке к обратной записи данных он сравнивает, было ли изменено исходное значение. Если оно не было изменено другими потоками, оно будет записан обратно.Если он был изменен, он будет перезаписан.Выполнить процесс чтения.
Это оптимистичная стратегия, предполагающая, что параллельные операции выполняются не всегда.
До сих пор не понимаю? Затем я еще раз объясню, что оптимистическая блокировка очень распространена в реальных сценариях разработки, и все еще должны это понимать.
Например, я хочу изменить часть данных в базе данных.Перед изменением я сначала получаю исходное значение, а затем добавляю оценку в SQL, чтобы увидеть, совпадает ли исходное значение с исходным значением, которое я получил в моей руке. Если это то же самое, мы можем изменить его. Если это не то же самое, это доказывает, что если он изменен другими потоками, вы можете вернуть ошибку.
Псевдокод SQL примерно такой:
update a set value = newValue where value = #{oldValue}//oldValue就是我们执行前查询出来的值
Может ли CAS гарантировать, что данные не были изменены другими потоками?
Нет, например, очень классическая проблема ABA, CAS не может ее судить.
Что такое АБА?
То есть пришел поток, чтобы изменить значение обратно на B, а другой поток пришел, чтобы изменить значение обратно на A. Для потока, который оценивал в это время, было обнаружено, что его значение по-прежнему равно A, поэтому он не Не знаю какое значение было.Оно не изменилось.На самом деле, во многих сценах, если только конечный результат правильный, это не имеет значения.
Тем не менее, в реальном процессе по-прежнему необходимо записывать процесс модификации, такой как модификация фонда и т. Д., У вас должна быть запись каждый раз, когда вы ее изменяете, чтобы облегчить ретроспективу.
Итак, как решить проблему ABA?
Просто используйте номер версии, чтобы гарантировать это. Например, когда я проверяю исходное значение перед модификацией, я привожу номер версии. Каждый раз, когда я выношу суждение, я оцениваю значение и номер версии вместе. Если суждение успешно, я добавлю номер версии к 1.
update a set value = newValue ,vision = vision + 1 where value = #{oldValue} and vision = #{vision} // 判断原来的值和版本号是否匹配,中间有别的线程修改,值可能相等,但是版本号100%不一样
Niu*, что-то есть, кроме номера версии есть еще какие-то гарантии?
На самом деле, есть много способов, таких как временные метки, вы можете вместе проверять временные метки при запросе и вместе изменять время обновления при обновлении значения.Это также может быть гарантировано.Существует много методов, но они похожи на номер версии Это замечательно, давайте посмотрим, как вы хотите оформить сцену.
Производительность CAS очень высока, но я знаю, что производительность синхронизации не очень хорошая.Почему после обновления jdk1.8 больше синхронизации?
Раньше Synchronized всегда был тяжеловесной блокировкой, но позже официальные лица Java обновили его, и теперь он использует для этого метод обновления блокировки.
Для того, как синхронизированный получает блокировки, JVM использует метод оптимизации эскалации блокировки, который заключается в использовании сначалаБлокировка смещенияНазначьте приоритет тому же потоку, а затем снова получите блокировку, если это не удастся, перейдите кЛегкий замок CAS, короткий, если это не удаетсявращение, чтобы предотвратить приостановку потока системой. Наконец, если все вышеперечисленное не помогло, обновите дотяжелый замок.
Таким образом, он был обновлен шаг за шагом, и изначально он был заблокирован многими легкими способами.
🐂, тогда вернемся к теме, а что с операцией get ConcurrentHashMap?
- В соответствии с рассчитанной адресацией хэш-кода, если он находится в корзине, верните значение напрямую.
- Если это красно-черное дерево, получите значение в соответствии с деревом.
- Если он не удовлетворен, то пройдите по связанному списку, чтобы получить значение.
Резюме: 1.8 внесла серьезные изменения в структуру данных 1.7, а использование красно-черных деревьев может обеспечить эффективность запросов (O(logn)
), и даже отменил ReentrantLock и изменил его на синхронизированный, так что видно, что в новой версии JDK оптимизация синхронизации есть.
Суммировать
Hashtable ConcurrentHashMap и HashMap в основном представляют собой наборцепочка комбинация, я часто могу долго дуть во время интервью, и интервьюер часто говорит: Ладно, давай перейдем к следующей теме ха-ха.
Да потому что при упоминании HashMap вы обязательно расскажете о его потокобезопасности.Тогда одним предложением не замкнешь.Не хотят авторы джавы,поэтому написали и разработали соответствующие альтернативы,тогда это поток -safe Hashtable&ConcurrentHashMap.
Оба имеют характеристики, но сценарий безопасности потоков по-прежнемуПоследний использует немного больше, причина, по которой я уже подробно и всесторонне представил ее в статье, поэтому не буду здесь вдаваться в подробности.
ты нашелИнтервью это яма, интервьюер может ударить вас, что бы вы ни сказали, не спрашивайте меня, откуда я знаю, хе-хе.
Вы знаете, что не уверены, сможете ли вы добавить баллы этому интервью, но вы не знаете, что это должно быть минусом.отказоустойчивыйспросил, что соответствуетотказоустойчивыйЭто также возможно знать, я думаю, что многие читатели этого не знают, потому что я спросил многих детей, ха-ха.
Также упоминается оптимистическая блокировка CAS, вам нужно знать ABA, вам нужно знать решение, потому что оно действительно не слишком часто используется в реальных сценариях разработки, и вам также необходимо знать обновление блокировки синхронизации.
Я не стал слишком много описывать про потокобезопасность, потому что написал все, что будет еще в будущем? Правильно ха-ха.
Общая проблема
- Поговорите о хеш-таблице, которую вы понимаете, и обсудите с ней процесс размещения. ConcurrentHashMap запрашивает то же самое.
- 1.8 Какие оптимизации были сделаны?
- Как обеспечивается безопасность потоков?
- Какие проблемы может вызвать неуверенность?
- Как решить? Существуют ли потокобезопасные параллельные контейнеры?
- Как реализован ConcurrentHashMap?
- Почему параллелизм ConcurrentHashMap намного лучше?
- В чем разница между реализациями 1.7 и 1.8? Зачем это делать?
- Что такое КАС?
- Что такое АБА? Какие бывают сценарии и как их решить?
- В чем заключается принцип синхронизации?
- Стратегия синхронизированной эскалации блокировок
- Что такое отказоустойчивость и каковы сценарии применения? Спросите отказоустойчивость.
- ...
бонус
Отвечая на вопросы интервью, связанные с Hashtable и ConcurrentHashMap, вы должны знать, как они обеспечивают безопасность потоков.Небезопасность потоков обычно возникает в процессе доступа, и вы должны знать о get и put.
HashMap — это тот, который необходимо задать. Эти два вопроса часто используются в качестве замещающих вопросов, но их часто задают. Их механизмы на самом деле относительно просты. В частности, ConcurrentHashMap очень похож на HashMap, но отличается с точки зрения безопасности потоков. .
Когда дело доходит до безопасности потоков, вы должны знать соответствующие точки знаний. Например, когда вы идете в CAS, вы должны знать проблему ABA. Когда дело доходит до синхронизированного, вы должны знать его принцип. Он блокирует объекты, методы, и блоки кода.Нижний слой, как достичь.
Synchronized вам также нужно знать его механизм эскалации блокировки, и его брат ReentantLock, один на уровне jvm, а другой на уровне jdk, все же есть большая разница.
Когда дело доходит до двух из них, вам нужно знать все общие классы в пакете juc и их основные принципы?
Это упомянул...
Обратите внимание, не потеряйтесь
Хорошо всем, вышеизложенное является полным содержанием этой статьи. Люди, которые могут видеть это здесь, всеталант.
Каждую неделю я буду обновлять несколько статей, связанных с интервью и общими технологическими стеками ведущих интернет-компаний, большое спасиботалантМы можем видеть здесь, если эта статья хорошо написана, я думаю, что «Ао Бин» ячто-тоеслиПожалуйста, лайкните 👍 Пожалуйста, следите за ❤️ поделитесь пожалуйста 👥Это правда для меняочень полезно! ! !
Проституция нехороша, творить нелегко,Ваша поддержка и признание — самая большая мотивация для моего творчества, увидимся в следующей статье!
Ао Бин | Текст [Оригинал]
Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!
Брюшная поэзия и газ из КитаяСтатья постоянно обновляется каждую неделю, вы можете искать в WeChat "Третий принц Ао Бин"Читать и запрашивать обновления в первый раз (на одну-две статьи раньше, чем в блоге), эту статьюGitHub github.com/JavaFamilyОн был включен, есть карта разума точек интервью заводов первого уровня, а также я организовал много своих документов. Добро пожаловать в Звезду и совершенствуйтесь. Каждый может обратиться в тестовый центр для ознакомления. Надеюсь мы можем иметь что-то вместе.