Это 58-я статья рубрики «Дорога продвинутого Java-программиста», давайте поговорим о том, почему HashMap небезопасен для потоков.
01. Расширение при многопоточности вызовет бесконечный цикл
Как мы все знаем, HashMap использует метод zipper для разрешения коллизий хэшей, то есть при возникновении коллизий хэшей пары ключ-значение с одинаковым хеш-значением сохраняются в виде связанного списка.
В JDK 7 для хранения связанного списка используется метод вставки заголовка, то есть следующая конфликтующая пара ключ-значение будет помещена перед предыдущей парой ключ-значение (новый элемент в той же позиции помещается в начало списка). заголовок связанного списка). При расширении это может привести к круговому связанному списку, что приведет к бесконечному циклу.
Исходный код метода изменения размера:
// newCapacity为新的容量
void resize(int newCapacity) {
// 小数组，临时过度下
Entry[] oldTable = table;
// 扩容前的容量
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
if (oldCapacity == MAXIMUM_CAPACITY) {
// 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
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);
}
Метод Transfer используется для переноса, копирования элементов небольшого массива в новый массив.
void transfer(Entry[] newTable, boolean rehash) {
// 新的容量
int newCapacity = newTable.length;
// 遍历小数组
for (Entry<K,V> e : table) {
while(null != e) {
// 拉链法，相同 key 上的不同值
Entry<K,V> next = e.next;
// 是否需要重新计算 hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根据大数组的容量，和键的 hash 计算元素在数组中的下标
int i = indexFor(e.hash, newCapacity);
// 同一位置上的新元素被放在链表的头部
e.next = newTable[i];
// 放在新的数组上
newTable[i] = e;
// 链表上的下一个元素
e = next;
}
}
}
Уведомлениеe.next = newTable[i]иnewTable[i] = eЭти две строки кода поместят новый элемент в ту же позицию в начале списка.
Если внешний вид до расширения выглядит следующим образом.
Тогда нормальное расширение выглядит следующим образом.
Предположим теперь, что есть два потока, расширяющихся одновременно, и поток A выполняется дляnewTable[i] = e;Приостановлено, в настоящее время в потоке A: e=3, next=7, e.next=null
Поток B начинает выполнение и завершает передачу данных.
В этот момент следующее из 7 равно 3, а следующее из 3 равно нулю.
Затем поток A получает квант времени процессора и продолжает выполнение.newTable[i] = e, поместите 3 в соответствующую позицию нового массива, и ситуация потока A после выполнения этого раунда цикла будет следующей:
Выполнить следующий цикл, в это время e=7, следующим из 7 в потоке A будет 5, но поскольку таблица совместно используется потоком A и потоком B, и после успешного выполнения потока B, следующим из 7 становится 3, Затем в потоке A в это время следующим из 7 также является 3.
Используя метод вставки головы, он становится следующим:
Вроде нет проблем, в это время next = 3, e = 3.
Выполняется следующий раунд цикла, но в это время, поскольку поток B изменяет следующее из 3 на null, этот раунд цикла должен быть последним.
Далее при исполненииe.next=newTable[i]То есть после 3.next=7, 3 и 7 связаны друг с другом, после выполненияnewTable[i]=eПосле этого 3 повторно вставляется в связанный список методом вставки головы, а результат выполнения показан на следующем рисунке:
Начались матрешки, и элемент 5 превратился в брошенного младенца, несчастного~~~
Однако эта проблема была исправлена в JDK 8, и исходный порядок связанного списка будет сохранен при расширении.Механизм расширения HashMapэтой статьи.
02. Многопоточность приведет к потере элементов
Обычно, когда происходит коллизия хэшей, HashMap выглядит так:
Однако когда несколько потоков выполняют операцию размещения одновременно, если вычисленные позиции индекса совпадают, это приведет к тому, что предыдущий ключ будет перезаписан последним ключом, что приведет к потере элементов.
Исходный код put:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
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);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
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;
}
Проблема возникает на шаге ② здесь:
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
Оба потока выполняют оператор if, предполагая, что поток A выполняется первым. tab[i] = newNode(hash, key, value, null), таблица выглядит так:
Затем поток B выполняет tab[i] = newNode(hash, key, value, null), таблица выглядит так:
3 убит.
03. Когда put и get являются параллельными, это приведет к нулевому значению get
Когда поток A выполняет put, он расширяется, потому что количество элементов превышает пороговое значение Поток B в это время выполняет get, что может вызвать эту проблему.
Обратите внимание на исходный код изменения размера:
final Node<K,V>[] resize() {
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;
}
// 没超过最大值，就扩充为原来的2倍
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);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
}
Поток A завершает выполнениеtable = newTabПосле этого в это время изменилась и таблица в потоке B. В это время, когда вы пойдете на получение, вы, конечно же, попадете в null, потому что элемент не был передан.
Чтобы всем было проще систематически изучать Java, второй брат открыл исходный код колонки «Дорога к продвинутым программистам Java» на GitHub. друзья. .
Адрес гитхаба:GitHub.com/IT Ван Эр/до…