ConcurrentHashMap

与HashMap、SynchronizedMap的差别

1.HashMap线程不安全
2.ConcurrentHashMap在JDK1.7中是以锁segment的方式保证并发,在JDK1.8中是以CAS和synchronized的方式保证并发
3.SynchronizedMap的put和get封装了HashMap相关方法,并通过互斥锁保证线程安全
4.ConcurrentHashMap做put时,用CAS+Synchronized保证线程安全,更轻量

JDK1.7的实现方式

1.segment数组 -> HashEntry数组 -> HashEntry列表
2.读取时不加锁,写入时锁segment
3.两次hash,一次定位到segment,一次定位到HashEntry头部

JDK1.8的实现方式

1.以node数组加列表或红黑树的方式实现
2.冲突会产生链表,链表数大于8会以红黑树方式存储
3.遍历链表的时间复杂度是O(n),遍历红黑树的时间复杂度是O(logN),利于冲突数大的场景

Node对象

1.val与next都会在扩容时发生变化,所以使用了volatile来保持可见性和禁止重排序
2.用next指向下一个Node,以处理冲突

JDK1.8中put的实现细节(含CAS原理)

1.如果Node数组为空,则调用initTable方法初始化Node数组
2.如果Node位置为空,即无冲突,则以CAS方式插入
3.如果Node位置不为空,表示已存在冲突,则对Node加synchronized锁,并加入到Node所指向的链表中
4.如果Node中包含的链表节点数大于8,则调用treeifyBin方法将链表转为红黑树
5.如果Node已经使用红黑树存储数据,则通过putTreeVal方法插入新的键值对
6.多个线程尝试使用CAS同时更新同一变量时,只有其中一个线程能更新变量的值,而其他线程都会失败,失败的线程并不会被挂起,而是被告知此次竞争失败,并可以再次尝试

CAS

1.Compare And Swap, CAS有三个参, 分别是V, E, N (CAS(V, E, N)),如果V等于E,则将V设为N;如果V和E不相同,说明已有其他线程做了更新,当前线程什么都不做或更改V,E和N的参数再重试
2.put中的casTabAt方法,实际调用了compareAndSwapObject方法来实现的
3.比较当前tab中的i索引是否为null,是则插入Node<K, V>,不是则说明有其他线程已更改,不做操作

JDK1.8中get的实现细节

计算key的hash值,如果Node数组中匹配到首结点即返回,否则调用next方法遍历链表或红黑树,由于可能会存在冲突,需要调用equals方法进行判断

volatile实例

1.容纳Node的数组和表示长度的变量都是volatile修饰的,设计动机: 多个线程并发操作,一个线程更改完成后,通过volatile保证线程间的可见,其他线程能够立刻感知到当前线程的更改