上一篇说到空HashMap的put函数执行过程，今天我们继续看下非空HashMap的put函数执行过程。上一篇链接我贴出来，供大家快速跳转过去。
一起精读源代码系列(1) HashMap(一) put函数的执行过程
那么当HashMap中已经存有元素的时候会发生什么呢？话不多说，直接上putVal函数的前几行代码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
上篇分析的HashMap为空所以会进这行if
(tab = table) == null || (n = tab.length) == 0
这次并不会进，那下一行的if就需要判断一下了，因为计算出来的数组下标对应的节点p既可能为null，也可能不为null。打个比方
//代码片段1
Map<Integer,String> map1 = new HashMap<>();
map1.put(1,"1");
map1.put(2,"2");
//代码片段2
Map<Integer,String> map2 = new HashMap<>();
map2.put(1,"1");
map2.put(1,"2");
代码片段1执行的时候第二次put这里的p就是null，而代码片段2执行的时候第二次put这里的p就不是null。还是老规矩，分两种情况一行行分析。
当节点p为null的时候，我们可以看到这里会执行newNode函数。也就是这么一个玩意：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
这个已经分析过了，就是新建了一个Node节点。那么当p不为null的时候继续往下看。先来看第一个if会不会进
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
按照从左到右依次执行的顺序，p.hash==hash这个肯定为true，因为key是一样的(从代码片段1可以看到，都是1)，p.key==key这个也是true，所以这整个表达式一定是true，所以就会执行e=p，把节点p赋值给e。这里暂时还看不出什么，我们继续往后看。那进了这个if，后面的else都直接跳过即可。来到最后
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
很明显会进到这里，e的value其实就是p的value，这时候会赋值给oldValue。下面又有一个if，其中的onlyIfAbsent这个参数传进来是false。参考putVal函数的注释
* @param onlyIfAbsent if true, don't change existing value
这意思就是如果这个参数传了true，则表示put同一个key的键值对进HashMap的时候不替换原来的值。这个值默认为false，所以if的条件是true，就会用新value替换原来的value了。同样的，后面也执行了一个空函数afterNodeAccess（这个函数在linkedHashMap有实现），并且这种情况下会把老的value返回。这样我们就发现了，put函数其实是有返回值的。
好的，这下我们明白了同样key不同value的替换过程。那接下来我们分析如果发生了所谓的hash冲突，HashMap会如何处理。什么是Hash冲突呢？上一篇我们聊到，HashMap会根据key计算出hash值，然后再与n-1按位与操作计算出在数组中的下标，有了下标，就往数组中添加一个Node。那如果不同的key得到的hash值相同的时候就会发生hash冲突。我写了一个简单的类来模拟hash冲突的过程。
import java.util.Objects;
public class User {
private String name;
public User(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return Objects.equals(name, user.name);
}
@Override
public int hashCode() {
if (name.equals("wang") || name.equals("WANG")) {
return 0x6666;
}
return super.hashCode();
}
}
hashcode函数的意思就是当name为wang或者WANG的时候，hash值设置为同样的0x6666。equals函数的意思就是当两个对象的name字段相等时就认为两个对象相等。
好，那接下来我们用这个类做一些事情。我们分别用wang和WANG作为HashMap的key，看看会发生什么。
User user1 = new User("wang");
User user2 = new User("WANG");
Map<User,String> map = new HashMap<>();
map.put(user1,"30");
map.put(user2,"32");
很显然，这里的user1和user2用了wang和WANG作为key，根据我们上面的设定，两个对象的hashCode值是一样的。下面贴出这种情况下HashMap的执行过程代码
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，p.next为null，也就是说p是链表的尾结点，或者说链表中的最后一个节点。这段代码其实就是在循环查找链表直到链表的尾部。我们的代码片段刚好符合这个逻辑，所以会进到这个if。p.next=newNode，也就是说往链表的尾部又插入了一个元素，然后break跳出for循环。因此我们可以得出第一个结论，当HashMap中发生hash冲突的时候，会找到数组的下标，然后往数组的下标处对应的链表尾部插入一个节点。
再往下一段代码就是同样key的一个value替换过程，之前也分析过，就不再多做分析了。
到了这里，大家应该能理解数组和链表在HashMap中的应用了。那么我们也会思考一个问题，在某种场景下链表长度可能会越来越大，是不是就有可能影响到HashMap的查询效率呢？甚至，在极端情况下，HashMap的查询时间复杂度可能会由O(1)退化到O(n)，这可是很严重的性能故障。为了解决这个问题，JDK1.8引入了红黑树。红黑树是一种平衡的二叉查找树，查询、插入、删除节点的时间复杂度均为O(logn)，是非常高效的一种数据结构。putVal函数中涉及到红黑树的代码如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
也就是当binCount这个值大于等于7或者链表长度大于等于8的时候，会调用treeifyBin()把链表转为红黑树。红黑树的代码不太好写，还涉及到数据结构和算法相关的知识，这不在本文的讨论范围，所以我不做太多的扩展，有兴趣的同学可以下去深入研究一下。
我们来总结一下整个put过程中数组、链表、红黑树之间的关系。首先数组的下标是通过key值计算出来的，数组的value就是Node节点，当没有hash冲突的时候，Node节点的next是null，当发生了hash冲突，Node节点的尾部会新增一个节点，链表长度加1，而当链表长度大于等于7，会转化为红黑树。
理解了这些之后，我们最后再来看一下put过程中另一个非常关键的点，HashMap扩容。随着我们不断往HashMap中添加元素，hashMap的容量不足以容纳我们放进去的数据的时候，自然就需要扩容了。相关代码：
if (++size > threshold)
resize();
很显然，当hashMap的size大于阈值的时候，会执行一次扩容。上一篇我们说到HashMap的默认阈值为12，也就是在默认情况下，当hashMap的容量到达最大默认容量16*0.75的时候，会进行扩容操作。0.75是指HashMap的负载因子。我先来解释下这个负载因子的作用。在散列表这种数据结构里面，有一个名词叫做装载因子，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。装载因子的计算公式如下:
散列表的装载因子=填入表中的元素个数/散列表的长度
在HashMap中，定义了一个默认的装载因子0.75f。为了计算方便，又定义了阈值threshold，初始值为默认最大容量16乘以默认装载因子0.75得到12。当HashMap中的容量第一次达到12以上的时候，就会执行一次扩容，我们就从第一次扩容为入口往下看扩容过程的代码。直接来到resize函数的第681行到689行
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
可以看出，当原来的容量大于0，会进到这里。看第一个if，原容量大于等于最大容量MAXIMUM_CAPACITY，查看源码可知，这个参数为2³º，这个场景不涉及，所以不会进。下面的else if，说的是原容量扩大一倍之后小于最大容量且原容量大于等于默认初始容量16，假如我们原容量为16，这个时候触发扩容，扩大一倍是32，满足这个else if的条件，所以得到newCap也就是新容量为32，newThr也就是新阈值为原阈值12扩大一倍得到24。由此可得，经过一次扩容之后，容量和阈值都扩大了一倍。进了681行的if，所以后面的else都不会进，直接跳到701行以后。由于这是一个for循环，没办法再缩短了，只能一起贴出来
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
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
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;
}
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
这个地方非常复杂，我会一行行解释。首先是把新阈值赋值给了成员变量threshold，然后新建了一个容量是新容量大小的Node数组并且赋值给成员变量table。下面的过程就是把原数组搬迁到新数组的过程，我们都知道数组的搬迁其实性能很一般，那这里就可以看下HashMap的源码是如何实现旧数组到新数组的数据搬迁的。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
这里就不多说了，就是一个数组的遍历，只不过把旧数组中的值赋值给到e之后，就把这个值置为null了。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
这里就是往新数组中插入数据的过程，如果e.next为null，意思就是这个地方的Node没有引申链表，也就是说没有发生hash冲突。那e.hash&(newCap-1)计算出来的值会作为旧数据在新数组的下标，上一篇我们分析了，由于newCap是2的x次方，所以这里的表达式其实就是e.hash对newCap进行取模运算。数据从旧表搬移到新表之后，即便下标发生了变化，也不会影响到数据的查询，因为在HashMap的get函数里，扩容之后，相应的取下标的计算也变了，这个我们后面会进行分析。
接下去继续，如果e.next不为null，这里我们先跳过红黑树直接进入到链表层面的分析。用do while对链表进行遍历这里不多说，重点在于一个表达式：(e.hash & oldCap) == 0，相信看过HashMap源码的同学很多人都无法理解这个表达式的意义。下面我带大家进行详细的推导
- 我们已知容量肯定是2的整数次幂，所以oldCap转为二进制就是类似10000这样的值；
- 如果按位与得到的值为0，则表示e.hash转为二进制之后在oldCap对应的1的位置的值一定是0，其他位置可以随意，例如01101这个hash值，又例如1101101这个hash值。只有在oldCap对应1的位置的值是0的前提下，按位与得到的结果才会是0；
- 这种情况下，我们分别计算e.hash&(oldCap-1)和e.hash&(2*oldCap-1)，也就是在(e.hash & oldCap) == 0的前提下计算扩容前后某个数据在数组中的下标。当2的x次方减1之后，转为二进制会得到低位全是1的数据，扩容其实就是二进制数据比扩容前多了一个1，而根据第2点的分析，在多的这个1的位置上e.hash对应的值是0，因此按位与操作扩容前后得到的结果是一样的，也就可以推导出4的结论;
- 在(e.hash & oldCap) == 0前提下，e在新旧数组的位置不变。
在这种情况下，把原数组搬移到新数组的时候，下标都不需要改变。只需要取出当前节点的头节点赋值到新节点即可。
接下来我们分析(e.hash & oldCap) != 0的时候。推导过程如下
- 我们已知容量肯定是2的整数次幂，所以oldCap转为二进制就是类似10000这样的值；
- 如果按位与得到的值不为0，则表示e.hash转为二进制之后在oldCap对应的1的位置的值一定是1，其他位置可以随意，例如11101这个hash值，又例如1111101这个hash值。只有在oldCap对应1的位置的值是1的前提下，按位与得到的结果才不会是0；
- 这种情况下，我们分别计算e.hash&(oldCap-1)和e.hash&(2*oldCap-1)，也就是在(e.hash & oldCap) != 0的前提下计算扩容前后某个数据在数组中的下标。当2的x次方减1之后，转为二进制会得到低位全是1的数据，扩容其实就是二进制数据比扩容前多了一个1，而根据第2点的分析，在多的这个1的位置上e.hash对应的值是1，因此按位与操作扩容前后得到的结果就是高位上多了一位1。高位多了一个1也就意味着换算为10进制多了2的x次方，也就是多了一个oldCap的值，可以推导出4的结论。
- 在(e.hash & oldCap) != 0前提下，e在新旧数组的位置等于原位置加oldCap。
那到此为止，整个扩容过程就分析完毕，put函数也分析的差不多了。
下期预告，一起精读源代码系列(2) Android Handler系列源码分析。基于Android8.0。
网友评论