HashMap在并发时不是线程安全的，当多个线程对map进行扩容会导致链表成环。不单单是这个问题，当多个线程向同一个槽中插入数据，也不是线程安全的。
接下来分析一下ConcurrentHashMap的put方法
1.检验 key value值是否为null，为null直接抛出异常，hash map是允许null的存在的
2.得到key的hash值
3.死循环并更新tab变量的值。
4.如果容器没有初始化，则初始化，调用initTable方法，该方法是通过一个调用unself中的CAS来控制并发
5.根据hash值来找到数组的下标，如果对应的位置为空，就创建一个Node对象用CAS方式添加到容器，并跳出循环
6.如果hash冲突了，即对应的位置不为null，则判断该槽是否被扩容了(-1表示被扩容了)，如果被扩容了，则返回新的数组
7.如果 hash 冲突 且 hash 值不是 -1，表示没有被扩容。则进行链表操作或者红黑树操作，注意，这里的 f 头节点被锁住了，保证了同时只有一个线程修改链表。防止出现链表成环。
8.和 HashMap 一样，如果链表树超过8，则修改链表为红黑树。
9.将数组加1（CAS方式），如果需要扩容，则调用 transfer 方法（非常复杂，以后再详解）进行移动和重新散列，该方法中，如果是槽中只有单个节点，则使用CAS直接插入，如果不是，则使用 synchronized 进行同步，防止并发成环。
initTable 方法
该方法为了在并发环境下的安全，加入了一个 sizeCtl 变量来进行判断，只有当一个线程通过CAS修改该变量成功后（默认为0，改成 -1），该线程才能初始化数组。保证了初始化数组时的安全性。
hash算法的原由
Hash算法就是通过一种运算将Key值映射为Int型的hashcode，之后再对hashcode进行高位运算（1.8New），取模运算，将其映射成一个小于Map数组大小的int值之后将键值对存入对应的数组位置。为什么要这么做呢？当HashMap中的数据数量较小时，经过计算可以使得键值对较为均匀的存入数组的不同位置，尽量不生成链表。链表的时间复杂度为O（n），数组的时间复杂度是O（1），所以为了提高HashMap的效率，在数据量较小的时候尽可能的不生成链表。这也可以用来解释为什么在链表长度过长的时候使用红黑树代替链表，红黑树的时间复杂度为O（log2(n)），在数据量较大时远远小于链表。
hash算法
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
ConcurrentHashMap的重要变量
//Map对应的Hash桶数组
transient volatile Node<K,V>[] table;
//扩容时候新建的Hash桶数组，注意transient关键字，该字段不会被序列化
private transient volatile Node<K,V>[] nextTable;
//用于节点计数
private transient volatile long baseCount;
//非常非常非常重要的一个参数，统御全局
//sizeCtl = -1，表示有线程正在进行初始化操作，防止多线程同时初始化Map
//sizeCtl = -(1 + nThreads)，表示有nThreads个线程正在进行扩容操作
//sizeCtl > 0，表示接下来的初始化操作中的Map容量，或者表示初始化/扩容完成后的阈值
//sizeCtl = 0，默认值
private transient volatile int sizeCtl;
//用以维护多线程扩容时候的线程安全
private transient volatile int transferIndex;
锁的方式
部分锁定+CAS算法来进行实现线程安全的。CAS算法也可以认为是乐观锁的一种,其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
网友评论