HashMap

Put方法流程

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

链表长度大于等于8并且数组长度大于64才会转化为红黑树，否则会首先进行数组克隆

HashMap扩容流程

HashMap的寻址算法

HashMap在1.7版本下的死循环问题

ConcurrentHashMap

ConcurrentHashMap是一种线程安全的高效Map集合

底层数据结构：

• JDK1.7底层采用分段的数组+链表实现
• JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树

1.7版本

有默认16个segment数组，当进行put操作时，会根据hash运算查找是哪个segment数组，然后会获取ReentrantLock，当获取到锁时，再通过hash值定位hashEntry数组下标，然后插入

1.8版本的

放弃了Segment臃肿的设计，数据结构跟hashMap的数据结构是一样的：数组+链表/红黑树，采用CAS+Synchronized来保证并发安全进行实现

• CAS控制数组节点的添加(谁能用CAS添加成功了就成功了)
• Synchronized只锁定当前链表或红黑树树的首节点，只要hash不冲突，就不会产生并发的问题，效率的到提升

总结