当我们 put 的时候，首先计算 key 的 hash 值，这里调用了 hash 方法，hash方法实际是让 key.hashCode()与 key.hashCode ()>>>16 进行异或操作,高16bit 补 0，一个数和 0 异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为 bucket 数组大小是 2 的幂,计算下标 index=（table.length-1)& hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或來简单处理减少碰撞，而且JDK8 中用了复杂度 O(logn)的树结构来提升碰撞下的性能。
putVal方法执行流程图
Public V put(K key, V value){
return putVal (hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16);
}
//实现 Map.put 和相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node < K, V > [] tab;
Node < K, V > p;
int n, i;
//步骤①：tab 为空则创建
//table 未初始化或者长度为 0，进行扩容
if((tab = table）== null ||(n = tab.length)== 0) n =(tab = resize()).length;
//步骤②：计算 index，并对 null 做处理
//（n – 1）& hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中（此时，这个结点是放在数组中)
if((p = tab[i =（n – 1）& hash]）== null）tab[i]= newNode(hash, key, value,null)；
//桶中已经存在元素
else {
Node < K, V> e;
K k;
//步骤③：节点 key 存在，直接覆盖 value
//比较桶中第一个元素(数组中的结点)的 hash 值相等，key 相等
if (p.hash == hash && ((k = p.key)== key || (key != null && key. equals(k))))
//将第一个元素赋值给 e，用 e 来记录
e = p;
//步骤④，判断该链为红黑树
// hash 值不相等，即key 不相等；为红黑树结点
// 如果当前元素类型为 TreeNode，表示为红黑树，putTreeVal 返回待存放的 node， e可能为null
else if (p instanceof TreeNode)
//放入树中
e=((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value);
//步骤⑤：该链为链表
//为链表结点
else {
//在链表最末插入结点
for(int binCount = 0;;++binCount) {
//到达链表的尾部
//判断该链表尾部指针是不是空的
if ((e = p.next)== null){
//在尾部插入新结点
p.next = newNode (hash, key, value, null);
//判断链表的长度是否达到转化红黑树的临界值，临界值为 8
if (binCount >= TREEIFY_THRESHOLD – 1）//-1 for 1st
//链表结构转树形结构
treeifyBin(tab, hash);
//跳出循环
break;
}
//判断链表中结点的 key 值与插入的元素的 key 值是否相等
if (e.hash == hash && ((k = a.key)== key || (key != null && key.equals(k))))
//相等，跳出循环
break；
//用于遍历桶中的链表，与前面的 e = p.next 组合，可以遍历链表
p= e；
}
}
//判断当前的 key 已经存在的情况下，
//再来一个相同的 hash 值、key 值时，返回新来的 value 这个值
if (e!= null){
//记录e的 value
V oldValue = e.value;
// onlyIfAbsent 为 false 或者旧值为 null
if (!onlyIfAbsent || oldValue == null）
//用新值替换旧值
e.value = value;
//访问后回调
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//结构性修改
++modCount；
//步骤⑥：超过最大容量就扩容
//实际大小大于阈值则扩容
if(++size>threshold) resize();
//插入后回调
afterNodeInsertion (evict);
return null;
}
1、判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；
2、根据键值 key 计算 hash 值得到插入的数组索引 i，如果table[i]==null,直接新建节点添加，转向⑥，如果 table[i]不为空，转向③；
3、判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖value，否则转向④，这里的相同指的是 hashCode 以及 equals；
4、判断 table[i]是否为 treeNode，即 table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 ⑤；
5、遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key 已经存在直接覆盖 value 即可；
6、插入成功后，判断实际存在的键值对数量 size 是否超过了最大容量threshold，如果超过，进行扩容。
Was this helpful?
0 / 0