jdk8 HashMap源码解读(数学思想)，亲自造数据实验其原理*(੭*ˊᵕˋ)੭*ଘ（持续更新中）
前言
这个HashMap底层源码，加上这次写博文，再加上我前面分析了ConcurrentHashMap的put,扩容,计数，我已经看hashMap原理看了4遍了，每次一看就好几天。我真的每看一次，都有新的大收获啊！！！作为一个技术控的妹子，哇╰(°▽°)╯，sun公司的大神真的好厉害，仰慕！！！
概述
HashMap是一种数组加链表形式的结构，跟准确的说是一个线程不安全链表数组结构。适合存放key-value键值对，做等值查找。
java8及之后的改变
在java1.8之后，将HashMap做了优化。
首先，当链表节点个数大于8个以后，会将链表转换为一棵红黑树。至于为什么是8个，源码中的注释说，是做了大量随机数测试。
而后，就是面试经常喜欢问的，在多线程的情况下，HashMap会有什么缺陷。在java8之前，标准答案就是形成循环链表。java8及之后，对这个缺陷做了优化。
在java8之前，扩容时，直接对所有的节点rehash(重新计算下标值)，使用e.hashCode&(newTabLength-1)得到一个在新数组里的新下标。这种方式在多线程的情况下，存在隐患，会形成循环链。
那么在什么情况下会出现这种情况？
线程1，发现 size*local_factory(扩容因子0.75)>=tab.length, 准备开始扩容。这时线程1这一段的时间片执行完，让出cpu。
线程2获得了cpu，也发现可以触发扩容了,创建一个新的数组(ps:新数组当前独属于当前线程内存)。开始对所有的节点进行rehash。
期间可能由于时间片执行完，而让出cpu执行权。线程1，获取cpu执行权，两条线程交替执行。
当线程1，对原数组中的i位置的链表进行rehash，此时该链表是这样的
这时，线程1时间片执行完，线程2获得cpu，也对这条链表进行rehash之后，放到新数组，得到将B放到了链头，即B.next=A，A的next指向还没来得及改，于是A.next还是指向B。在要改的关键时刻，其它线程获取cpu执行权，它这时来看链表，已经变成这个样子了。
形成了一条循环链表。如果是做查找操作，那就完蛋了，一直循环在这里。rehash的时候，刚rehash完A，然后rehash A.next(B),之后rehash B.next,没错又是A。。。 ㄟ( ▔, ▔ )ㄏ
java8的时候，对这个缺陷做了修改。不再是逐个rehash节点，对原数组i位置的链表节点依次进行 e.hash & oldCap(原数组长度) 结果等于1的组成一条链表放到新数组i+oldCap位置。结果等于0的组成一条链表放到新数组i位置。这样就避免了循环链表的出现。
HashMap源码中用到的运算
&:按位与
1 1 0 1 0 1
& 1 0 0 1 0 1
———————
1 0 0 1 0 1
|：按位或
1 0 1 1 0 1 0
| 1 1 0 1 1 0 0
————————
1 1 1 1 1 1 0
^:按位异或
1 0 1 1 0 1 0
^ 1 0 0 1 1 0 0
————————
0 1 0 0 1 1 0
>>>:无符号右移
10000(16)>>>2 = 100(4)
<<:左移
100(4)<< 2 = 10000(16)
源码解析
接下开始我们的源码解析啦（￣︶￣）↗
构造方法
无参构造方法
public HashMap() {
//设置扩容因子为默认扩容因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
有参构造方法
/**
* initialCapacity 元素可能的个数
* loadFactor 扩容因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果元素个数超过默认最大容量，替换为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//初始化阈值，tableSize方法会返回一个略大于initialCapacity的一个2^n的值
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor方法,根据参数cap，计算一个略大于cap的2^n的数
/**
* cap元素个数
* |= :先按位或再赋值
* >>> :无符号右移
*/
static final int tableSizeFor(int cap) {
//因为cap可能是2^n,减一之后变成111...111,使得二进制数中尽量多一些1.
int n = cap - 1;
//任何数的二进制最高位一定是1，所以n>>>1右移之后最高位也是，进行 | 运算，如下：
/** 100...00(n)
* | 0100...0(n>>>1)
*——————————————
* = 110....0
* 得到最高两位一定是1的数
*/
n |= n >>> 1;
/**
* n=110....0
* 110....0(n)
* | 00110...(n>>>2)
* ————————————————————
* 11110....
* 得到最高的四位是1的数
*/
n |= n >>> 2;
/**
* 同上
*/
n |= n >>> 4;
/**
* 同上
*/
n |= n >>> 8;
/**
* 同上，因为数组最大长度是32，所以右移到16位已经够了
*/
n |= n >>> 16;
//最终得到一个二进制全是1的数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
hash 计算key的hash值，返回的值用于与数组长度做运算得出存放的下标位置
将key的hashcode值与hashcode>>>16进行异或运算
原因：
将高16位与低16位进行异或运算，尽量打乱16位。一般数组长度不会超过16位二进制，数组长度都那么大，那么占用的内存也比较大了，还不如别放内存里。
本人也本着实验的精神，稍微实验了一下：
hashcode & (tab.length-1) 和 (hashcode ^ (hashcode>>>16)) & (tab.length-1) 分别得出的下标 ↓
hashcode & (tab.length-1):
key=hella;index=4 key=abcde;index=3 key=asdfg;index=3 (一对碰撞)
key=world;index=2 key=yuics;index=13 key=bkjsd;index=2 (一对碰撞)
key=world;index=2 key=yuics;index=13 key=bkjsd;index=2 key=dhjah;index=13 (两对碰撞)
(hashcode ^ (hashcode>>>16)) & (tab.length-1) :
key=hella;index=13 key=abcde;index=7 key=asdfg;index=15 (没有碰撞)
key=world;index=3 key=yuics;index=2 key=bkjsd;index=5 (没有碰撞)
key=world;index=3 key=yuics;index=2 key=bkjsd;index=5 key=dhjah;index=15 (没有碰撞)
可以粗略验证合并高位影响可以减少碰撞率
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
putVal
putVal方法主要做的事是：
1.检查数组是否初始化；否，初始化数组长度为2^n
这里可能就有两个考点了：
(1)为什么hashMap的数组一定是2^n ?
(2)为什么hashMap每次扩容是原来长度的2倍 ?
这两个可以一并回答。目的是为了，防溢出，减少碰撞。
首先我们从hashMap计算存放下标位置的方式开始说起，(len-1)&hash，可能乍一看迷惑不解。其实用数学来等价替换一下就是 hash%len 即求hash除数组长度的余数。
那为啥是求余数呢？
假设数组长len=16，hash=34，hash超出了数组长度。怎么办？
我们对它们进行求余运算，hash%len=2,哦~( •̀ ω •́ )y 放到下标为2的位置。所以对长度求余运算，得到值的范围是0~(len-1),永远不会超出下标值范围。=>由此可得，(len-1)&hash 做 & 是为了防溢出。
那为什么len必须是2^n？
由上面可知，为了防溢出，必须是(len-1)&hash。所以接下来，要解决得是减少碰撞。 可以转化成数学来解释 ↓。
设a,b为集合{0，1}中的一个数，求a&b的值。
①令a=1，则有当b=0时，a&b=0;有当b=1时，a
&b=1;两种结果{0,1}
②令a=0,则有当b=0时,a&b=0;有当b=1时，a&b=0;只有一种结果{0}
所以由上题可知，a&b运算中，只要有一方的值为1，则运算之后的可能的结果多一些。
所以，要想减少碰撞，即(len-1)&hash的结果可能性多一些,必须其中一个的二进制每一位都是1。hash变化比较大，没法控制;len-1相对固定，可以控制它是111…11这种形式。
由于11…11=2^n -1,比如1111=2^4 -1=15;
由此可知 len-1 = 2^n -1; len=2^n; <(￣︶￣)↗ 所以答案出来了。
由上述可知，每次扩容的长度得是2^n ,每次扩大2倍，是不是就是2^(n+1) 保持了它是2的幂次方
/**
* Implements Map.put and related methods.
*
* @param hash hash for key key的hash值
* @param key the key
* @param value the value to put 要put的value
* @param onlyIfAbsent if true, don't change existing value 如果为true，则代表如果value相同不覆盖
* @param evict if false, the table is in creation mode. 如果参数为false，这个数组处于创建模式
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前数组还未初始化
if ((tab = table) == null || (n = tab.length) == 0)
//调用resize()方法，也是扩容的方法，初始化数组,数组长度必然是2^n
n = (tab = resize()).length;
/**
* n数组长度；
* 若当前数组i位置没有元素存放，直接构建一个node存放进去
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//数组i位置有元素
//e:tab[i]中相同节点
Node<K,V> e; K k;
//若tab[i]的链表头节点与要添加的新元素hash值和key相等，不需要插入操作，后续判断是否需要覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//tab[i]位置是一颗红黑树节点，调用插入红黑树节点方法，有相同节
//点，则返回节点；没有则插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//tab[i]位置是一个直线链表型节点
/**
*查找链表中是否有与新节点相同hash、key节点，有，后续判断是
*否需要覆盖value；
*没有:
*将新节点插入到链表最后，并判断是否需要转换成红黑树
*/
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若链表/红黑树中有相同节点，根据参数判断是否需要覆盖value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//HashMap修改次数加1
++modCount;
if (++size > threshold)
resize();
//LinkedHashMap子类实现的方法，插入后的回调，创建者模式
afterNodeInsertion(evict);
return null;
}
resize扩容
1.这个在1.7及之前最喜欢问的就是，上面讲过的循环链表的问题。
2.新数组长度=原数组长度<< 1
3.1为了解决循环链表的问题，直接对直线型链表进行分类拆分。
方法：
将节点的hash值与原数组长度进行**&**运算，只会得到两种结果：
{0,oldCap},即0和原数组长度。可以验证下 ↓
数组长度为2^n(100…00),至于hash值,分成两种情况：
① hash二进制数按位对应数组长度二进制数(100…0)的最高位都是1
=> hash: 1 x x x x 1 x x x x
oldCap:& 0 0 0 0 0 1 0 0 0 0
————————————
0 0 0 0 0 1 0 0 0 0 => oldCap
② hash二进制数按位对应数组长度二进制数(100…0)的最高位一个0一个1
=> hash: 1 x x x x 0 x x x x
oldCap:& 0 0 0 0 0 1 0 0 0 0
————————————
0 0 0 0 0 0 0 0 0 0 => 0
由上可得，经过 hash&oldCap 运算可分成两类。
3.2 将3.1计算结果为oldCap节点组合成一条链表，直接放到新数组的i+oldCap位置。
那么问题来了，为什么要直接放到i+oldCap?
作为一个理科女，我最喜欢找规律。然后就拿一个具体的数字计算了下，我明白了规律。果然sun公司大神！！！我真的忍不住仰慕！！！还是跟数学相关，当然不是高等数学。
以下我随便拿了一个数找的规律 ↓
由上面的规律我也突然明白了为什么他拆分的时候要以hash & oldCap方式来区分了。
待续
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//原数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原数组的阈值
int oldThr = threshold;
int newCap, newThr = 0;
//数组已经初始化了
if (oldCap > 0) {
//如果原数组的长度大于等于hashMap最大的容量大小
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果新数组长度小于最大值 1<<30 并且大于等于默认初始值 1<<4
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//计算新阈值，原阈值<<1
newThr = oldThr << 1; // double threshold
}
//如果原数组尚未初始化，但阈值已有值，设置数组长度为旧阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//数组为初始化，阈值也未初始化，设置为默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新阈值尚未赋值，使用newCap乘扩容因子得出新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//创建新数组，并将table的引用指向新数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//注：table没有用volidate关键字修饰，其他线程检测不到table引用的变化
table = newTab;
if (oldTab != null) {
//循环读取原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//置空就数组的引用
oldTab[j] = null;
//如果该链表只有一个头节点，直接重新计算一遍下标
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是一颗红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果是一条直线型链表，直接拆分成两条链表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
/**
* 拆分链表
* 拆分方法：
* 节点哈希值与旧数组长度进行&运算，数组长度
*/
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上一篇： 简单的测试"框架"
下一篇： python怎么随机产生一个范围内的数