集合之HashMap 复盘:

个人印象笔记地址https://app.yinxiang.com/fx/59e1a3a1-dde0-4e78-8908-ea0200edccf0
 

阅读源码:

1.默认数组是16,但是可以自己指定。 预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的,
eg:
11-->16
17-->32

 

2.HashMap的扩容机制:
触发条件:hashmap中的元素个数超过数组大小*loadFactor加载因子
eg:16*0.75=12 ---->重新扩大一倍为32
然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作

 

3.jdk7中:HashMap线程不安全的原因

  1.高并发的情况下,HashMap的resize扩容操作会导致线程不安全(死锁,cpu使用率达到100%)
  2.还会有数据丢失的情况(扩容的原理是再新申请一个比旧数组*2的新数组,高并发多线程环境下可能出现jvm内存溢出,触发大量GC)

4,扩容死锁的原因:(Java7)

简单的说就是扩容后,链表可能会成环,(两个指针e,next()) Hashmap多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。
 

java8的优化:用了四个指针指向

 

5.concurentHashMap是怎么做到线程安全?

阅读源码可知,
concurentHashMap不允许key和value 为空。
 
HashMap对象的key、value值均可为null。
HahTable对象的key、value值均不可为null。且两者的的key值均不能重复,若添加key相同的键值对,后面的value会自动覆盖前面的value,但不会报错。
 

 

6.Java7 和Java 8中,concurenthashmap的区别

 
 

1.7中的原理和实现

   1.7中采用的是数组+单向链表的结构,ConcurrentHashMap将数据分别放到多个Segment中,默认16个,每一个Segment中又包含了多个HashEntry列表数组
需要注意的是 Segment 是一种可重入锁(继承ReentrantLock)
 
 
 

 

1.7的扩容操作

Segment 不扩容(默认l6个 不变),扩容下面的table数组(初始化时为2),每次都是默认将数组翻倍

1.8中的原理和实现

1、原理

 
   1.8中是采用数组+链表+红黑树的结构, 对于链表个数小于等于默认值8的链表使用单向链接,而个数超对默认值的时候将链表转换为红黑树,查询时间复杂度优化到了O(logN)【二分查找】,O(logN)即二叉树的深度
放弃了segment分段式锁链表,并发控制使用SynchronizedCAS来操作
加锁的位置,在每个链表的头结点或者是红黑树的根节点
 

2、put()

1.8:由于移除了Segment,类似HashMap,可以直接定位到桶,拿到first节点后进行判断,1、为空则CAS插入;2、为-1则说明在扩容,则跟着一起扩容;3、else则加锁put(类似1.7)
 

3、get()

基本类似,由于value声明为volatile,保证了修改的可见性,因此不需要加锁。

4、resize()

1.8:支持并发扩容,HashMap扩容在1.8中由头插改为尾插(为了避免死循环问题),ConcurrentHashmap也是,迁移也是从尾部开始,扩容前在桶的头部放置一个hash值为-1的节点,这样别的线程访问时就能判断是否该桶已经被其他线程处理过了

 

 

 

 

原文链接:https://blog.csdn.net/weixin_43373417/article/details/106610785

最后修改日期:2020年6月10日