和HashMap不同的是，ConcurrentHashMap采用分段加锁的方式保障线程安全，JDK 1.8之后，ConcurrentHashMap的底层数据结构从1.8开始跟HashMap差不多。

　　HashTable也是线程安全的，存储Key-Value键值对的数据结构，Key和Value都不能为空，但不推荐使用，因为其所有的方法采用synchronized修饰，效率低。

　　Key和Value都不能为Null的原因是：如果map.get(key)返回null，可以认为是value的值本来就是null，也可以认为map中不存在key的存储数据，因此具有二义性，但HashMap在单线程环境，可以通过map.containsKey(key)判断，消除而已性。

　　但在多线程环境中，map.get(key)和map.containsKey(key)是非原子的操作，可能在线程A的两个语句运行之间，其他线程B运行map.put(key,value)，导致线程A无法消除上面的二义性。

　　下图是ConcurrentHashMap的UML关系图。

　　image-20200809215755661

　　1、底层存储结构

　　1.1、JDK 1.7的存储结构，了解即可

　　在JDK 1.7，ConcurrentHashMap通过对Segment的分段加锁实现线程安全。一个Segment里面就是HashMap的存储结构，可以扩容。Segment的数据量初始化以后不可以更改，默认值16，因此默认支持16个线程同时操作ConcurrentHashMap。

　　img

　　1.2 JDK 1.8的存储结构

　　JDK 1.8之后，存储结构变化比较大，跟HashMap类似。红黑树节点小于某个数(默认值6)又会转换为链表。

　　image-20200809221531416

　　[]ConcurrentHashMap的主要成员变量，类似HashMap，补上注释

　　2、ConcurrentHashMap的构造方法

　　ConcurrentHashMap的默认构造容量为16，在初始化的时候并不会初始化table数组。同HashMap一样，在put第一个元素的时候才会initTable()初始化数组。

　　/**Creates a new,empty map with the default initial table size(16).*/

　　public ConcurrentHashMap(){

　　}

　　//设置初始化大小的构造函数

　　public ConcurrentHashMap(int initialCapacity){

　　this(initialCapacity,LOAD_FACTOR,1);

　　}

　　//根据传入的map初始化

　　public ConcurrentHashMap(Map<?extends K,?extends V>m){

　　this.sizeCtl=DEFAULT_CAPACITY;

　　putAll(m);

　　}

　　//设置初始容量和加载因子的大小

　　public ConcurrentHashMap(int initialCapacity,float loadFactor){

　　this(initialCapacity,loadFactor,1);

　　}

　　//初始容量、加载因子、并发级别

　　public ConcurrentHashMap(int initialCapacity,

　　float loadFactor,int concurrencyLevel){

　　//数据校验

　　if(!(loadFactor>0.0f)||initialCapacity<0||concurrencyLevel<=0)

　　throw new IllegalArgumentException();

　　//如果初始容量小于并发级别

　　if(initialCapacity<concurrencyLevel)//Use at least as many bins

　　initialCapacity=concurrencyLevel;//as estimated threads

　　//一些比较

　　long size=(long)(1.0+(long)initialCapacity/loadFactor);

　　int cap=(size>=(long)MAXIMUM_CAPACITY)?

　　MAXIMUM_CAPACITY:tableSizeFor((int)size);

　　this.sizeCtl=cap;

　　}

　　3、get、put方法

　　3.1 get方法，根据key找value，没有返回null

　　get的流程总体和HashMap差不多，只不过是通过头结点的hash值判断是红黑树还是链表。

　　static final int MOVED=-1;//转发节点？TODO作用？

　　static final int TREEBIN=-2;//跟节点

　　static final int RESERVED=-3;//临时保留的节点？TODO作用？

　　static final int HASH_BITS=0x7fffffff;//hash的扰动函数spread()计算用的

　　//根据key获取value值

