阅读数:40 评论数:0

一、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。