HashMap ConcurrentHashMap 以及JDK8的优化

阅读数:98 评论数:0

跳转到新版页面

分类

python/Java

正文

一、HashMap

HashMap使用链表法避免哈希冲突(相同hash值),当链表长度大于TREEIFY_THRESHOLD(默认为8)时,将链表转换为红黑树。当小于等于UNTREEIFY_THRESHOLD(默认为6)时,又会退化回链表以达到性能均衡。

1、HashMap在并发时出现的问题

(1)多线程put的时候可能导致元素丢失

主要问题出在addEntry方法的new Entry (hash, key, value, e),如果两个线程都同时取得了e,则他们下一个元素都是e,然后赋值给table元素的时候有一个成功有一个丢失。

(2)多线程put后可能导致get死循环

造成死循环的原因是多线程进行put操作时,触发了HashMap的扩容(resize函数),出现链表的两个结点形成闭环,导致死循环。

2、jdk8中HashMap的优化

(1)长链表的优化

在JDK8中,如果链表的长度大于等于8 ,那么链表将转化为红黑树;当长度小于等于6时,又会变成一个链表

(2)hash碰撞的插入方式的优化

发生hash碰撞时,JDK7会在链表头部插入,而JDK8会在链表尾部插入。如果变成红黑树,也不可能做头插法了

(3)扩容机制的优化

简单的说,就是减少了扩容后移动的数据量。

二、ConcurrentHashMap

1、特点

由于HashMap在并发中会出现一些问题,所以JDK中提供了并发容器ConcurrentHashMap。

2、JDK8 的优化

从JDK7版本的ReentrantLock+Segment+HashEntry,到JDK8版本中synchronized+CAS+HashEntry+红黑树。

(1)线程安全机制

JDK7采用segment的分段锁机制实现线程安全,其中segment继承自ReentrantLock。JDK8采用CAS(读)+Synchronized(写)保证线程安全。

(2)锁的粒度

原来是对需要进行数据操作的Segment加锁,JDK8调整为对每个数组元素加锁(Node)。

(3)链表㔹化为红黑树

定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。

(4)查询是间复杂度

从原来的遍历链表O(n),变成遍历红黑树O(logN)。

(5)JDK8推荐使用mappingCount方法而不是size方法获取当前map表的大小,因为这个方法的返回值是long类型,size方法是返回值类型是int。




相关推荐

一、Collection接口 Collection接口的iterator和toArray方法都用于获得集合中的“所有元素”。前者返回一个“iterator”对象,后者返回一个包含集合中所有元素的数组。

一、概述 1、序列化的作用 个人理解它的主要作用是为了对象可以跨平台存储和进行网络传输,在网络传输的时候,我们需要经过 IO,而 IO 传输支持的就是字节数组这种格式,所以序列化过后可以更好的传输。

一、Base64 Base64是一种基于64(8Bit)个可打印字符来表示二进制数据的方法。 索引 对应字符 索引 对应字符 索引 对应字符 索引 对应字符