阅读的源码为JDK1.8版本。
1.8中HashMap的底层结构为数组+链表+红黑树。

put()方法

可以看到put方法首先调用的是putVal方法,操作逻辑都写在putVal中。
image.png

putVal()方法:

putVal方法有五个参数传入,第一个参数为为经过hashMap的hash(也成为扰动函数),对k进行进一步的处理,防止一些处理的较差的hashcode,减少哈希碰撞;第三个参数onlyIfAbsent当为false时,代表如遇到相同的key时新值覆盖原值,为true时不替换;最后一个参数evict,目前看来只有在其初始化时为false,表示其为创建模式,其余时候均为true,在put方法内,evict参数只在倒数第二行的方法afterNodeInsertion(evict)作为参数传入,而且阅读源码发现这个方法的方法体为空,网上查资料说是用于方法回调,这个参数不是本章的重点不做更多讨论。

hash()方法

image.png
详解putVal()
image.png
image.png

  1. 会先判断此时的table是否为空,如果是第一次调用,那么table为空,会先调用resize()初始化大小为16。
  2. 然后根据此时的hash值与数组的长度减-1进行与运算出他在数组中的位置,判断此位置是否为空,若为空直接写入。
  3. 如果不为空进入else中判断:这里分为三种情况:
  4. 如果新值与数组中第一个值的hash值相同且进一步通过equals比较发现它们也相等。则通过Node类型的e把此时的原值记下来。注意:此时还不进行修改覆盖,覆盖操作放在后面。
    这里判断key是否相等的方法源码如下
    image.png
  5. 在判断此时的节点是不是一个树节点,是的话,将其以红黑树节点的方式插入。
  6. 如果以上判断都不成立证明其是一个链表结构,此时对其从其往后遍历比较。有两种方法推出遍历:
  7. 一种情况是当遍历到最后一个节点还未找到相同的数据,则在末尾插入新值,这里有一个注意点是如果此时链表的长度超过8,则进入treefiyBin方法,判断此时数组的长度是否小于64,超过则将链表转换为红黑树,未超过则继续扩容,增加数组长度(扩大为原来的两倍)。
  8. 另一种退出循环的情况,遍历中途遇到了相等的key,此时也是通过e记录这个位置,然后退出循环遍历。判断方法与第四步一样。
  9. 然后判断若之前用于标记的e若不为空,判断一开始传入的参数,onlyIfAbsent是否为false,若是,则用新值替换旧值。
  10. 最后modcount++;判断是否需要扩容,若不需要扩容返回null,方法执行结束。

resize()方法

下图为resize()方法截取的一部分,是扩容后重新将旧值写入新结构的方法
image.png
可以发现这里与jdk1.7时的方法有明显不同。
jdk1.7需要循环遍历每一个键值对,将他们一一与新的哈希表重新计算位置放入。
而在1.8中可以看到,放入的位置只有两种可能,一种是原数组的位置,另一个是原数组的位置加原数组的长度。
原因是巧妙地运用了hashmap数组长度始终为2的幂次,每次扩容相当于二进制前面加了一个1,这使得旧值与新老数组长度-1进行hash与运算时只需考虑,新增那一位的情况,若与运算(&&)得到的结果一样,则保持原位置;不一样则是原位置+原数组的长度。(即将e的hash值与老数组容量进行与运算,为0则不用移动,为1则需要移动)

modCount到底是个啥?有啥用?

在本篇和上一篇解读ArrayList源码中都出现了modCount这个词,它到底是个啥呢?
查阅资料发现,发现它和Fail——Fast机制有关,通常用于线程不安全的集合类中涉及到增删改时都会用到。它在初始化迭代器时会被用到,被赋值给exceptedModCount若在运行过程中,map被其他线程操作,导致modCount和exceptedModCount不一样,则会即刻报错,抛出ConcurrentModificationExceptions异常。

Q.E.D.