参考java并发编程的艺术一书中,对ConcurrentHashMap的讲解
ConcurrentHashMap使用的是分段锁Segment来保证不同的Segment区域互相不干扰,不存在锁竞争关系,从而提升map的效率.
由于ConcurrentHashMap中存放的是Segment数组,每个Segment持有一个锁,和HashEntry数组.
定位一个key应该在哪个segment中非常重要,如果大多数的key被定位到一个segment中,则这个机制的意义就不大了.因此要避免不同的hashcode被分配到同一个segment中去.
segment掩码最终用于计算key在segment数组中的位置,他的值为
segmentMask:segment数组长度-1
以put方法举例(jdk版本1.7)
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
第6行中j即是定位segments位置的代码.默认情况下segmentShift的值为28,之所以无符号右移了28位,是因为hash(key)中已经进行了取key.hashcode,多次左右移动
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
下面直接用key.hashcode与掩码mask(默认15)进行与有什么后果呢
以下四个hashcode & 15的结果 (15的二进制位1111)
0001111 & 15 =15 0011111 & 15 =15 0111111 & 15 =15 1111111 & 15 =15
这样就造成了只要低4位相同,则无论高位是否相同,最终结果都一样,这样的就造成了大量key被分配到同一个segment中.
采用rehash值算法后,j的值为4,15,7,8就都不相同了
HashMap
由此推算HsahMap其实也做了小量reHash操作
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
第6行中,其实hash(key)也做了简单的rehash,避免大量key,分配到某一个Entry中
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
总结:
ConcurrentHashMap和HashMap归根结底,里面都有一个数组,来存放Entry<K,V>,数组的大小是有限的.
一个key被映射到数组的哪个位置其实不重要,重要的是避免大量key映射到同一个位置.由于ConcurrentHashMap里面位运算太多,以HashMap举例,它拿到一个hash后,定位数组位置的算法是:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
以HashMap默认的length:16举例, h&15就是最终的位置.h是int型,有32位,而15只有低4位不为0,则在按位与的场景下,只要低4位相同,则总会获取相同的位置下标.rehash就是为了消除这种较高冲突的可能,根据某种算法,打乱低4位,最终等到不同的位置下标.当然,如果两个h一样,是肯定会分配到相同的位置下标的