一、背景
jdk1.8
二、hashMap的put主要流程
1、hash()过程,经历了rehash()
2、执行put流程前的初始化定义,如初始化桶,数组长度等等
3、执行开始,验证桶是否初始化过,如果没有则扩容并重新赋值数组长度
4、通过桶数组长度、hash值的&运算,获取对应的数组下标
5、验证对应链表上的头节点,如果为空,就不用走接下来的逻辑,直接创建节点即可
6、如果不为空,那么确定当前节点已经处于链表上了,那么对头节点进行比较,如果头节点正好是当前值的节点，那么替换值即可.
7、如果头节点不是,需要确认当前链表结构是否为树形结构,即头节点是否为树形节点,如果是树形节点,调用putTreeVal()即可.
8、如果头节点也不是树形节点,那么就有趣了,hashMap会直接来个死循环遍历当前链表,知道获取到相同的节点为止,如果匹配到了,那么就将值进行替换.
9、如果直到尾结点也没有匹配上，说明当前节点在之前不存在,那么hashMap就会为当前值创建一个节点,并且判断是否需要进行树化,如果满足树化条件,那么会对当前链表进行树化.
三、hashMap的源码解析
如果直接看原生的hashMap不好理解,可以换成大家平时编码的方式进行解读,
如下:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//执行流程前的初始化定义
//定义桶数组
Node<K,V>[] tab = table;
//定义当前key对应的节点
Node<K,V> p;
//初始化数组长度
int n = tab.length;
//开始执行
//如果桶不存在,初始化扩容
if (tab == null || n == 0){
//扩容并重新赋值数组长度
n = (tab = resize()).length;
}
//将数组长度减一与hash值做&运算,得到0到数组长度减一之间的数字【如数组长度为16,那么得到的i是0~15之间的数字】
//i就是对应的数组桶下标
int i= (n - 1) & hash;
//通过得到数组桶坐标的链表头节点
p = tab[i];
//如果头结点为空,创建新节点
if (p == null){
tab[i] = newNode(hash, key, value, null);
} else {
//如果不为空,那么确定节点已经位于链表上了
Node<K,V> e; K k;
//和链表中的头节点比较,如果相同,那么就取得了相同key的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){
//如果是树节点,那么找到头部节点为树节点,那么将对应的树中的节点进行赋值
//如果返回了e = null,表示在树上新创建了一个节点 - 详情见hashMap - putTreeVal详解
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
//匹配链表上的节点,如果能匹配上，就返回对应节点,
//如果匹配不上,那么创建一个新的节点,并且验证是否需要树化
//树化的条件:
//condition1: 大于等于阈值-1即7;
//condition2: 数组长度大于MIN_TREEIFY_CAPACITY即64
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;
}
}
//如果在链表中有值,那么将值替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//hashMap未实现,linkedHashMap因为带序问题会实现
afterNodeAccess(e);
return oldValue;
}
}
//修改次数加一
++modCount;
//如果添加元素之后的大小超过了阈值,需要扩容
if (++size > threshold)
resize();
//hashMap没有实现,linkedHashMap实现了，因为是带序的
afterNodeInsertion(evict);
return null;
}
四、思考
1、rehash()的目的?
2、什么时候进行扩容?
3、如何扩容?倍数?一定是这么多倍吗?为啥这么多倍？
4、树化的条件?
未完待续......
网友评论