Java中的HashMap

几天前，一个正在疯狂码代码的午后，钉钉上一个小伙伴问我：“你知道HashMap是在什么时候做bucket的初始化的么？”，我一边关注着手头的代码，一般含糊了一句：“new HashMap()的时候”，这个时候我想了想貌似不对，返回去看了看源码，发现并不是的。接下来就从几个方面分析分析JDK中HashMap的具体实现。

前言

在分析HashMap之前，先简单的提几个问题，以供大家思考：

• HashMap的bucket在什么时候初始化？
• HashMap采用哪种方式处理冲突？
• HashMap在什么时候扩容？
• HashMap的默认大小和loadFactor是多少？
• JDK 7和JDK 8在HashMap的实现上有什么区别？

如果各位老司机们有对这些问题持有疑问的，那可以带着这些问题来看后文的相关内容。接下来就分别分析JDK 7和JDK 8中HashMap的具体实现。

HashMap实现分析

数据结构

JDK中的HashMap采取开链法来处理冲突，所以：

1. 在JDK 7 中，HashMap的数据结构是数组+链表；

2. 在JDK 8 中，HashMap的数据结构由数组+链表变为数组+（链表或者rbtree）

JDK 7中的HashMap

• 构造方法
  

  JDK 7 的构造方法
  从构造方法中可以看出几个重要参数：capacity，loadFactor，threshold
  • capacity：容量，bucket数组长度，默认长度为16；
  • loadFactor：装载因子，默认值为0.75，它决定了bucket填充程度；
  • threshold：等于capacity * loadFactory，决定了HashMap能够放进去的数据量。

  当然，bucket的初始化并没有在这里完成，具体的初始化其实是在第一次调用put的inflateTable方法里完成的。接下来我们来具体看看put方法的具体实现。

• put方法的实现
  

  put方法实现
  put方法的具体流程如下：
  1. 如果bucket数组为空，调用inflateTable方法完成初始化；
  2. 判断待插入key是否为null：
  • key == null成立，调用putForNullKey方法完成数据插入，由此可以看出，HashMap的key是可以为null的；
  • key == null不成立，跳转到步骤3；
  3. 计算带插入key的hashCode；
  4. 根据hashCode按位与计算出所在bucket数组中的位置i；
  5. 遍历挂在bucket中位置i下的Entry链表，如果当前key已存在，更新它所对应的oldValue为value，并返回oldValue，否则，跳转到步骤6；
  6. 将key-value插入对应bucket中位置i下的Entry链表中，返回null。

  从put方法的流程中可以看到这样几个比较重要操作：inflateTable、hash和addEntry，接下来就详细分析它们的具体实现。

• inflateTable完成bucket初始化
  

  inflateTable实现

• hash
  

  hash实现
  从上图源码可以看出：
  1. hash方法为了让每一位都参与位运算，让相近的数最后通过hash能分散开并减少碰撞，采用了多次位移和异或，当然多一次与key的hashCode异或，也是为了尽量减少碰撞；
  2. hashSeed也是一个非常重要的角色，可以把它看成一个开关，如果开关打开，并且key的类型是String时可以采取sun.misc.Hashing.stringHash32方法获取其hash值。

  需要注意的是，hashSeed的默认值是0，hashSeed会在capacity发生变化的时候调用initHashSeedAsNeeded方法重新计算，具体代码如下：
  

  initHashSeedNeeded实现
  从上图代码可以看到，hashSeed的计算流程涉及到一个设定值Holder.ALTERNATIVE_HASHING_THRESHOLD，该设定值是通过JVM的参数jdk.map.althashing.threshold来设置的。

  注：
  在JDK 8 中，hashSeed已经被移除掉了，移除掉的原因是调用sun.misc.Hashing.randomHashSeed计算hashSeed时会调用方法java.util.Random.nextInt()，该方法使用AtomicLong，在多线程情况下会有性能问题。

• addEntry完成key-value插入
  

  addEntry实现
  从上图代码中可以看出，当size >= bucket的数据填充量threshold，需要扩容（resize），将HashMap的容量扩充为原来容量的两倍，接下来我们就来看看HashMap是如何做扩容的。

