首页 > 其他分享 >HashMap线程不安全实例(jdk8)

HashMap线程不安全实例(jdk8)

时间:2024-03-11 19:55:22浏览次数:31  
标签:HashMap 元素 next 链表 jdk8 线程 数组 null

一、前言

本文紧接:HashMap线程不安全实例(jdk1.7) - seeAll - 博客园 (cnblogs.com),介绍jdk8中线程不安全的一些情况,且主要是在上篇文章的基础上和jdk1.7做一个对比。

 

二、初始化桶数组的例子

1,测试代码

和上篇文章一样。

2,断点设置

同样设置在初始化桶数组的地方,且断点的详细配置也和上篇文章一样,如下图

3,测试步骤

和上篇文章一样。

线程0和线程1都走到断点处;

线程0完成初始化动作,初始化了桶数组,并在数组中插入了第一个元素;

线程1在此之之后进行初始化动作。

4,结果分析

并没有出现,线程1的操作覆盖线程0的情况。

jdk1.7有这种情况,是因为初始化的方法,直接new一个新的空数组对象,赋值给了HashMap的桶数组,如下图所示

 jdk8中没有这种情况,是因为初始化的方法中,虽然也是直接new一个新的空数组对象,赋值给了HashMap的桶数组,但是先前却持有了HashMap老数组的对象。这样其他线程的操作情况,都能通过这个老数组得知,并作出反应,避免了相互覆盖的情况,如下图

5,其他线程不安全情况

5.1,桶位插入第一个元素的情况

HashMap的桶数组的某个桶位插入第一个元素的时候,直接在桶位上new一个链表,和jdk1.7中初始化桶数组的情况类似,不管其他线程在该桶位上插入了多少元素了,当前线程只要停在此处并步进一步就会初始化该桶位上的链表。

5.2,桶位链表尾部链接新元素的情况

HashMap的桶数组的某个桶位链表链接新元素时,先循环链表以找到尾部元素,当两个线程同时找到尾部元素时,同时为其链接下个元素,会发生互相覆盖的问题。

 6,其他说明

a,HashMap中元素的hash值和桶数组下标(桶位)的算法,在jdk1.7和jdk8中不同;所以如果要构造相同桶位的key,需要分别设计;比如在jdk1.7中,容量为16,key=1、16、35、50的元素会落在一个桶位;在jdk8中,相同的容量,key=1、17、33、49的元素会落在一个桶位。

b,HashMap中链表的元素插入方式,在jdk1.7和jdk8中不同;在jdk1.7中,使用“头插法”,即新元素放在链表的最前面;在jdk8中,新元素放在链表的最后面,且在链表长度即将超过8时,且桶数组长度大于等于64时,转化为红黑树,树也会在扩容时因为元素数量小于等于6而又变成链表。

 

三、链表成环的例子

1,回忆jdk1.7的情况

a,在jdk1.7中,触发扩容后,之前某个桶位上的链表,比如"月“->"秋“->"花“->"春“->null,所有元素会按照前后顺序一个一个操作,转移到自己对应的新桶位上。

b,比如其中“秋”和“春”会转移到同一个新桶位,新桶位已有的链表为“大”->"梦“->null。

c,查看下图红框中的代码,会发现转移元素的时候,也是使用的头插法,即先是“秋”接上“大”->"梦“->null变成“秋”->“大”->"梦“->null,然后赋值给新桶位,即新桶位当前的链表是“秋”->“大”->"梦“->null。然后“春”接上“秋”->“大”->"梦“->null变成“春”->“秋”->“大”->"梦“->null,再赋值给新桶位,最终新桶位当前的链表是“春”->“秋”->“大”->"梦“->null。

d,参考上篇文章,一个线程在转移元素的时候还是秋在前,春在后;另一个线程已经都转移好了,变成了春在前,秋在后;再回到最开始的线程,此时的情形已经和它固有的设计背道而驰了。

打个比方,完成上篇文章中未完成的游戏

前言:

人1、人2、人3分别代表栈里面的e、next、newTable[i];

道具“秋”、道具“春”,道具“大”,道具“梦”,道具null分别代表堆里面的待转移的或者已在链表中的元素对象;

“秋”前面的钩子钩在了“春”后面的环上,“秋”->“春”;

“大”前面的钩子钩在了“梦”后面的环上,“大”->“梦”;“梦”前面的钩子钩在了“null”后面的环上,“梦”->null;即“大”->"梦“->null;

人1抓着“秋”;

开始游戏:

a1,人2看下人1手上的“秋”,顺着看下去,“秋”勾着“春”,所以人2抓住这个“春”;

此时局外人人4解开了秋的钩子,反而把“春”前面的钩子钩在了“秋”后面的环上,“春”->“秋”;

a2,人1将自己手上“秋”的钩子解开(此时已经被人4解开了),勾到了人3抓着的“大”上面;

a3,人3松开手,抓住人1手上的“秋”;

a4,人1松开手,抓住人2手上的“春”;

 

