Map的实现原理
https://blog.csdn.net/justloveyou_/article/details/62893086
数组:寻址容易,插入 删除难
链表: 插入删除容易,寻址难
Map 底层:数组,数组的每一项都是一个链表
hashmap.png
负载因子:loadFactor: 一个散列表的空间使用程度
扩容阀值:thershold :它的值=HashMap容量* 负载因子
// map 底层实现仍是数组,只是数组的每一项都是一条链表
table =new Entry[ DEFALT_INITIAL_CAPACITY];
每次new hashmap 时候都会初始化 一个Entry 类型的数组;
Entry 定义:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 键值对的键
V value; // 键值对的值
Entry<K,V> next; // 下一个节点
final int hash; // hash(key.hashCode())方法的返回值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的构造函数
value = v;
next = n;
key = k;
hash = h;
}
......
}
Entry是map的内部类,定义了key value等 ,Entry 哈希表所存储的元素的具体形式
5.存取方法
保持key唯一,需要比较,如果是用equal 效率较低,时间复杂度O(n);哈希内部有个哈希表管理元素, 哈希算法现快速存取:通过key.hashcode 获得哈希码,查对应的桶位置即bucketIndex,如果有哈希冲突,就会取出bucketIndex桶内所有元素,并通过hashcode和 equal 逐个比较看是否存在key,存在替换,不存在,存储到这个桶里
- 对NULL键的特别处理:putForNullKey()
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
// 若key==null,则将其放入table的第一个桶,即 table[0]
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { // 若已经存在key为null的键,则替换其值,并返回旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 快速失败
addEntry(0, null, value, 0); // 否则,将其添加到 table[0] 的桶中
return null;
}
if key ==null ,put in bucketIndext==0 ;
the key==null is the only one in the hashmap
7.hashmap中哈希策略(即hash算法)
在同一个版本的Jdk中,HashMap、HashTable以及ConcurrentHashMap里面的hash方法的实现是不同的。再不同的版本的JDK中(Java7 和 Java8)中也是有区别的。
hash() 算法对 key的hashcode 重新计算
indexFor()生成Entry 数组对应的位置
int hash =hash(key.hashcode);
//hash在桶中的位置
int i =indexFor(hash,table.length)
先看下 hash算法的实现:
HashMap In Java 7
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
h & (length-1)什么意思呢? hash值与hashMap的(length-1)做了&运算,取模计算(%) ,得到位于区间[0,length-1]的一个值。特别地,这个值分布的越均匀, HashMap 的空间利用率也就越高,存取效率也就越好。
为什么用&运算 ,而不是“%”?因为 在javaz中,&运算是直接对内存数据操作,而不需要转为十进制,效率更高。
位运算(&)来实现取模运算(%)呢?这实现的原理如下:
X % 2^n = X & (2^n – 1)
2n表示2的n次方,也就是说,一个数对2n取模 == 一个数和(2^n – 1)做按位与运算 。
假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 = 7 ,即0111。
此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。
上面的解释不知道你有没有看懂,没看懂的话其实也没关系,你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。
6 % 8 = 6 ,6 & 7 = 6
10 & 8 = 2 ,10 & 7 = 2
&=%.png所以,只要保证hashmap长度是2的倍数,就可以实现上述的&运算 =%;
实际上,hashmap的长度的确是2的倍数,初始值是16,之后每次扩容都是原来的2倍
总结:hashmap在put() get() 时候,为了保证key的唯一性,先去查找是否已经存在key,查找方法就是 通过int h= hash(key.hashCode) 得到 一个int值 h,然后indexFor(h)
h&(length -1) 得到在链表数组的位置。
hash冲突:
即2个键值不同但是 和(length -1)进行相与后相同,则产生冲突
主要是 高位不同、地位相同造成的冲突,举个例子:
如果HashTable的大小为16,
length -1 =15 二进制:“00000000000000000000000000001111”
一个hashCode:
“1011000110101110011111010011011”
按位与算(都为1时,才=1)如下图:
按位与算.png
那么如何解决这种冲突呢,来看下Java是如何做的。其中的主要代码部分如下:
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
意义: 主要是对hashCode进行扰动,将高位、地位的特征结合,使得高位或是低位的变化都会对最终结果产生影响,从而降低产生哈希冲突的概率。
哈希:就是 根据 hashCode 得到hashMap 数组所在桶的位置。
举例说明,扰乱解决冲突:
key1的hashCode是11280384,用16进制表示是0x0AC20000
key2的hash是1568768,用16进制表示是0x017F0000
如果不进行扰动,直接用hashCode来计算key在HashMap的table[]中的index://HashMap的indexFor源码
static int indexFor(int h, int length) {
return h & (length-1);
}
假设此时table[]的length是16,那么对于key1来说就是0AC20000 & 0000000F = 0对于key2来说017F0000 & 0000000F = 0也就是说key1和key2的存储位都是0,发生了hash冲突。
加入扰动函数之后:0AC20000 >>> 20 = 000000AC0000 1010 1100 0010 0000 0000 0000 0000 右移20位 = 0000 0000 0000 0000 0000 0000 1010 11000AC20000 >>> 12 = 0000AC20000000AC ^ 0000AC20 = 0000AC8C0AC20000 ^ 0000AC8C = 0AC2AC8C
扰动函数的目的是把hashcode的高低位混在一起,让高位发生变化时,低位同时也发生变化。
接下来又进行了一些更多的扰动计算:
0AC2AC8C >>> 7 = 001585590AC2AC8C >>> 4 = 00AC2AC80AC2AC8C ^ 00158559 ^ 00AC2AC8 = 0A7B031D所以对于key1来说,扰动完成后的hash是0A7B031D而key2进行相同的扰动计算后,hash是016A18B6这样key1的存储位是13,key2是6,没有发生hash冲突。
在java8中这个扰动函数被简化了:
h = h ^ (h >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
只简单地把hashCode的高16位移动到低16位后与自身进行异或。
(https://www.zhihu.com/question/51784530)
HashTable In Java 7
在线程安全的 HashTable中,其hash的实现:
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
可见,和HashMap的“&”不同的是,直接取模“%”
1.为何把hash值和0x7FFFFFFF做一次按位与操作呢?
Because:
-
0x7FFFFFFF
is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit. -
(hash & 0x7FFFFFFF)
will result in a positive integer. -
(hash & 0x7FFFFFFF) % tab.length
will be in the range of the tab length.
哈哈,说人话就是
为了保证得到的index的第一位为0,也就是为了得到一个正数。因为有符号数第一位0代表正数,1代表负数。
HashTable采用简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数了。由于篇幅有限,这里就不贴代码了,直接给出结论:
HashTable默认的初始大小为11,之后每次扩充为原来的2n+1。
也就是说,HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。
由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时,简单的取模哈希的结果会更加均匀。(这个是可以证明出来的,由于不是本文重点,暂不详细介绍,可参考:http://zhaox.github.io/algorithm/2015/06/29/hash)
2.关于hash函数为什么要选择对素数求余?
一组均匀分布的key,其中同m公约数为1的那部分,余数后在[0,m-1]上还是均匀分布的,但同m公约数不为1的那部分,余数在[0, m-1]上就不是均匀分布的了。把m选为素数,正是为了让所有key同m的公约数都为1,从而保证余数的均匀分布,降低冲突率。
例子:一组key值 12、5、7、16、22 同m=5公约数分别为2、1、1、3、4
同m公约数不为1的那部分,余数是0、2
但同m公约数不为1的那部分,余数是 2、2、1可见不是均匀分布的;
ConcurrentHashMap
ConcurrentHashMap In Java 8
Java 8 里面的求hash的方法从hash改为了spread。实现方式如下:
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}