ConcurrentHashMap\HashMap put操作时key为什么要rehash

时间：2020-12-22 06:14:09

参考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一样,是肯定会分配到相同的位置下标的

相关文章