HashMap并发put（）为什么会导致线程安全性问题

淩亂°似流年 2023-10-10 17:25 39阅读 0赞

1.  **HashMap put() 7 1.8**

当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash。//JDK1.7的put()过程：首先使用HashCode计算出put值属于哪个segment，并给此segment加锁；然后使用HashCode计算出put值的K-V在HashEntry数组中的索引，如果索引位置元素为空则直接插入数据；若存在数据，即发生了Hash冲突则该遍历HashEntry的链表，若key存在就直接返回\\新数据覆盖旧数据并返回旧数据，若key不存在就用头插法将HashEntry<K, V>插入索引位置的链表中。

JDK1.8的put()：也是通过HashCode定位到Node，如果Node为空就通过CAS插入数据；如果Node不为空

put方法对比

1.7是通过hashcode定位到segment，然后segment加锁；在通过hashcode定位到hashentry，然后进行添加；添加的过程中可能会碰到hash冲突的情况，采用头插法形成链表。所以底层是数组\+链表

1.8是通过hashcode定位到下标位置；如果node==null通过cas的添加；如果不为null且在扩容(node的hashcode == -1)，那么当前线程加入—起进行扩容；不为null且不在扩容，那么synchorized (node）进行添加；count++

**1.put插入方式区别**

在jdk 1.7中, hashmap调用put()方法插入时时采用的是头插法, 并且因为hashmap不是线程安全的, 所以当并发插入、并触发扩容时可能会把数组内部的链表变成循环链表, 造成死循环的问题

**//为什么造成线程安全/死循环问题**

Jdk1.7：

比如：

![faf462ac6ed046528cb738806daff8ed.png][]

线程A e=3 7=next e.next=null(用头插法 把3拿出来) 线程被挂起

线程B 扩容完成 7.next=3 3.next=null

线程A 放置好3 接下来放置7 e=7 此时7.next=3 覆盖/数据丢失

HashMap的线程不安全主要是发生在扩容函数（transfer）中，JDK1.7中HashMap的transfer函数如下:

HashMap的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点。

在jdk 1.8中, hashmap的put()方法改为了尾插法插入, 因此解决了1.7中并发扩容造成的循环链表问题, 但是实际上在往红黑树内部并发插入时也有可能会造成两个父节点相互引用而导致的死循环问题

Jdk1.8 尾插法

//并发put判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A（还没插入成功）执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

**2.HashMap扩容 resize()**

Jdk1.7:用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

总结：

Hashmap的扩容需要满足两个条件：**当前数据存储的数量（即****size()****）大小必须大于等于阈值；当前加入的数据是否发生了****hash****冲突。**

//**特点**：先扩容，再添加（扩容使用的头插法）

**缺点**：头插法会使链表发生反转，多线程环境下可能会死循环

//因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），\[在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11<12(16\*0.75)，所以在存入第12个元素的时候不会发生扩容，那么还有15个数据下标的位置是空的，后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），前面11+15=26（12+15=27评论指正，20201230日晚验证后修改为27），所以在存入第28个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

![b599d06ee62d4ff6bd23039826ef71df.png][]

//头插法

JDK7版本及以前使用是：**头插法（对比****JDK8****使用的是尾插法）**

注：使用头插法在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，到是线程执行无法结束

**头插法**：有点类似于砌墙的砖头后来居上的感觉，先插入的会被逐步放到最底下，越后来的会被放在头部，并将next指针指向之前的头部，这样在扩容的时候，先取头部然后把头部放到新对应数组下标的链表处，由于头插法，最早取的会被最先放进并逐步变成最尾，如果多线程执行扩容，将数组下标3位置链表存入的A->B->C扩容时存入到新的数组（假设扩容后A/B/C还在同一个链表上），线程1取第一个元素A被挂起的时候，挂起的元素A元素的next指向B，而线程2放入新的链表时，A被先放但没有完成，线程2在放入B后，B的next指向之前放入的A，当线程1执行的时候本身A的next指向B，这样就行程了循环引用，最后存入C，并将C的next指向B，最终就变成C->B-><-A，在get()方法执行到该数组下标时，遍历链表查找的时候就会出现死循环。

///HaspMap扩容就是就是先计算 新的hash表容量和新的容量阀值，然后初始化一个新的//hash表，将旧的键值对重新映射在新的hash表里。如果在旧的hash表里涉及到红黑树，//那么在映射到新的hash表中还涉及到红黑树的拆分。

负载因子：负载因子在初始化Map的时候被赋值，要么被用户传的参数赋值，要么被默认的0.75f给赋值；

Jdk1.8

1.  当前存储的数量大于等于阈值
2.  当某个链表长度>=8，但是数组存储的结点数size() < 64时

**特点**：先插后判断是否需要扩容（扩容时是尾插法）

**缺点**：多线程下，1.8会有数据覆盖：

**HashMap是怎么解决哈希冲突的？**

![c2ea5621bb684e59a253434498405815.png][]

[faf462ac6ed046528cb738806daff8ed.png]: https://img-blog.csdnimg.cn/faf462ac6ed046528cb738806daff8ed.png
[b599d06ee62d4ff6bd23039826ef71df.png]: https://img-blog.csdnimg.cn/b599d06ee62d4ff6bd23039826ef71df.png
[c2ea5621bb684e59a253434498405815.png]: https://img-blog.csdnimg.cn/c2ea5621bb684e59a253434498405815.png