一、HashMap底层实现
数组+链表的形式,在jdk1.8还引入了红黑树
每个节点分别有hash,key,value,next这四个成员变量,next指向下一个节点
二、JDK1.8做了哪些优化
JDK1.7底层
数组加链表
JDK1.8的优化
增加红黑树结构,
当链表数大于8且总结点数大于64时,转换成红黑树
链表过长会严重影响HashMap的性能,红黑树的结构可以快速增删改查
三、面试常见问题
JDK1.8HashMap扩容做了哪些优化
扩容时计算索引的优化(e.hash & newCap-1) ->(e.hash & oldCap),JDK1.8新的索引要么是j,要么是j+oldCap
头插法改尾插法(避免哈希环)
加载因子为什么是0.75
性能和容量之间平衡的结果:
因此,取了0.5和1 的均值0.75
当哈希冲突时,HashMap是如何查找并确认元素
确认key值是否相等
HashMap源码中的重要方法
查询(get),新增(putVal),数据扩容(resize)
新增方法的执行流程
HashMap是如何导致死循环的
JDK1.7:
假设原来HashMap大小为2,只有一个元素key=5
这时用两个线程分别添加thread1:key=3和thread2:key=7
如果thread1在执行Entry<K,V> next = e.next;时交出CPU使用权
此时thread1的e 指向 key=3 而next指向key=7
而此时thread2 resize之后,链表顺序反转,key=5指向key=7,key=7指向key=3
当thread1获取执行权后,new Table[i] = e把key=3的next指向key=7
此时形成的key=3和key=7的next是彼此,形成环,如下
主要原因是因为JDK1.7的扩容是头插法(resize之后倒序),而JDK1.8为尾插法(避免了这个问题)
HashMap的源码包括:
默认的初始化长度(16)
长度最好是2的倍数,因为取模运算(计算在数组的那个位置)在hashmap底层是用的位运算。
最大长度(1<<30)
默认加载因子/扩容因子/负载因子(0.75f)
当HashMap中有16*0.75个元素的时候,就会进行扩容
红黑树转换成链表的值(6)
当链表的元素降低到6及以下时,红黑树会转换成链表
链表元素转换成红黑树的最小值(8)
最小树容量(64)
当hashmap有64个元素及以上,数组中某个索引的元素有8个及以上时,会链表转红黑树
注意:
HashMap.put如果key在HashMap中已经有了一个键值对,则返回oldValue,如果不存在,则返回null
HashMap.tableSizeFor
一开始看的时候,我觉得这是什么玩意,在玩什么呢,(因为我设置的cap值基本都是遵循了2的幂指数),后面发现,这里的操作其实是将cap-1后,最高位位1的数位后面全部数位都赋值为1(二进制),然后再+1,使得我们获取到的值是2的幂指数,不得不说java源码开发团队的智慧还是值得吹一波的。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap.resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // oldTab指向扩容前的HashMap的底层Node数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap指向原来HashMap数组长度
int oldThr = threshold; // oldThr指向原HashMap的扩容阈值,初始化大小的最近的二进制(相等或向上)
int newCap, newThr = 0; // 新table暂时不初始化
if (oldCap > 0) { // 原来的HashMap有值
if (oldCap >= MAXIMUM_CAPACITY) { // 原来的元素个数大于等于最大元素个数 1 << 30
threshold = Integer.MAX_VALUE; // 扩容阈值设置为最大值
return oldTab; // 返回老HashMap 即不扩容
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 如果老的容量双倍都没有超过最大容量,且大于等于16
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 如果老的容量小于等于零,且老的阈值大于零
newCap = oldThr; // 新的容量等于阈值
else { // 老的阈值和容量小于等于零
newCap = DEFAULT_INITIAL_CAPACITY; // 新table容量为默认容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 阈值为默认阈值 16*0.75
}
if (newThr == 0) { // 如果新table的阈值没有设置
float ft = (float)newCap * loadFactor; // ft等于新容量 * 扩容因子(没传入默认0.75)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); // 新容量和ft都小于最大容量,则新阈值为ft,否则为Int最大值
}
threshold = newThr; // 这个table的阈值改变
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 新建Node数组
table = newTab;
if (oldTab != null) { // 扩容前的Node数组非空
for (int j = 0; j < oldCap; ++j) { // 遍历数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { // e = 数组j索引位置不为空(有Node)
oldTab[j] = null; // 老数组j索引位置制空
if (e.next == null) // 老数组j索引位置只有一个node
newTab[e.hash & (newCap - 1)] = e; // 老的hash重新分配在新数组的新索引
else if (e instanceof TreeNode) // 老数组j索引位置不止一个Node,且是红黑树
// 红黑树中做Node重新计算索引,与下面else类似,不同的是对新的链表检验是否需要生成红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// loHead标记不需要移动的链表头部,Tail为尾部
Node<K,V> loHead = null, loTail = null;
// hiHead标记需要移动的链表的头部,Tail为尾部
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next; // 循环的下一个Node
do { // 循环完Node数组j索引下所有Node
next = e.next;
if ((e.hash & oldCap) == 0) { // 不需要移动索引
// 1.7用的是(e.hash & newCap-1),计算模运算,重新计算索引
// 1.8的(e.hash & oldCap)用的是高位运算,只能得出0或者oldCap
// 所以新的索引要么是j,要么是j+oldCap
if (loTail == null) // 如果尾部为空,也就是刚初始化
loHead = e; // 当前Node为头部
else
// 否则尾部的Next为当前Node
loTail.next = e;
loTail = e; // 尾部指针指向当前节点
}
else {
if (hiTail == null) // 需要移动的尾部为空
hiHead = e; // 需要移动的头部为当前Node
else
// 否则尾部的Next为当前Node
hiTail.next = e;
hiTail = e; // 尾部指针指向当前节点
}
} while ((e = next) != null);
if (loTail != null) { // 不需要迁移的尾部不为空
loTail.next = null; // 尾部的Next为空
newTab[j] = loHead; // 新数组的j索引指向不需要迁移的链表
}
if (hiTail != null) { // 需要迁移的链表不为空
hiTail.next = null; // 需要迁移的链表的尾部的next制空
newTab[j + oldCap] = hiHead; // 新数组新索引指向需要迁移的链表的头部
}
}
}
}
}
return newTab; // 返回新链表
}
这里解释一下为什么需要将尾部的next设置为空。因为1.8以后的HashMap用的是尾插法。如果不制空,比如loTail的next很可能在hiTail中(而hiTail在新HashMap中是在另一个索引下),这时候可能会出现不同索引之间的关联,造成查询的时候可能会查询到本不在这个索引位置下的Node。