b1,人2看下人1手上的“春”,顺着看下去,“春”勾着“秋”,所以人2抓住这个“秋”;

b2,人1将自己手上“春”的钩子解开,勾到了人3抓着的“秋”上面;

b3,人3松开手,抓住人1手上的“春”;

b4,人1松开手,抓住人2手上的“秋”;

 

c1,人2看下人1手上的“秋”,顺着看下去,“秋”勾着“大”,所以人2抓住这个“大”;

c2,人1将自己手上“秋”的钩子解开,勾到了人3抓着的“春”上面;问题来了,“春”勾着“秋”,现在“秋”又勾着“春”,不就形成环了吗。

2,jdk8的情况

2.1,插入元素的情况

新元素找到对应桶位后,先遍历桶位上的链表,直到找到尾部元素,最后才会将新元素挂到“链表尾部元素”的后面,如下图;和jdk1.7的头插法相比多了“循环遍历找尾部元素”的步骤。

 2,扩容转移元素的情况

示例代码

public class MyNode {
    public int key;
    public String value;
    public MyNode next;

    public MyNode(int key, String value, MyNode next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public static void main(String[] args) {
        // “花” -> “春” -> null
        MyNode e = new MyNode(1, "花", new MyNode(17, "春", null));
        // 假设原数组长度为8
        int oldCap = 8;
        // 假设链表在原数组下标为1的位置
        int oldIndex = 1;
        // 假设扩容后,新数组长度16
        MyNode[] newTab = new MyNode[16];

        MyNode loHead = null, loTail = null;
        MyNode hiHead = null, hiTail = null;
        MyNode next;
        do {
            next = e.next;
            // 扩容后,链表上某些元素所在数组下标位置不变,还在1
            if ((hash(e.key) & oldCap) == 0) {
                if (loTail == null)
                    // 如果尾部指针还没有指向元素,说明该元素e是第一个元素(头部元素)
                    loHead = e;
                else
                    // 如果尾部指针已经指向了元素,说明该元素e不是第一个元素,需要挂到尾部指针指向的元素
                    loTail.next = e;
                // 将尾部指针指向当前元素,表示当前元素现在是链表上的最后一个元素
                loTail = e;
            } else {
                // 扩容后,链表上某些元素需要转移到数组另外的位置上,HashMap通过巧妙的设计,需要改变位置的只会转移到同一个位置(1+8=)9
                if (hiTail == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
            }
        } while ((e = next) != null);
        if (loTail != null) {
            // 链表的最后一个元素后挂上null,到此链表完整形成
            loTail.next = null;
            // 处理转移后位置不变的元素,桶位指向他们形成的链表的头部元素
            newTab[oldIndex] = loHead;
        }
        if (hiTail != null) {
            hiTail.next = null;
            // 处理转移后位置改变的元素,新桶位指向他们形成的链表的头部元素
            newTab[oldIndex + oldCap] = hiHead;
        }

        System.out.println(Arrays.asList(newTab));
    }

    // 直接copy的源码,为jdk1.8中hashMap计算hash值的方法
    public static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    @Override
    public String toString() {
        return "MyNode{" +
                "key=" + key +
                ", value='" + value + '\'' +
                ", next=" + next +
                '}';
    }
}

运行结果

 结果分析

使用固定”头部指针“,移动”尾部指针“的方式,实现正序;

假如使用固定”尾部指针“,移动”头部指针“的方式,也能实现倒序,改成下面代码替换进去;

                if (loHead == null)
                    loTail = e;
                else
                    e.next = loHead;
                loHead = e;

之所以使用正序,先来的元素在前面,后来的元素在后面,和HashMap中put元素采用尾插法一样,应该是有原因的。可能是为了整体的一致性,防止出现jdk1.7中那种问题吧。

 

四、总结

1,

  jdk1.7中,初始化桶数组时,会发生线程安全问题,两个线程同时走到初始化动作那一行,不管谁快谁慢,最终总有一方覆盖另一方;

  jdk8中,初始化桶数组时,不会发生线程安全问题,不管谁,都会在初始化完后,继续将对方的操作结果与自己的操作结果进行融合。

2,

  jdk8中,桶位链表初始化第一个元素时,会发生线程安全问题,原理同上jdk1.7初始化桶数组一样,两个线程走到初始化动作那一行,不管谁快谁慢,最终总有一方覆盖另一方;

3,

  jdk1.7中,链表头插新元素时,会发生线程安全问题,因为桶位原先指向链表的头部对象,插入新元素后需要指向新元素对象,在堆里面是两个不同的对象;

  线程执行方法,对应”虚拟机栈“,栈里有个变量(不管是局部变量,还是方法参数),变量指向堆里的桶位对象,这个变量一旦指定对象后,就不会重新指向了(除非代码里,下面有将这个变量指向另一个对象,需要一行代码,再换个对象,又需要一行代码,可是代码是早就写好的,不会动态的改变),无法保证变量指向的对象接下来使用前会不会过时。

  可以理解为,在虚拟机层面,获取对象和使用对象是两个步骤,两个步骤之间一定有时间间隔,时间间隔内对象可能过时;

  jdk8使用尾插法,桶位指向的一直是一个对象,就不会存在这样的问题;但是会出现其他问题,如下面

4,

  在jdk8中,链表尾插新元素时,会发生线程安全问题,原理同上,线程执行方法对应的栈中的变量指向链表的尾部元素对象,但是这个尾部元素对象也会过时。

5,

  jdk1.7中,扩容翻转链表时,会发生线程安全问题,因为HashMap插入元素和扩容转移元素都是使用头插法,相当于一个正面朝上的硬币,插入后变成反面朝上,扩容转移后又变成正面朝上;

  两个线程同时扩容翻转链表时,一个线程正在处理正面朝上的硬币,它的思路就是按照正面朝上处理了,且已经处理了一半,中途被另一个线程把硬币变成了反面朝上,之前的线程的思路又不会转变,最终导致问题。

  jdk8使用尾插法后,一个正面朝上的硬币,插入后还是正面朝上,扩容转移后还是正面朝上,一直不会改变,也就不会出现偏差和矛盾的地方,没有循环依赖的问题。

标签:HashMap,元素,next,链表,jdk8,线程,数组,null
From: https://www.cnblogs.com/seeall/p/18065592

相关文章

  • t01_多线程
    进程与线程进程:进程是程序的基本执行实体线程:线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位在Java中,进程(Process)和线程(Thread)是两个并发执行的概念,用于实现多任务处理和并发执行。它们都是操作系统和编程语言级别的概念,用于管理和执......
  • Java高并发讲解:守护线程——在源代码中分析setDaemon()
    Java高并发讲解:守护线程——在源代码中分析setDaemon()提出问题我们都知道Java线程分为主线程和守护线程,守护线程是需要手动指定的(setDaemon(true)......
  • Spring多线程事务处理
    一、背景本文主要介绍了spring多线程事务的解决方案,心急的小伙伴可以跳过上面的理论介绍分析部分直接看最终解决方案。在我们日常的业务活动中,经常会出现大规模的修改插入操作,比如在3.0的活动赛事创建,涉及到十几张表的插入(一张表可能插入一行或者多行数据),由于单线程模型的关系,......
  • 面试官:说说线程池的工作原理?
    线程池的底层是基于线程和任务队列来实现的,创建线程池的创建方式通常有以下两种:普通Java项目,使用ThreadPoolExecutor来创建线程池,这点《阿里巴巴Java开发手册》中也有说明,如下图所示:Spring项目中,会使用代码可读性更高的ThreadPoolTaskExecutor来创建线程池,虽然它的......
  • Java多线程基础用法
    线程创建线程创建的三种方式:Thread(继承Thread类)自定义线程类继承Thread类重写run()方法。编写线程执行体创建线程对象,调用start()方法启动线程packagecom.lily.demo01;publicclassTestThreadextendsThread{@Overridepublicvoidrun(){for......
  • QT 多线程
     第一种:静态函数1voidprint()2{3for(inti=0;i<5;i++)4qInfo()<<"helloglobalprint";5}6classMainWindow:publicQWidget7{8Q_OBJECT9public:10MainWindow(QWidget*parent=nullptr):QWidget(parent)......
  • Intel Lunar Lake失去超线程!但多核性能飙升1.5倍
    Intel将在今年晚些时候推出ArrowLake、LunarLake两套平台,工艺、架构基本相同,分别面向高性能和低功耗,一个意外变化就是不支持超线程。尽管如此,大家也不必为多核性能担忧。据最新曝料,17W功耗的LunarLake对比15W功耗的MeteorLake-U,CineBench23/5.4.5测试中,多核性能可提升几乎......
  • 线程池的使用场景
    在实际开发中,线程池用于优化线程的使用,提高系统性能,减少线程创建和销毁的开销,以及提供更高的系统稳定性。下面将详细解析几个常见的线程池使用场景,并结合源码和代码演示进行说明。场景一:Web应用的并发请求处理Web应用通常需要同时处理多个用户的请求。为了不每个请求都创建一......
  • 进程与线程
    进程与线程:进程:进程是操作系统资源分配的单位,其中存放dll,代码,堆,栈线程:调度单位多线程优点:1.提高响应能力:GUI程序,主线程操作UI,耗时操作放在工作线程中2.提高程序性能线程有哪些开销:空间上:1.数据结构上C#:Thread类......
  • 深入浅出Java多线程(十):CAS
    引言大家好,我是你们的老伙计秀才!今天带来的是[深入浅出Java多线程]系列的第十篇内容:CAS。大家觉得有用请点赞,喜欢请关注!秀才在此谢过大家了!!!在多线程编程中,对共享资源的安全访问和同步控制是至关重要的。传统的锁机制,如synchronized关键字和ReentrantLock等,能够有效防止多个线程......