proginn0937458772
再谈HashMap
hashMap优化说明
本文主要针对jdk中hashMap从1.7=>1.8做了哪些优化说明，在阅读本文之前需要对hashMap原理有基本的了解
1.8HashMap做了哪些优化？
01
数据结构优化
在1.7时Map的结构为数组+链表，1.8为了解决hash冲突时导致链表的长度过长，针对链表进行了优化，引入了红黑树，1.8后的map结构为数组+链表/红黑树
02
hash函数优化
1.7需要对hashCode值进行4次移位运算，4次异或运算
1.7hash函数
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 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);
1.8hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.8后hash函数优化为获取key的hashCode值后进行右移16位再进行异或运算，这样很大程度上提高了性能问题
03
链表插入的顺序
链表的插入方式由头插法变为了尾插法，1.7中将新元素放到数组中，原始节点作为新节点的后置节点，1.8是变量链表，将元素放到链 表 最后
这样做是为了避免在多线程对map进行扩容时链表结构形成环形数据结构，造成死循环
04
扩容优化
在1.7扩容时会调用hash函数重新hash，把旧数组上的元素复制到新数组上，1.8后在扩容时采用更简单的判断，只需要把索引位置发生变化的元素复制到新数组上面
扩容的时候为什么1.8不用重新hash就可以确定元素在新数组上的位置？
因为扩容时每次都是对数组进行扩容原数组的2倍，通过二进制来看仅仅是计算数组下标位置高位多了个1。
例如: 计算数组下标(数组长度-1) & hash
数组长度由16扩容到32，16-1 对应二进制为0000 1111
32-1 对应二进制为0001 1111
在进行&运算时，1与任何数&都是它本身，如下图hashcode高位第4位为0和高位为1的情况:
当第4位为0时重新hash值不变，
当低位为1时重新hash比原数量大16，刚好大就数组的长度
05
扩容时元素拷贝
在1.7时是循环遍历数组元素，并将旧数组元素复制到新数组上面，
在1.7之后是通过一种高低链表的方式，不需要拷贝到新数组的元素放在低链表，需要拷贝到新数组的元素放在高链表
如源码:loHead,hiHead
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;
}
