最近在写一个简易的分离锁的类:
要求:对不同的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的平均分布
。
分享到:
相关推荐
并且如果HashMap中元素的个数大于等于阈值并且根据key的哈希值和数组长度减一做按位与运算获取的数组下标位置元素非空,则需要扩容,扩容后容量是原来的2倍,也仍然是一个2的幂,那么HashMap为什么这样来做呢?...
Java基础-模拟HashMap集合(基于数组和链表) 数组和链表.pdf
hashmap的数组长度为什么要保证是2的幂? 如何用LinkedHashMap实现LRU? 如何用TreeMap实现一致性hash? ConcurrentHashMap是如何在保证并发安全的同时提高性能? ConcurrentHashMap是如何让多线程同时参与扩容? ...
HashMap 底层的数据结构主要是:数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时, 链表会转化成红黑树,...比如数组下标索引为 2 的位置就是一个链表,下标索引为 9 的位置对应的 就是红黑树,具体细节请看内容
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized,所以HashMap很快...
Java数组+链表简单实现HashMap的put和get 数组和链表.pdf
树tree、动态数组dyArray、hashMap、拼图算法.zip
// 默认的HashMap中数组的长度 16 static final int DEFAULT_INITIAL_CAPACITY = 1 ; // aka 16 // HashMap中的数组的最大容量 static final int MAXIMUM_CAPACITY = 1 ; // 默认的扩容的平衡因子 static final ...
14.HashMap 的长度为什么是2的幂次方? 15.HashMap 与 HashTable 有什么区别? 16.如何决定使用 HashMap 还是 TreeMap? 17.HashMap 和 ConcurrentHashMap 的区别? 18.ConcurrentHashMap 和 Hashtable 的区别?
NULL 博文链接:https://128kj.iteye.com/blog/1749453
3、HashMap的数组大小为什么一定要是2的幂 4、HashMap为什么是线程不安全的 5、Java7到Java8做了哪些改进 1、HashMap的默认容量 从HashMap的构造函数说起。 initialCapacity表示的是初始化的容量,默认是1<<4...
Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 数组和链表.pdf
Java用数组和链表的方式简单实现HashMap的增删改功能 数组和链表.pdf
java hashmap 扩容因子为什么是0.75,官方给出的解释
工程(VS2013)主要构造了HashMap和list集合,通过查找集合中的元素对两者的效率进行比较
hashmap的内部实现,hashmap是使用数组+链表+红黑树的形式实现的,其中数组是一个一个Node[]数组,我们叫他hash桶数组,它上面存放的是key-value键值对的节点。HashMap是用hash表来存储的,在hashmap里为解决hash...
HashMap是一个存储key-value的键值对集合,每一个元素都是一个Entry,这些键值对分散在数组当中。 你为什么要用HashMap? 1.解决问题需要的数据结构是一种键值对的数据结构 2.HashMap是线程不安全的,其速度比较快 3....
存储结构在jdk1.7当中是数组加链表的结构,在jdk1.8当中改为了数组加链表加红黑树的结构。 HashMap在多线程的环境下是不安全的,没有进行加锁措施,所以执行效率快。如果我么需要有一个线程安全的HashMap,可以使用...
3.为什么hashmap不安全 why 3.1 插入HashMap.put 3.1.1 HashMap 在扩容的时候 3.2 HashMap 在删除数据的时候 0.背景 经常会看到说HashMap是线程不安全的,ConcurrentHashMap是线程安全的等等说法,不禁有个疑问,...
分析HashMap在put数据时是如何找到要存放的位置的,对决定位置的hashCode计算方法进行详细解释,分析为啥要用高低16位异或运算,以及数组长度是如何影响元素存放位置的