HashMap扩容过程
一、开始分析
JDK版本基于JDK1.8以上,JDK1.8以上的HashMap使用红黑树+链表的组合方式//调用putVal方法,传入key,value
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
二、分析过程
先看官方说明
/**
* Implements Map.put and related methods.
*
* @param hash hash for key 存储的key的hash值
* @param key the key 存储的键值
* @param value the value to put 存储的值
* @param onlyIfAbsent if true, don't change existing value
* //判断是否需要替换旧值,每次插入重复的key,替换为最新的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) {
//这里定义了四个参数
// tab 定义一个空的Node 哈希桶数组
// n : 桶的长度
// p:存储在当前位置的元素
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table:hashmap中的重要的组成部分 transient Node<K,V>[] table;
//初始化HashMap
if ((tab = table) == null || (n = tab.length) == 0)
//一边初始化一边给n赋值
n = (tab = resize()).length;
//tab[0] 这种写法很好理解嘛，就是看hash位置有没有元素
if ((p = tab[i = (n - 1) & hash]) == null)
//将数据插入进去,数组的常规赋值方式
tab[i] = newNode(hash, key, value, null);
else {
//刚才if是没有元素,else 很显然,有元素了,这个时候需要链表或者红黑树了
Node<K,V> e; K k;
//判断当前key是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//直接替换
//判断p是不是一个树节点,是树了，就说明这个数据存储在红黑树上面
else if (p instanceof TreeNode)
//调用putTreeVal的方式将值添加到树里面
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//key没有,也不是红黑树,这个时候就是链表了
//一直for循环
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;
}
}
// e 是被替换出来的值,这个时候就替换值
if (e != null) { // existing mapping for key
//把当前的值给旧的值
V oldValue = e.value;
//看是不是需要替换值,不需要还把旧的值返回给你
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//空方法,允许自己去实现插入之后的一些操作
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size太大了,扩容
if (++size > threshold)
resize();
//空实现
afterNodeInsertion(evict);
return null;
}
多线程扩容死循环
HashMap扩容死循环只在JDK1.8之前出现，为什么呢，因为使用头插法导致的呀，JDK 1.8 之后使用尾插法解决了这个问题。
所以JDK1.7在多线程的情况下为什么会出现死循环呢?
采用头插法有个坏处，就是插入之后，元素的位置倒过来了
假设原元素的顺序是 1-2 , 扩容后顺序是 2-1
1，先看看jdk1.7扩容的时候怎么弄的
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); -----------------1
//使用头插法将需要转移的节点插入到hash桶中原有的单链表中
e.next = newTable[i]; -----------------2
//将hash桶的指针指向单链表的头节点
newTable[i] = e; -----------------3
//转移下一个需要转移的节点
e = next;
} while (e != null);
}
}
}
假设在多线程的情况下，去进行扩容
假设有两个线程 T1 和 T2
T1 在执行到e = e.next 的时候挂起，下一步就是T2去执行
T2 执行完了 把原有的 1 2 3 的顺序改成了 3 2 1
那么T1 再去执行的时候 , 发现原本喔的next 原本是 null 的 现在有值了，
那么一直next一直都会找到值，那么就造成死循环了。
说白了，就是扩容的过程中，有另外的线程把数组的next给改了
就是你要去洗头，别人把你洗发水换成沐浴露了，头永远洗不干净是一个道理。
那怎么解决死循环呢
1 升级JDK版本
2 使用HashTable
3 使用ConcurrentHashTable
4 使用Collections 返回一个线程安全的HashMap