• resize实现
  

  resize实现
  从代码不难看出，resize分为两大步骤：
  • 扩容；
  • 将扩容前的所有数据transfer到扩容后的新的地址，在transfer数据中需要注意的是，如果hashSeed有变化，需要重新计算原有key的hash值。

到这里JDK 7的重要实现差不多分析完了，接下来我们再来看看JDK 8中相关实现。

JDK 8中的HashMap

• 构造方法
  

  构造方法实现
  JDK 8跟JDK 7一样，都不会在new HashMap()的时候初始化bucket，而是在第一次进行put操作的时候调用resize方法完成。当然，JDK 8对于HashMap的threshold计算同JDK 7是不一样的，从上图代码标红的位置可以看出，如果你通过带参数构造方法初始化HashMap时，会调用tableSizeFor方法计算出一个比initialCapacity大的第一个2的n次幂的值存入threshold。tableSizeFor的具体实现如下：
  tableSizeFor实现

• hash
  JDK 8 中在进行get和put操作时，会先根据key的hashCode进行再散列，再进行bucket对应节点位置计算，接下来我们来做个简单的运算：
  

  hash及下标计算
  从这个小例子可以看出：h >>> 16，高16位补0，由于任意数跟0异或不变，所以hash的作用就是高16位不变，低16位和高16位做异或运算，来达到减少碰撞的目的。

  hash方法的具体实现如下：

  
  hash方法实现
  

  当然，为了提高碰撞下的性能，JDK 8引入了rbtree来代替链表，将原有链表部分查询的时间复杂度o(n)提升为o(logn)，接下来我们就来看看JDK 8中的put方法的具体实现。

注：具体的红黑树实现将会在后续文章中给出，在本文不做详细分析。

• put方法的实现
  

  put方法实现
  从put的实现可以看出，put方法的所有操作都在putVal方法中实现，接下来我们来看看putVal的具体实现。

• putVal实现
  

  putVal实现
  从上图的代码可以看出，putVal具体流程如下：
  1. 如果当前bucket为空时，调用resize方法进行初始化；
  2. 根据key的hash值计算出所在bucket节点位置；
  3. 如果没有发生冲突，调用newNode方法封装key-value键值对，并将其挂到 bucket对应位置下，否则，跳转到步骤4；
  4. 如果发生冲突：
  • 如果该key已存在，更新原有oldValue为新的value，并返回oldValue;
  • 如果key所在的节点为treeNode，调用rbtree的putTreeVal方法将改节点挂到rbtree上；
  • 如果插入节点后，当前bucket节点下链表长度超过8，需要将原有的数据结构链表变为rbtree；
  5. 数据put完成之后，如果当前长度 > threshold，调用resize方法扩容。

到这里put方法的主要流程就结束了，接下来我们来看看JDK 8是如何来对HashMap扩容的。

• resize实现
  

  resize前半部分实现
  resize的前半部分主要完成了新的capacity和threshold的计算。从代码实现可以看出，每一次扩容，newCapacity和newThreshold均是扩容前值的两倍，为什么如此设计呢？还是照样举个例子来说明这样子设计的原因：
  resize后index计算
  从小例子可以看出，resize后，key所在bucket的节点位置保持不变。首先，table.length也就是capacity肯定是2的n次方，根据所在bucket节点下标计算公式：index = hash & (table.length - 1)，其实在进行&运算的时候，只是多了一个最高位1，那么新位置要么保持原位置不变，要么在原位置 + oldCapacity，这个设计的巧妙就在于节省了一部分重新计算hash的时间，而且hash值高位出现0和1的概率均等，在resize的过程又将节点平均分配到两个bucket节点。

  resize的后半部分对数据做了transfer，具体实现如下：

  
  resize后半部分实现

总结

到这里为止HashMap的相关实现分析就结束了，不难看出，JDK 8 比起JDK 7比较大的优化在：

1. 引入rbtree，在bucket节点下链表长度 > 8时将链表编程rbtree；
2. 优化hash和resize，减少resize带来的hash性能消耗。