(binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
//由链表转换成红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//使用cas统计数量增加1,同时判断是否满足扩容需求,进行扩容
addCount(1L, binCount);
return null;
}
在代码上写注释可能看得不是很清晰,那么我就使用文字再来描述一下插入数据的整个流程:
1、判断传进来的key和value是否为空,在ConcurrentHashMap中key和value都不允许为空,然而在HashMap中是可以为key和val都可以为空,这一点值得注意一下;
2、对key进行重hash计算,获得hash值;
3、如果当前的数组为空,说明这是第一插入数据,则会对table进行初始化;
4、插入数据,这里分为3中情况:
1)、插入位置为空,直接将数据放入table的第一个位置中;
2)、插入位置不为空,并且改为是一个ForwardingNode节点,说明该位置上的链表或红黑树正在进行扩容,然后让当前线程加进去并发扩容,提高效率;
3)、插入位置不为空,也不是ForwardingNode节点,若为链表则从第一节点开始组个往下遍历,如果有key的hashCode相等并且值也相等,那么就将该节点的数据替换掉,
否则将数据加入 到链表末段;若为红黑树,则按红黑树的规则放进相应的位置;
5、数据插入成功后,判断当前位置上的节点的数量,如果节点数据大于转换红黑树阈值(默认为8),则将链表转换成红黑树,提高get操作的速度;
6、数据量+1,并判断当前table是否需要扩容;
所以,put操作流程可以简单的概括为上面的六个步骤,其中一些具体的操作会在下面进行详细的说明,不过,值得注意的是:
1、ConcurrentHashMap不可以存储key或value为null的数据,有别于HashMap;
2、ConcurrentHashMap使用了懒加载的方式初始化数据,把table的初始化放在第一次put数据的时候,而不是在new的时候;
3、扩容时是支持并发扩容,这将有助于减少扩容的时间,因为每次扩容都需要对每个节点进行重hash,从一个table转移到新的table中,这个过程会耗费大量的时间和cpu资源。
4、插入数据操作锁住的是表头,这是并发效率高于jdk1.7的地方;
4.1、hash计算的spread方法
/**
* Spreads (XORs) higher bits of hash to lower and also forces top
* bit to 0. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
从源码中可以看到,jdk1.8计算hash的方法是先获取到key的hashCode,然后对hashCode进行高16位和低16位异或运算,然后再与 0x7fffffff 进行与运算。高低位异或运算可以保证haahCode的每一位都可以参与运算,从而使运算的结果更加均匀的分布在不同的区域,在计算table位置时可以减少冲突,提高效率,我们知道Map在put操作时大部分性能都耗费在解决hash冲突上面。得出运算结果后再和 0x7fffffff 与运算,其目的是保证每次运算结果都是一个正数。对于java位运算不了解的同学,建议百度自行了解相关内容。
4.2、java内存模型和cas操作
这里我只是简单的说一下java的内存模型和cas,因为这篇文章的主角的ConcurrentHashMap。
java内存模型:在java中线程之间的通讯是通过共享内存(即我们在变成时声明的成员变量或叫全局变量)的来实现的。Java内存模型中规定了所有的变量都存储在主内存中,每条线程还有自己的工作内存(可以与前面将的处理器的高速缓存类比),线程的工作内存中保存了该线程使用到的变量到主内存副本拷贝,线程对变量的所有操作(读取、赋值)都必须在工作内存中进行,而不能直接读写主内存中的变量。不同线程之间无法直接访问对方工作内存中的变量,线程间变量值的传递均需要在主内存来完成,线程、主内存和工作内存的交互关系如下图所示,和上图很类似。
举一个非常简单的例子,就是我们常用的i++的操作,这个操作看起来只有一行,然而在编译器中这一行代码会被编译成3条指令,分别是读取、更新和写入,所以i++并不是一个原子操作,在多线程环境中是有问题了。其原因在于(我们假设当前 i 的值为1)当一条线程向主内存中读取数据时,还没来得及把更新后的值刷新到主内存中,另一个线程就已经开始向主内存中读取了数据,而此时内存中的值仍然为1,两个线程执行+1操作后得到的结果都为2,然后将结果刷新到主内存中,整个i++操作结果,最终得到的结果为2,但是我们预想的结果应该是3,这就出现了线程安全的问题了。
cas: cas的全名称是Compare And Swap 即比较交换。cas算法在不需要加锁的情况也可以保证多线程安全。核心思想是: cas中有三个变量,要更新的变量V,预期值E和新值N,首先先读取V的值,然后进行相关的操作,操作完成后再向主存中读取一次取值为E,当且仅当V == E时才将N赋值给V,否则再走一遍上诉的流程,直至更新成功为止。就拿上面的i++的操作来做说明,假设当前i=1,两个线程同时对i进行+1