分享

知道为啥HashMap里面的数组size必须是2的次幂?

 liuguichuan 2014-12-23

最近在写一个简易的分离锁的类:

要求:对不同的Key进行hash得到一个Lock,并要求对锁映射的概率差不多。比如,160个Key,分布到16个锁上,大概有10个Key是映射到同一个锁上的,只要这样并发效率才会高。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class SplitReentrantLock {
    private Lock[] locks;
    private int LOCK_NUM;
    public SplitReentrantLock(int lockNum) {
        super();
        LOCK_NUM = lockNum;
        locks = new Lock[LOCK_NUM];
        for (int i = 0; i < LOCK_NUM; i++) {
            locks[i] = new ReentrantLock();
        }
    }
    /**
     * 获取锁, 使用HashMap的hash算法
     *
     *
     * @param key
     * @return
     */
    public Lock getLock(String key) {
        int lockIndex = index(key);
        return locks[lockIndex];
    }
    int index(String key) {
        int hash = hash(key.hashCode());       
        return hash & (LOCK_NUM - 1);
    }
    int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

用法:

1
2
3
4
5
6
7
8
SplitReentrantLock locks = new SplitReentrantLock(16);
  Lock lock =locks.getLock(key);
  lock.lock();
  try{
     //......
   }finally{
   lock.unlock();
   }

本来认为用HashMap的hash算法就能够将 达到上述的要求,结果测试的时候吓了一跳。

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SplitReenterLockTest extends TestCase {
    public void method(int lockNum, int testNum) {
        SplitReentrantLock splitLock = new SplitReentrantLock(lockNum);
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
        for (int i = 0; i < lockNum; i++) {
            map.put(i, 0);
        }
        for (int i = 0; i < testNum; i++) {
            Integer key = splitLock.index(RandomStringUtils.random(128));
            map.put(key, map.get(key) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
    public void test1() {
        method(50, 1000);}
  
}

结果:1000个随机key的hash只是映射到8个Lock上,而不是平均到50个Lock上。

而且是固定分布到0,1,16,17,32,33,48,49的数组下标对应的Lock上面,这是为什么呢?

如果改为:

1
2
3
public void test1() {
    method(32, 1000);
}

 结果:1000个随机key的hash 映射到32个Lock上,而且基本上是平均分布的。

问题:为什么50和32的hash的效果差别那么大呢?

再次测试2,4,8,16,64,128. 发现基本上都是平均分布到所有的Lock上面。

得到平均分布的这些数都是2的次幂,难道hash算法和二进制有关?

看看hash算法:   

1
2
3
4
5
6
7
8
9
int index(String key) {
        int hash = hash(key.hashCode());       
        return hash & (LOCK_NUM - 1);
    }
    int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 先是经过神奇的(ps:不知道为什么这么运算,无知的我只能用神奇来形容)的位运算,最后和LOCK_NUM - 1来进行与运算。

本帖的关键点就是在于这个与运算中,如果要想运算后的结果是否平均分布,在于LOCK_NUM-1的二进制中1的位数有几个。如果都是1,那么肯定是平均分布到0至LOCK_NUM-1上面。否则仅仅分布指定的几位。

下面以50和32说明:

假设Key进行hash运行得到hash值为h,

比如:我测试的数据中的一些h的二进制值:

1100000010000110110101010001001
10111100001001110111000100010001
11111011111010101010000111001001
11001010011000100110110111011111
10001010100010111101011010011110

 50的二进制值:110010.减去1后的二进制:110001

 32的二进制值:  100000.减去1后的二进制:11111

因此h和 49 (即110001)与的结果只能为

000000  : 0

000001  : 1

010000  : 16

010001  : 17

100000  : 32

100001  : 33

110000  : 48

110001  : 49

而h和31 (即11111)与的结果为:

00000

00001

00010

....

11110

11111

这下知道原因了吧。LOCK_NUM -1 二进制中为1的位数越多,那么分布就平均。

这也就是为什么HashMap默认大小为2的次幂,并且添加元素时,如果超过了一定的数量,那么就将数量增大到原来的两倍,其中非常重要的原因就是为了hash的平均分布

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多