　　public V get(Object key){

　　Node<K,V>[]tab;Node<K,V>e,p;int n,eh;K ek;

　　//计算hash值

　　int h=spread(key.hashCode());

　　//集散所在的hash桶

　　if((tab=table)!=null&&(n=tab.length)>0&&

　　(e=tabAt(tab,(n-1)&h))!=null){

　　if((eh=e.hash)==h){

　　//头结点，刚好是要找的节点

　　if((ek=e.key)==key||(ek!=null&&key.equals(ek)))

　　return e.val;

　　}

　　else if(eh<0)

　　//头结点hash值小于0，说明正在扩容或者是红黑树，find查找

　　return(p=e.find(h,key))!=null?p.val:null;

　　while((e=e.next)!=null){

　　//链表遍历查找

　　if(e.hash==h&&

　　((ek=e.key)==key||(ek!=null&&key.equals(ek))))

　　return e.val;

　　}

　　}

　　return null;

　　}

　　3.2、put方法

　　put方法的流程跟HashMap的流程差不多，不同点在于线程安全，自旋，CAS，synchronized

　　onlyIfAbsent如果为true，如果已经存在了key，不会替换旧的值。

　　public V put(K key,V value){

　　return putVal(key,value,false);

　　}

　　/**Implementation for put and putIfAbsent*/

　　final V putVal(K key,V value,boolean onlyIfAbsent){

　　//key和value都不能为null

　　if(key==null||value==null)throw new NullPointerException();

　　//计算hash(key)的扰动函数

　　int hash=spread(key.hashCode());

　　//离岸边的长度

　　int binCount=0;

　　for(Node<K,V>[]tab=table;;){

　　Node<K,V>f;int n,i,fh;K fk;V fv;

　　//如果table还没有初始化，就初始化table（自旋+CAS)

　　if(tab==null||(n=tab.length)==0)

　　tab=initTable();

　　else if((f=tabAt(tab,i=(n-1)&hash))==null){

　　//如果当前hash桶为null，直接放入，CAS加入，成功了就直接break

　　if(casTabAt(tab,i,null,new Node<K,V>(hash,key,value)))

　　break;//no lock when adding to empty bin

　　}

　　//TODO:

　　else if((fh=f.hash)==MOVED)

　　tab=helpTransfer(tab,f);

　　else if(onlyIfAbsent//check first node without acquiring lock

　　&&fh==hash

　　&&((fk=f.key)==key||(fk!=null&&key.equals(fk)))

　　&&(fv=f.val)!=null)

　　return fv;

　　else{

　　//旧的值

　　V oldVal=null;

　　//加锁

　　synchronized(f){

　　if(tabAt(tab,i)==f){

　　if(fh>=0){

　　binCount=1;

　　for(Node<K,V>e=f;;++binCount){

　　K ek;

　　//如果存在hash(key)和key对应的节点，直接更改value值

　　if(e.hash==hash&&

　　((ek=e.key)==key||

　　(ek!=null&&key.equals(ek)))){

　　oldVal=e.val;

　　if(!onlyIfAbsent)

　　e.val=value;

　　break;

　　}

　　Node<K,V>pred=e;

　　if((e=e.next)==null){

　　//不存在直接放入，因为前面加锁了

　　pred.next=new Node<K,V>(hash,key,value);

　　break;

　　}

　　}

　　}

　　//如果是红黑树，红黑树插入

　　else if(f instanceof TreeBin){

　　Node<K,V>p;

　　binCount=2;

　　if((p=((TreeBin<K,V>)f).putTreeVal(hash,key,

　　value))!=null){

　　oldVal=p.val;

　　if(!onlyIfAbsent)

　　p.val=value;

　　}

　　}

　　else if(f instanceof ReservationNode)

　　throw new IllegalStateException("Recursive update");

　　}

　　}

　　if(binCount!=0){

　　//是否要转为红黑树

　　if(binCount>=TREEIFY_THRESHOLD)

　　treeifyBin(tab,i);

　　//旧的值

　　if(oldVal!=null)

　　return oldVal;

　　break;

　　}

　　}

　　}

　　addCount(1L,binCount);

　　return null;

　　}

　　4、TODO ConcurrentHashMap的扩容方法

　　ConcurrentHashMap也是默认扩容2倍，扩容的方法transfer()

　　Node<K,V>[]nt=(Node<K,V>[])new Node<?,?>[n<<1];

　　5、总结

　　ConcurrentHashMap在JDK 1.7和1.8变化很大，在JDK 1.7中，采用Segment分段存储数据，也通过Segment分段加锁。

　　而在JDK 1.8中，使用synchronized锁定hash桶的链表的首节点/红黑树的根节点，只要hash(key)不冲突，就不会影响其他线程。