什么时加载因子?为什么加载因子时0.75?
加载因子也叫扩容因子或负载因子,用来判断什么时候进行扩容的,假如加载因子是0.5,
HashMap
的初始化容量是16,那么当
HashMap
中有16*0.5=8个元素时,
HashMap
就会进行扩容。
那加载因子为什么是0.75而不是0.5或者1.0呢?
这其实是出于容量和性能之间平衡的结果:
- 当加载因子设置比较大的时候,扩容的门槛就被提高了,扩容发生的频率比较低,占用的空间会比较小,但此时发生Hash冲突的几率就会提升,因此需要更复杂的数据结构来存储元素,这样对元素的操作时间就会增加,运行效率也会因此降低;
- 而当加载因子值比较小的时候,扩容的门槛会比较低,因此会占用更多的空间,此时元素的存储就比较稀疏,发生哈希冲突的可能性就比较小,因此操作性能会比较高。
所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。
.扩容
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;
}
//扩大容量为当前容量的两倍,但不能超过MAXIMUM_CAPACITY
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
//如果初始化的值为0,则使用默认的初始化容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的容量等于0
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
table = newTab;
//原数据不为空,将原数据复制到新 table中
if (oldTab != null) {
//根据容量循环数组,复制非空元素到新 table
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
//链表复制,JDK1.8扩容优化部分
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;
}
// 原索引 + oldCap
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;
}
// 将 原索引+oldCap 放到哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
从以上源码可以看出,JDK1.8在扩容时并没有像JDK1.7那样,重新计算每个元素的哈希值,而是通过高位运算(
e.hash&oldCap
)来确定元素是否需要移动,比如key1的信息如下:
- key1.hash = 10 0000 1010
- oldCap = 16 0001 0000
使用
e.hash&oldCap
得到的结果高一位为0,当结果为0时表示元素在扩容时位置不会发生任何变化,而key 2信息如下:
- key2.hash = 10 0001 0001
- oldCap = 16 0001 0000
这时候得到的结果高一位为 1,当结果为 1 时,表示元素在扩容时位置发生了变化,新的下标位置等于原下标位置 + 原数组长度
HashMap死循环分析
以JDK1.7为例,假设
HashMap
默认大小为2,原本
HashMap
中有一个元素key(5),我们再使用两个线程:t1添加元素key(3),t2添加元素key(7),当元素key(3)和key(7)都添加到
HashMap
中之后,线程t1在执行到
Entry<K,V>next=e.next
;时,交出了CPU的使用权,源码如下:
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){
e.hash = null==e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash,newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
那么此时线程t1中的e指向了key(3),而next指向了key(7);之后线程t2重新rehash之后链表的顺序被反转,链表的位置变成了key(5)→key(7)→ key(3),其中 “→” 用来表示下一个元素。
当 t1 重新获得执行权之后,先执行
newTalbe[i] = e
把 key(3) 的 next 设置为 key(7),而下次循环时查询到 key(7) 的 next 元素为 key(3),于是就形成了 key(3) 和 key(7) 的循环引用,因此就导致了死循环的发生
当然发生死循环的原因是JDK1.7链表插入方式为首部倒序插入,这个问题在JDK1.8得到了改善,变成了尾部正序插入。
Sun公司认为这不是一个问题,因为
HashMap
本身就是非线程安全的,如果要在多线程下,建议使用
ConcurrentHashMap
替代,但这个问题在面试中被问到的几率依然很大,所以在这里需要特别说明一下。
在 JDK 1.7 时 HashMap 是由数组和链表组成的,而 JDK 1.8 则新增了红黑树结构,当链表的长度大于 8 并且容量大于 64 时会转换为红黑树存储,以提升元素的操作性能。同时还介绍了 HashMap 的三个重要方法,查询、添加和扩容,以及 JDK 1.7 resize() 在并发环境下导致死循环的原因。