счет за волкаПожалуйста, указывайте первоисточник при перепечатке, спасибо!
проблема
В последних нескольких интервью я спрашивал, понимаю ли я, что HashMap может иметь бесконечный цикл при одновременном использовании, что приводит к 100% загрузке процессора.Результат меня удивил и сказал, что я не знал о такой проблеме.Меня удивило то, трудовая жизнь интервьюера не коротка.
Поскольку HashMap не является потокобезопасным, в случае высокого параллелизма неизбежно возникнут проблемы.Это распространенная проблема.Хотя в Интернете проанализировано много статей, я все же считаю, что необходимо написать статью, чтобы студенты кто обратит внимание на мой официальный аккаунт.Знайте о проблеме и поймите как возникает этот бесконечный цикл.
Если HashMap используется в одном потоке, проблем нет, если логика вводит многопоточное параллельное выполнение из-за оптимизации кода на более позднем этапе, в неизвестный момент времени, будет обнаружено, что ЦП занимает 100% и остается high.Посмотрев на стек, вы с удивлением обнаружите, что все потоки висят на методе get() hashMap.После перезапуска сервиса проблема исчезает и может появиться снова через некоторое время.
это почему?
Анализ причин
Прежде чем разобраться во всех тонкостях, давайте взглянем на структуру данных HashMap.
Внутри HashMap использует массив Entry для хранения данных ключа и значения. Когда добавляется пара ключа и значения, нижний индекс массива получается с помощью хеш-алгоритма. Алгоритм очень прост. В соответствии с хеш-значением ключ, определяется размер массива.Взять по модулю хеш&(длина-1),и вставить результат в позицию массива.Если на этой позиции уже есть элемент,значит конфликт хэшей , который создаст связанный список в позиции индекса.
Если есть конфликт хэшей, в худшем случае все элементы расположены в одной и той же позиции, образуя длинный связанный список, поэтому при получении значения в худшем случае необходимо пройти все узлы, и производительность становится O (n) , Так что алгоритм хеширования элементов и начальный размер HashMap очень важны.
При вставке нового узла, если такого же ключа не существует, будет оцениваться, достиг ли текущий внутренний элемент порогового значения (по умолчанию 0,75 от размера массива).Элементы повторно хэшируются.
выполнить
Реализация метода put HashMap:
1. Определите, существует ли уже ключ
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
// 如果key已经存在，则替换value，并返回旧值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// key不存在，则插入新的元素
addEntry(hash, key, value, i);
return null;
}
2. Проверьте, достигает ли емкость порогового значения
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
Если количество элементов достигло порога, расширьте емкость и переместите исходные элементы.
3. Реализация расширения
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
...
Entry[] newTable = new Entry[newCapacity];
...
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Здесь будет создан массив большего размера, а элементы будут перемещены методом переноса.
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];
newTable[i] = e;
e = next;
}
}
}
Логика перемещения также очень понятна: пройдите по связанному списку каждой позиции в исходной таблице, повторно хешируйте каждый элемент, найдите место назначения в новой новой таблице и вставьте его.
анализ случая
Предположим, что начальный размер HashMap равен 4, и вставляются 3 узла. К сожалению, все эти 3 узла хэшируются в одно и то же место. Если используется коэффициент загрузки по умолчанию, вставка третьего узла увеличит емкость. Чтобы проверить эффект, предположим, что коэффициент нагрузки равен 1.
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];
newTable[i] = e;
e = next;
}
}
}
Выше приведена соответствующая логика движения узлов.
При вставке четвертого узла происходит перехеширование Предположим, что одновременно выполняются два потока, поток 1 и поток 2. Оба потока создадут новый массив.
Предположениенить 2в исполненииEntry<K,V> next = e.next;После этого квант процессорного времени израсходован, и переменная e указывает на узел a, а переменная next указывает на узел b.
нить 1Продолжайте выполнять, к сожалению, узлы a, b и c находятся в той же позиции 7 после повторного хеширования, и начинают перемещать узел
Первый шаг — переместить узел a
Второй шаг — переместить узел b
Обратите внимание, что порядок здесь обратный, продолжайте перемещать узел c
В настоящее времянить 1Квант времени израсходован, а для внутренней таблицы не задана новая таблица newTable.нить 2Запустите выполнение, и внутренняя ссылочная связь выглядит следующим образом:
В это время внить 2, переменная e указывает на узел a, переменная next указывает на узел b, и начинает выполняться остальная логика тела цикла.
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
Ссылочное отношение после выполнения выглядит следующим образом
После выполнения переменная e указывает на узел b, поскольку e не равно нулю, затем продолжайте выполнять тело цикла, ссылочное отношение после выполнения
Переменная e снова указывает на узел a и может продолжать выполнять только тело цикла Вот тщательный анализ:
1. ГотовоEntry<K,V> next = e.next;, в настоящее время узел a не имеет next, поэтому переменная next указывает на null;
2,e.next = newTable[i];Среди них newTable[i] указывает на узел b, то есть следующий из a указывает на узел b, так что a и b ссылаются друг на друга, образуя кольцо;
3.newTable[i] = eПоместите узел a в позицию массива i;
4.e = next;Присвойте переменной e значение null, потому что переменная next указывает на null на первом шаге;
Таким образом, окончательное ссылочное отношение выглядит следующим образом:
Узлы a и b ссылаются друг на друга и образуют кольцо.Когда get находит соответствующий ключ в позиции массива, возникает бесконечный цикл.
Кроме того, если поток 2 установит newTable во внутреннюю таблицу, данные узла c будут потеряны, и похоже, что проблема потери данных все еще существует.
Суммировать
Поэтому в случае параллелизма при расширении может быть сгенерирован круговой связанный список.При выполнении get будет запущен бесконечный цикл, вызывающий 100% проблемы с процессором.Поэтому необходимо избегать использования HashMap в параллельной среде. .
Кто-то однажды сообщил об этой проблеме в Sun, но Sun не считает это ошибкой, потому что HashMap не поддерживает многопоточное использование, а ConcurrentHashmap используется для параллельного использования.
КОНЕЦ. Я маленький волк. Если вы найдете это полезным после прочтения, не забудьте подписаться и поставить лайк