HashMap加载因子及转红黑树探究
HashMap探究（二）
今天我们来探究下：负载因子为什么是0.75？为什么红黑树扩容是当链表长度>=8时扩容？Java7的hashmap扩容死锁演示与环链形成分析？
负载因子为什么是0.75？
我们先来看看源码：在构造函数中未指定时使用的加载因子
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
我们知道，最理想的情况就是，当我们put进来的元素刚好平铺在数组上，而不产生链表，尽量不产生Hash碰撞。但是我们明白这种情况只是理想化的，是难以实现的。
那么我们反证一下：当我们将负载因子不定为0.75的时候（两种情况）：
1、 假如负载因子定为1（最大值），那么只有当元素填慢数组长度的时候才会选择去扩容，虽然负载因子定为1可以最大程度的提高空间的利用率，但是我们的查询效率会变得低下（因为链表查询比较慢）
结论：所以当加载因子比较大的时候：节省空间资源，耗费时间资源
2、加入负载因子定为0.5（一个比较小的值），也就是说，知道到达数组空间的一半的时候就会去扩容。虽然说负载因子比较小可以最大可能的降低hash冲突，链表的长度也会越少，但是空间浪费会比较大
结论：所以当加载因子比较小的时候：节省时间资源，耗费空间资源
但是我们设计程序的时候肯定是会在空间以及时间上做平衡，那么我们能就需要在时间复杂度和空间复杂度上做折中，选择最合适的负载因子以保证最优化。所以就选择了0.75这个值，Jdk那帮工程师一定是做了大量的测试，得出的这个值吧~
为什么红黑树扩容是当链表长度>=8时扩容
看源码：当链表数量大于8时转化为树
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 树阈值 = 8；
*/
static final int TREEIFY_THRESHOLD = 8;
泊松分布
当我们在put一个元素，产生hash冲突的时候，会遵循泊松分布（通过概率学统计出来）的规则;
泊松分布公式：(exp(-0.5) * pow(0.5, k)
泊松分布图：
意思就是说，当负载因子为0.75的时候，还有当链表的长度的增加。如果再添加新的节点进链表的时候，这个添加进当前链表概率是随着节点的增加而越来越少（泊松分布）。JDK源码中有这样的解释：
也就是说，当put进来一个元素，通过hash算法，然后最后定位到同一个桶（链表）的概率会随着链表的长度的增加而减少，当这个链表长度为8的时候，这个概率几乎接近于0，所以我们才会将链表转红黑树的临界值定为8
当然，虽然在hashmap底层有这种红黑树的结构，但是我们要知道能产生这种结构的概率也不大，所以我们知道在 JDK1.7 到 JDK1.8 这其中HashMap的性能只提高了 7%-8% 左右，提高的并不多。
Java7的hashmap扩容死锁演示与环链形成分析
Java7的hashmap扩容死锁演示与环链形成分析
我们首先来看一下JDK1.7中put方法的源码
我们打开addEntry方法如下，它会判断数组当前容量是否已经超过的阈值，例如假设当前的数组容量是16，加载因子为0.75，即超过了12，并且刚好要插入的索引处有元素，这时候就需要进行扩容操作，可以看到resize扩容大小是原数组的两倍，仍然符合数组的长度是2的指数次幂
我们再进入resize方法如下，它首先会对之前的数组容量进行判断，看是否已经达到了数组最大容量，如果没有，后面会进行数组的转移操作，即transfer方法
JDK1.7中，当数组容量达到16*0.75=12的时候，数组就需要扩容，在扩容的时候，我们都知道会涉及元素的迁移，那么下面代码就是元素迁移的主要代码：JDK1.7中HashMap存在死锁问题的原因也主要集中在这
//将老的表中的数据拷贝到新的结构中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//容量
for (Entry<K,V> e : table) { //遍历所有桶：即数组
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
if (rehash) {//如果是重新Hash，则需要重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//定位Hash桶
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
}
我们将重新记算hash值的逻辑先去掉（回顾：为什么使用位运算而不使用取模运算：因为位运算效率高，取模运算效率低，在数组迁移的时候会进行重hash，如果效率不高会极大的影响put的效率）。只留下主要的迁移数组的代码：
for (Entry<K,V> e : table) { //遍历所有桶
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
举例：
假设有两个线程，两个线程都对这个hashmap进行扩容，扩容就要执行数组迁移代码。
假设线程T2先来对数组进行迁移，当线程而二执行到Entry<K,V> next = e.next的时候，然后线程T2突然阻塞了;
外层for循环来遍历数组的，当数组的值不是空的时候就进入内层的while循环去遍历链表，假设线程T2两个指针（一个叫做e2，一个叫做next2），当遍历到这个结点的时候：e2表示的就是大狂神这个节点，next2表示e2的下一个节点，也就是佩雨的这个节点；
然后刚好线程T1也跑进啦这个逻辑里面了，那么线程T1也有两个指针（e，next），e也指向的是大狂神，next也指向的是佩雨
T1线程继续跑这个逻辑（下面是T1线程自己的扩容与迁移图），会继续转移这个链表，转移完成之后发现一个问题：转移过去后两个节点的上下位置反了（大狂神和佩雨已经反了）
然后T2这个时候又唤醒了，因为线程T2一直都是指向这两个元素的（e2–>大狂神，next–>佩雨），也就是成下图这样
然后T2也要去循环执行这个逻辑
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
最后会产生这样的情况，就是最终会形成一个环
Java8中的HashMap扩容优化（不会出现死环）
JDK1.8中HashMap扩容的代码
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
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);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
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;
}
当我们对数组进行迁移的时候，这里面定义了两组指针，分别是高位和低位的头和尾
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
然后用当前节点的hash值和旧数组的长度（16）做’与’运算
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
分析：
hash值： 0010 1111 1010 1110
数组的长度(16) 0000 0000 0000 1000
‘与’运算的结果，只可能有两种值：
0000 0000 0000 0000---------------0
0000 0000 0000 1000---------------16
也就是说当前节点用当前节点的hash值和旧数组的长度（16）做'与'运算的结果只可能是0或16
用当前节点的hash值和旧数组的长度（16）做’与’运算，结果出来如果时0就是低位指针，如果是16就是高位指针，那么我们再看：
// 如果是0，则使用低位的指针
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 如果是16，则使用高位的指针
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
如果说 ‘与’ 出来的值是0，那么就会用低位的指针去迁移该数组。如果判断出来的是16，就会用高位的指针去迁移。
那么我们的最终的指针就会成下面的样子：
然后就开始迁移
低位迁移：首先：先将高位和低位断开（将低位的尾部的next置为空）
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
就成下面这样了：
紧接着将低位的头部loHead付给新数组的某个值，也就是将低位的所有节点移动过去，并且放在与就索引相同的位置；
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值，也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
高位迁移：先将高位的尾部断开
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值，也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null; //把高位的尾部节点的next值为空
newTab[j + oldCap] = hiHead;
}
再将高位的头部放到新数组的j + oldCap索引处（当前索引+旧数组的长度），比如说现在的索引是3，再加上数组长度16，最后就是将高位放到新数组的索引为19的地方去；
然后我们发现这个设计非常的巧妙，避免了顺序的颠倒，再也不会出现狂神和佩雨颠倒的问题了
总结
在JDK1.8之后，HashMap底层的数组扩容后迁移的方法进行了优化。把一个链表分成了两组，分成高为和低位分别去迁移，避免了死环问题。而且在迁移的过程中并没有进行任何的rehash（重新记算hash），提高了性能。它是直接将链表给断掉，进行几乎是一个均等的拆分，然后通过头指针的指向将整体给迁移过去，这样就减小了链表的长度