2025年2月24日 星期一 甲辰(龙)年 腊月廿四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > Java

HashMap多线程不安全原因分析

时间:01-31来源:作者:点击数:57

众所周知,HashMap在多线程环境下是线程不安全的,

在jdk1.7中,主要有两个方面线程不安全,一是多线程扩容因为头插法容易造成死循环。二是put的时候容易造成数据覆盖。

在jdk1.8中,使用尾插法避免了resize时死循环,但是put的时候,多线程环境下仍然会出现数据覆盖的问题。

接下来逐个分析问题点:

jdk1.7中扩容死循环的问题

HashMap在jdk1.7扩容时在多线程环境下会发生死循环问题,研究一下多线程环境下为什么会发生死循环,首先看一下扩容代码,扩容代码发生在put方法中:

  • public V put(K key, V value) {
  •     if (table == EMPTY_TABLE) {
  •       inflateTable(threshold);
  •     }
  •     
  •     if (key == null)
  •       return putForNullKey(value);
  •         
  •     int hash = hash(key);
  •     int i = indexFor(hash, table.length);
  •     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++;
  •     //存值
  •     addEntry(hash, key, value, i);
  •     return null;
  •   }
  • void addEntry(int hash, K key, V value, int bucketIndex) {
  •     if ((size >= threshold) && (null != table[bucketIndex])) {
  •       //扩容,将原来数组重新计算hash值,并且放到新的位置中
  •       resize(2 * table.length);
  •       hash = (null != key) ? hash(key) : 0;
  •       bucketIndex = indexFor(hash, table.length);
  •     }
  •     createEntry(hash, key, value, bucketIndex);
  • }
  • 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);
  • }

发生死循环在transfer()方法中

  • void transfer(Entry[] newTable, boolean rehash) {
  •     int newCapacity = newTable.length;
  •     for (Entry<K,V> e : table) {
  •       while(null != e) {
  • //1.将链表的下个节点放入新的对象next中
  •         Entry<K,V> next = e.next;
  • //2.重新计算hash值
  •         if (rehash) {
  •           e.hash = null == e.key ? 0 : hash(e.key);
  •         }
  •          //3.重新计算当前e对象的hash值,并计算存储位置
  •         int i = indexFor(e.hash, newCapacity);
  • //4.将新数组的i的位置的元素放到当前元素的后面,头插法
  •         e.next = newTable[i];
  • //5.将新数组的i位置设置为当前e
  •         newTable[i] = e;
  • //6.继续遍历next对象
  •         e = next;
  •       }
  •     }
  •   }

单线程环境下是这样扩容的:

(1) 原来的数组,假如2,4,6的hash值相同,都在old这个位置的链表上。

(2)现在新来一个元素(这个元素放在其他位置,这里就不画了),导致当前hashmap对象需要扩容。首先移动2

(3)移动4

(4) 移动6

使用头插法,将元素依次移动到新的链表位置。

在多线程环境下,发生多线程死循环的位置是当某个线程还未扩容完,另外一个线程竞争到锁,执行扩容,之后原来线程继续执行扩容时,对象的指针发生改变,导致后面的死循环。这里举一个例子,两个线程A和B,对hashmap对象进行扩容,发生死循环的过程

(1) 仍然使用上面的例子

(2)线程A竞争到锁,进行扩容

(2)当线程A执行到Entry<K,V> next = e.next;这步时,线程B竞争到了HashMap对象的锁,完成扩容。此时2已经移动到了i位置上

(3)线程A竞争到锁,继续执行没完成的任务,这里涉及到JVM的知识,我们再看一下transfer代码:

  • void transfer(Entry[] newTable, boolean rehash) {
  •     int newCapacity = newTable.length;
  •     for (Entry<K,V> e : table) {
  •       while(null != e) {
  • //1.将链表的下个节点放入新的对象next中,next为栈帧中的局部变量
  •         Entry<K,V> next = e.next;
  • //2.重新计算hash值
  •         if (rehash) {
  •           e.hash = null == e.key ? 0 : hash(e.key);
  •         }
  •          //3.重新计算当前e对象的hash值,并计算存储位置
  •         int i = indexFor(e.hash, newCapacity);
  • //4.将新数组的i的位置的元素放到当前元素的后面,头插法
  •         e.next = newTable[i];
  • //5.将新数组的i位置设置为当前e
  •         newTable[i] = e;
  • //6.继续遍历next对象
  •         e = next;
  •       }
  •     }
  •   }

