HashMap небезопасен для потоков. При работе с переменными экземпляра типа HashMap в объекте в многопоточной среде могут возникнуть различные непредвиденные проблемы.
В этой статье подробно объясняется несколько проблем безопасности потоков, существующих в HashMap.
Примечание. Следующее основано на JDK1.8.
1 Многопоточная установка может привести к потере элементов
1.1 Тестовый код выглядит следующим образом
Примечание. Как и пример кода, который может вызвать эту проблему, его запуск напрямую не обязательно вызывает проблемы.
public class ConcurrentIssueDemo1 {
private static Map<String, String> map = new HashMap<>();
public static void main(String[] args) {
// 线程1 => t1
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 99999999; i++) {
map.put("thread1_key" + i, "thread1_value" + i);
}
}
}).start();
// 线程2 => t2
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 99999999; i++) {
map.put("thread2_key" + i, "thread2_value" + i);
}
}
}).start();
}
}
1.2 Сценарии, вызывающие эту проблему
Давайте сначала посмотрим на исходный код метода put.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, I;
// 初始化hash表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过hash值计算在hash表中的位置，并将这个位置上的元素赋值给p，如果是空的则new一个新的node放在这个位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// hash表的当前index已经存在元素，向这个元素后追加链表
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) { // #1
p.next = newNode(hash, key, value, null); // #2
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();
afterNodeInsertion(evict);
return null;
}
Предположим, что статус таблицы в текущем HashMap следующий:
В это время t1 и t2 выполняют put одновременно, предполагая, что t1 выполняет put("key2", "value2"), t2 выполняет put("key3", "value3"), и хэш-значения key2 и key3 такие же, как key1 на рисунке.
Тогда при нормальных обстоятельствах, после завершения пут, состояние стола должно быть одним из двух, как показано на рисунке ниже.
Давайте посмотрим на исключения
Предположим, что поток 1 и поток 2 теперь выполняются до позиции #1 в исходном коде put, а текущее состояние таблицы выглядит следующим образом.
Затем оба потока выполнили код if ((e = p.next) == null) и пришли к строке кода №2.
На данный момент предполагается, что t1 сначала выполняет p.next = newNode(hash, key, value, null);
Тогда таблица станет следующим состоянием
Сразу после t2 выполнить p.next = newNode(hash, key, value, null);
В этот момент таблица примет следующее состояние
В результате элемент key2 теряется.
2 Когда put и get являются параллельными, это может привести к тому, что get будет нулевым
Сценарий: когда поток 1 выполняет команду put, вызывается перехеширование, так как число элементов превышает пороговое значение, а поток 2 в это время выполняет get, что может вызвать эту проблему.
проанализируйте, как показано ниже:
Сначала взгляните на исходный код метода изменения размера.
Грубо говоря, сначала вычислите новую емкость и порог, создайте новую хеш-таблицу и, наконец, перехешируйте элементы из старой хеш-таблицы в новую хеш-таблицу.
Ключевой код — это два предложения №1 и №2.
// hash表
transient Node<K,V>[] table;
final Node<K,V>[] resize() {
// 计算新hash表容量大小，begin
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 计算新hash表容量大小，end
@SuppressWarnings({"rawtypes","unchecked”})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // #1
table = newTab; // #2
// rehash begin
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// rehash end
return newTab;
}
В позиции кода #1 создается новая хеш-таблица с вновь рассчитанной емкостью, а #2 присваивает только что созданную пустую хеш-таблицу таблице переменных экземпляра.
Обратите внимание, что в настоящее время таблица переменных экземпляра пуста.
Затем, если в это время другой поток выполнит get, он получит null.
3 Параллельное размещение HashMap в JDK7 приведет к циклическому связанному списку, что приведет к бесконечному циклу во время получения
Эта проблема была решена в JDK8.
3.1 Формирование кругового связанного списка в JDK7
Возникает в случае многопоточного одновременного изменения размера.
Соответствующий исходный код выглядит следующим образом:
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
// 关键在于这个transfer方法，这个方法的作用是将旧hash表中的元素rehash到新的hash表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) { // table变量即为旧hash表
while(null != e) {
// #1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 用元素的hash值计算出这个元素在新hash表中的位置
int i = indexFor(e.hash, newCapacity);
// #2
e.next = newTable[I];
// #3
newTable[i] = e;
// #4
e = next;
}
}
}
Предполагая, что поток 1 (t1) и поток 2 (t2) изменяются в одно и то же время, до изменения размера двух потоков состояние двух потоков и хэш-карты выглядит следующим образом.
Поле таблицы в объекте HashMap в куче памяти указывает на старую хэш-таблицу, и есть два элемента в позиции индекса 7. Давайте возьмем перефразирование этих двух элементов в качестве примера, чтобы увидеть, как формируется кольцевой связанный список. .
Поток 1 и поток 2 соответственно создают новую хэш-таблицу, которая представлена полем newTable.
PS: Если выполнение каждого шага представлено в виде графика, места слишком много, вот статус в конце каждого цикла, который можно пошагово рассчитать по коду и пояснению каждого шага .
Step1: После того, как t2 выполнит код #1, ЦП переходит к выполнению t1, и выполнение t1 завершено.
Здесь можно рассчитать на основе приведенного выше рисунка, состояние на данный момент выглядит следующим образом.
Используйте t2.e для представления локальной переменной e в потоке 2, а t2.next — то же самое.
Step2: t2 продолжает выполнять этот цикл вниз
Step3: t2 продолжить выполнение следующего цикла
Step4: t2 продолжает следующий цикл, появляется круговой связанный список
3.2 Возникновение бесконечного цикла
Исходный код метода HashMap.get выглядит следующим образом:
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 遍历链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 假设这里条件一直不成立
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
Как видно из рисунка выше, e = e.next в цикле for никогда не будет пустым, поэтому если вы получите ключ, которого нет в этом связанном списке, будет бесконечный цикл.
Добро пожаловать в мой публичный аккаунт WeChat