`
NanguoCoffee
  • 浏览: 49250 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

阅读更多

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

 

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

 

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);
	}

 

 

用法:

 

SplitReentrantLock locks = new SplitReentrantLock(16);
  Lock lock =locks.getLock(key); 
  lock.lock();
  try{
     //......
   }finally{
   lock.unlock(); 
   }

 

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

 

测试代码:

 

 

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上面,这是为什么呢?

 

如果改为:

 

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

 

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

 

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

 

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

 

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

 

看看hash算法:   

 

   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的平均分布

 

分享到:
评论
13 楼 NanguoCoffee 2011-02-18  
javantsky 写道
楼主为什么要自己实现分离锁呢?

java.util.concurrent.ConcurrentHashMap<K,V>
这个已经帮你搞定了



分离锁和Map没什么必然的关系呀。
分离锁的应用场景和Map的应用场景不同呀。

要求这样:
SplitReentrantLock locks = new SplitReentrantLock(16);
  Lock lock =locks.getLock(key); 
  lock.lock();
  try{
     //......
   }finally{
   lock.unlock(); 
   }





12 楼 javantsky 2011-02-18  
楼主为什么要自己实现分离锁呢?

java.util.concurrent.ConcurrentHashMap<K,V>
这个已经帮你搞定了
11 楼 obullxl 2011-02-18  
LZ分析有道理,最后的&操作,(LOCK_NUM - 1)的二进制1越多,越是平均分布,反过来说,也就是2^n会平均分布。
10 楼 NanguoCoffee 2011-02-17  
sniffer123 写道
LZ你自己的写法有问题啊。。跟HASH是不是 2的幂一点关系也没有
hash & (LOCK_NUM - 1) 能等同 hash % (LOCK_NUM - 1)吗?
假如LOCK_NUM = 14,那么 (LOCK_NUM - 1) 就是 二进制 1101
你用&,第二位永远都是会被去掉的,简单点说,如果hash 是 1~100,&后出来的结果分布肯定是不平均的
之所以会出现你那个只要是2^n就会分布平均,是因为这个时候,2^n的二进制是 1111,&出来相当于取低四位。


恩,在SplitReentrantLock 中使用hash & (LOCK_NUM - 1)确实达不到平均分布的要求。
直接拷贝hashMap.index(...),刚开始没注意,测试过后才发现的。

我没说和hash值有关。
只是和数组的长度有关。

9 楼 sniffer123 2011-02-17  
LZ你自己的写法有问题啊。。跟HASH是不是 2的幂一点关系也没有
hash & (LOCK_NUM - 1) 能等同 hash % (LOCK_NUM - 1)吗?
假如LOCK_NUM = 14,那么 (LOCK_NUM - 1) 就是 二进制 1101
你用&,第二位永远都是会被去掉的,简单点说,如果hash 是 1~100,&后出来的结果分布肯定是不平均的
之所以会出现你那个只要是2^n就会分布平均,是因为这个时候,2^n的二进制是 1111,&出来相当于取低四位。
8 楼 NanguoCoffee 2011-02-17  
Ulysses 写道
楼主把因果关系搞颠倒了吧。


不明白,怎么颠倒了?
不是因要求均匀分布,才要求数组长度为2次幂么?
7 楼 Ulysses 2011-02-17  
楼主把因果关系搞颠倒了吧。
6 楼 superobin 2011-02-17  
我觉得哈,仅有一个方面,就是分配平均。为啥分配平均?首先hashCode就是一个能基本保证散列后的数据均匀分布在int区间上的函数,而用一个平均分配的hashCode对table长度取余则可以另对象均匀的落在table中的每个链表中
假定 x 是2^n(n>0)那么 对任意整数i有
i&(x-1) === i%x
而&与%效率差距实在太大了
我之所以知道这个是因为看过访谈hashmap的作者,貌似他就是这个意思,原帖翻不到了
这个东西同样也解开了我对md5碰撞算法时那帮科学家写的i&3的疑惑


另外,map中有个void transfer(Entry[] newTable)方法,重新将old entrys逐链表扔进新的数组,故capalicy为2^n和扩容没有直接关系

5 楼 CoderPlusPlus 2011-02-17  
ls的两句话不就是同一个意思么
4 楼 pengmj 2011-02-17  
HashMap的算法有两个目的:1、尽量均匀分配;2、在一个节点上的元素尽可能少。
3 楼 NanguoCoffee 2011-02-17  
发现我的SplitReentrantLock的index(String key)改成另外一种算法,就可以避免hash分布不均匀。
 int index(String key) {
	int hash = hash(key.hashCode());
	hash = Math.abs(hash);
	return hash % LOCK_NUM;
}


使用取余操作 代替 与 操作。

优点:使用非2次幂的长度也能够hash均匀
缺点:多了一次Math.abs(hash),并且取余的效率比与运算的效率低

因此大并发使用的情况下,还是使用与操作比较好。普遍性来说还是取余比较好。
2 楼 NanguoCoffee 2011-02-16  
kimmking 写道
还有一个原因,扩容后,原有hash不变

其实还有一个方法可以满足这两个要求:使用质数。(例如.net的hashtable中当前用的是p,下个数则用小于2p的最大的质数)


hash不变是
 
  static int hash(int h) {
        // 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);
    }

得到的,不管是否扩容,对于指定的key来说,得到的值都是不变的。

因此扩容之后得到数组下标和扩容之前有可能是不一样的
1 楼 kimmking 2011-02-16  
还有一个原因,扩容后,原有hash不变。

其实还有一个方法可以满足这两个要求:使用质数。(例如.net的hashtable中当前用的是p,下个数则用小于2p的最大的质数)

相关推荐

Global site tag (gtag.js) - Google Analytics