有两个重点需要了解一下:

  • JVM虚拟机中,包含虚拟机栈,为私有,栈中包含栈帧,每增一个栈帧都代表执行一次方法。堆中包含对象,是公共的,栈帧中局部变量的指针指向堆中对象。因此在线程A中,已经执行过

Entry<K,V> next = e.next,next是局部变量,为线程A私有,因此next值不变,为4。

  • transfer方法的for循环遍历,每个e变量都是指向table的某个位置,当前e的指针已经被线程B改变,改成了指向4的位置。因此e等于4
  • void transfer(Entry[] newTable, boolean rehash) {
  •     ···
  •     for (Entry<K,V> e : table) {
  •       ···
  •     }
  • //上面的for循环等价于
  • for(int j = 0; j < table.size(); j++){
  • Entry<K,V> e = table[j];//e指向table[j]的某个位置
  • }
  •   }

接着说线程A的扩容,由于next和e都指向4,因此在while循环中,e的位置已经由old变为了i位置

(4)后面无论是线程A还是线程B扩容,e的指针都已经发生改变,执行这段代码的时候,next永远不为空,会循环放2和4,产生死循环

  • e.next = newTable[i];
  • //5.将新数组的i位置设置为当前e
  • newTable[i] = e;

(5)发生死循环

HashMap在jdk1.7中多线程会发生死循环的原因分析完成了。jdk1.8中HashMap去除了transfer方法,优化了链表插入方式,改为尾插法,避免了死循环。

put值覆盖的问题

jdk1.8中,HashMap在扩容的时候使用尾插法避免了死循环问题,但是put值覆盖的问题没有解决,接下来分析一下put为什么会造成值覆盖的问题。

原因resize扩容一样,当线程A执行完"if ((p = tab[i = (n - 1) & hash]) == null)"之后被线程B抢占资源继续执行,比如线程A定义的i=10,之后线程B执行完之后,i=10的位置已经有数据了,那么线程A继续执行的时候会将i=10的位置的数据覆盖,造成不安全的问题。接下来用代码演示一下put方法值覆盖的现象:

代码:

  • public class HashMapThreadDemo {
  • static HashMap<Integer, String> map = new HashMap<>();//存值
  • static ThreadLocal<Integer> count = new ThreadLocal<>();//计数器
  • static CountDownLatch countDownLatch = new CountDownLatch(2);//等待两个线程执行完主线程再继续执行
  • static Integer i = 0;//作为key自增
  • public static void main(String[] args) throws InterruptedException {
  • Thread t1 = new Thread(new HashMapThread(), "线程A");
  • Thread t2 = new Thread(new HashMapThread(), "线程B");
  • t1.start();
  • t2.start();
  • countDownLatch.await();
  • System.out.println("执行完成!map:" + map);
  • }
  • static class HashMapThread extends Thread {
  • @Override
  • public void run() {
  • if (count.get() == null) {
  • count.set(0);
  • }
  • //本地运行50次
  • while (count.get() < 50) {
  • String value = Thread.currentThread().getName() + "_" + i;
  • map.put(i, value);
  • System.out.println(Thread.currentThread().getName() + " key:" + i + " value:" + value + " 次数count:" + count.get());
  • count.set(count.get() + 1);
  • i++;
  • }
  • countDownLatch.countDown();
  • }
  • }
  • }

结果:

HashMap线程不安全的问题分析完成了。如果不太了解JVM里面的具体逻辑的话,直接看代码可能会云里雾里,不太了解JVM虚拟机的栈和堆各个对象存储以及运行机制的话,建议先了解一下JVM变量以及对象的存储相关知识,再回头看HashMap死循环的原因会理解的更加透彻!

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门