|
jdk1.7.0_79
HashMap可以说是每个Java程序员用的最多的数据结构之一了，无处不见它的身影。关于HashMap，通常也能说出它不是线程安全的。这篇文章要提到的是在多线程并发环境下的HashMap——ConcurrentHashMap，显然它必然是线程安全的，同样我们不可避免的要讨论散列表，以及它是如何实现线程安全的，它的效率又是怎样的，因为对于映射容器还有一个Hashtable也是线程安全的但它似乎只出现在笔试、面试题里，在现实编码中它已经基本被遗弃。
关于HashMap的线程不安全，在多线程并发环境下它所带来的影响绝不仅仅是出现脏数据等数据不一致的情况，严重的是它有可能带来程序死循环，这可能有点不可思议，但确实在不久前的项目里同事有遇到了CPU100%满负荷运行，分析结果是在多线程环境下HashMap导致程序死循环。对于Hashtable，查看其源码可知，Hashtable保证线程安全的方式就是利用synchronized关键字，这样会导致效率低下，但对于ConcurrentHashMap则采用了不同的线程安全保证方式——分段锁。它不像Hashtable那样将整个table锁住而是将数组元素分段加锁，如果线程1访问的元素在分段segment1，而线程2访问的元素在分段segment2，则它们互不影响可以同时进行操作。如果合理的进行分段就是其关键问题。
ConcurrentHashMap和HashMap的结果基本一致，同样也是Entry作为存放数据的对象，另外一个就是上面提到的分段锁——Segment。它继承自ReentrantLock（关于ReentrantLock，可参考《5.Lock接口及其实现ReentrantLock》），故它具有ReentrantLock一切特性——可重入，独占等。
ConcurrentHashMap的结构图如下所示：
可以看到相比较于HashMap，ConcurrentHashMap在Entry数组之上是Segment，这个就是我们上面提到的分段锁，合理的确定分段数就能更好的提高并发效率，我们来看ConcurrentHashMap是如何确定分段数的。
ConcurrentHashMap的初始化时通过其构造函数public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)完成的，若在不指定各参数的情况下，初始容量initialCapacity=DAFAULT_INITIAL_CAPACITY=16,负载因子loadFactor=DEFAULT_LOAD_FACTOR=0.75f,并发等级concurrencyLevel=DEFAULT_CONCURRENCY_LEVEL=16,前两者和HashMap相同。至于负载因子表示一个散列表的空间的使用程度，initialCapacity(总容量) * loadFactor(负载因子) = 数据量，有此公式可知，若负载因子越大，则散列表的装填程度越高，也就是能容纳更多的元素，但这样元素就多，链表就大，此时索引效率就会降低。若负载因子越小，则相反，索引效率就会高，换来的代价就是浪费的空间越多。并发等级它表示估计最多有多少个线程来共同修改这个Map，稍后可以看到它和segment数组相关，segment数组的长度就是通过concurrencyLevel计算得出。
//以默认参数为例initalCapacity=16，loadFactor=0.75，concurrencyLevel=16
public ConcurrentHashMap(int initalCapacity, float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
int sshift = 0;
int ssize = 1;//segment数组长度
while (ssize < concurrencyLevel) {
++sshift;
ssize <= 1;
}//经过ssize左移4位后，ssize=16,ssift=4
/*segmentShift用于参与散列运算的位数，segmentMask是散列运算的掩码，这里有关的散列函数运算和HashMap有类似之处*/
this.segmentShift = 32 – ssift;//段偏移量segmentShift=28
this.segmentMask = ssize – 1;//段掩码segmentMask=15（1111）
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;//c = 1
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;//MIN_SEGMENT_TABLE_CAPACITY=2
while (cap < c)//cap = 2, c = 1，false
cap <<= 1;//cap是segment里HashEntry数组的长度，最小为2
/*创建segments数组和segment[0]*/
Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[]) new HashEntry[cap]);//参数意为：负载因子=1，数据容量=(int)(2 * 0.75)=1，总容量=2，故每个Segment的HashEntry总容量为2，实际数据容量为1
Segment<K,V> ss = (Segment<K,V>[])new Segment[ssize];//segments数_ SjM7rMj!7:~&4(~9)>G
5ZWzCbj3ro> rokkR2 | 
转播
