HashMap的实现原理

概述

HashMap是Java中对Map接口的实现类，是最常用的实现类中之一。主要有以下几个特性：

  • HashMap中的key 和 value 都允许为null， 但最多智能拥有一个null的key
  • HashMap不保证顺序性
  • HashMap非线性安全

HashMap的数据结构：

HashMap内部是以数组+链表的方式存储的数据。

image-20210904213431065

HashMap的数组中，每个元素称之为“桶”。需要注意的是，这个“桶”并不等同于“键值对（Entity）”。至于它是什么请往下看。

初始化

HashMap在初始化时会创建一个Entity的数组。其个数为16。其源码类似下面的代码：

1
2
3
4
5
6
7
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}

其中key和value不必多说，不过它还包含了一个next属性，这说明它可以组织成一个链表结构。

put()方法

put方法被调用时，HashMap会根据key计算出对应的hashcode，然后根据hashcode确定该Entity应该存放在数组的哪个位置（应该放在哪个桶里）。

这种设定有一个问题：实际引用中有可能会发生hash碰撞（即两个数据虽然内容不同，但其hashcode有可能是相同的）！因此，HashMap如果发现hashcode已经存在，则会对key进行euqals对比：

  • equals结果是true，则认为确实是同一个key，然后将新的value覆盖旧的value（此时put方法将会返回旧value值）。
  • equals结果是false，则认为是hash碰撞，此时会将之前的Entity作为新Entity的next，此时形成一个链表，新Entity则处在链表的首位。

因此，所谓的“桶”就是数组每个位置放置的“链表”。

get()方法

如果理解了上述的put逻辑，则get方法就很容易理解。主要有以下几个步骤：

  • 根据key计算hashcode，然后得出其数组下标（位置）。
  • 去对应位置获取桶（链表）。
  • 从头到尾遍历链表的每一个Entity，通过equals方法找到对应的Entity。

上述的过程中有一个点未详细说明：如何根据key的hashcode计算出对应的数组坐标呢？

HashMap的内部实现用了一个非常巧妙的方法。HashMap的初始容量被定为16，且每次增长都是2的倍数。这样设计的目的是要保证存入map中的元素尽量分散，尽量避免出现桶中出现链表，这可以有效降低数据查询时的处理速度。

key是这么一步步转化成数组下标的：

第一步：Object Key –> int hash

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果key是null，则其hash为0；否则便将 hashcode 与 hashcode的高位 做 异或运算。这是为了尽量避免“低位不变，高位变化”时造成的hash冲突。

第二步：hash –> i

上一步计算出的hash是个长度较长的二进制数字，而通常情况下HashMap的底层数组长度（length）较小，因此如果我们进行 hash % length 计算，则一定能得到一个下标，且相对比较分散。而在源码中使用了性能更高的算法：

1
i = (length - 1) & hash

这个公式对hash和length进行了按位与运算，等价于取余。

为什么底层数组的长度总要是2的n次方呢

这时就能说清楚另外一件事情：为什么底层数组的长度总要是2的n次方呢？

下图是个示例：

img

可以看到，如果数组长度是2的n次方，那么length-1的二进制表示中，一定所有位都是1，此时取&运算则可以完整保留hash响应位置的二进制数据。相反的，如果数组长度不是2的n次方，则出现hash碰撞的可能性大大提高。

JDK8中HashMap的改进

上文曾提到“桶”的概念。其实这个概念在JDK8中才是真正有意义的。因为JDK7中，原始数组的每个元素都一定是个链表（链表的节点一个或者多个），而到了JDK8的时候就不一定是链表了。

JDK8对存储方式进行改进的原因很简单：如果在一个HashMap中，有很多Key发生了碰撞的时候，就会产生一个超级长的链表。那么在数据查询的时候就会花费O(n)的时间。所以，JDK8中HashMap采用了“桶+链表/红黑树”数据存储方式：如果链表的长度大于等于8时，其内部便会将链表转化为红黑树的结构。红黑树的查询时间是O(log n)。

由于数据存储方式发生变化，因此列表扩容时也会发生一些变化。具体细节请看下一篇HashMap的扩容。

扩容机制

为了方便说明，这里明确几个名词：

  • capacity 即容量，默认16。
  • loadFactor 加载因子，默认是0.75
  • threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

什么时候触发扩容？

一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。

HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（2^31^ - 1) ，即永远不会超出阈值了)。

JDK7中的扩容机制

JDK7的扩容机制相对简单，有以下特性：

  • 空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。
  • 有参构造函数：根据参数确定容量、负载因子、阈值等。
  • 第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。
  • 如果不是第一次扩容，则 [公式] ， [公式] 。

JDK8的扩容机制

JDK8的扩容做了许多调整。

HashMap的容量变化通常存在以下几种情况：

  1. 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
  2. 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 [公式] 。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！）
  3. 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

此外还有几个细节需要注意：

  • 首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；
  • 不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；

JDK7的元素迁移

JDK7中，HashMap的内部数据保存的都是链表。因此逻辑相对简单：在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值（也有可能不计算），找到新数组中的对应位置，以头插法插入新的链表。

这里有几个注意点：

  • 是否要重新计算hash值的条件这里不深入讨论，读者可自行查阅源码。
  • 因为是头插法，因此新旧链表的元素位置会发生转置现象。
  • 元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转）。

JDK8的元素迁移

JDK8则因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

img

数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图：

img

因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了。

JDK8的HashMap还有以下细节：

  • JDK8在迁移元素时是正序的，不会出现链表转置的发生。
  • 如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。

HashMap扩容死循环问题

  • 当插入一个新的键值对时，会根据key对HashMap底层数组长度取模，得到键值对存放的数组下标，然后调用addEntry() 函数把这个键值对插入到这个下标所在的链表中

    1
    2
    3
    4
    5
    6
    void addEntry(int hash, K key , V value, int bucketIndex){
        Entry<K, V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key , value, e);
        if(size++ >= threshold)			// 如果键值对个数超过hashmap当前的阈值
            resize(2 * table.length)	// 调整resize()函数进行扩容
    }

  • 在这个addEntry() 函数中，会判断键值对个数是否超过了HashMap当前容量的阈值，如果超过了，则说明需要扩容，接下来就调用resize() 函数扩容为原来的两倍

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
              return;
         }
        Entry[] newTable = new Entry[newCapacity];  // 创建一个新数组
        transfer(newTable);        // 把老数组中的所有键值对都拷贝到新数组中
        table = newTable;        // 修改老数组的指向，把老数组指向新数组，完成扩容
        threshold = (int)(newCapacity * loadFactor);
    }

  • resize()函数会先创建一个新数组，然后调用 transfer() 函数把老数组中的所有键值对都拷贝到新数组中，最后修改老数组的指向，把老数组指向新数组，完成扩容。

    扩容过程中会出现循环链表的情况就是多个线程在执行 transfer() 函数导致的，下面看看 transfer() 函数的代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void transfer(Entry[] newTable) {
        Entry[] src = table;        // 老数组
        int newCapacity = newTable.length;     // 新数组的长度
        for (int j = 0; j < src.length; j++) // 遍历老数组，把老数组中所有键值对拷贝到新数组
            Entry<K,V> e = src[j];    // 记录下老数组第 j 个链表，接下来会链表上的键值对都拷贝到新数组
            if (e != null) {        // 如果链表不为空才需要拷贝
                src[j] = null;        // 先老数组第j个链表置为空链表
                do {                // 循环遍历刚才记录下来的链表，把所有键值对都采用头插法插入到新数组对应链表
                    Entry<K,V> next = e.next;        // 记录下当前结点的下个结点
                    int i = indexFor(e.hash, newCapacity);    // 求出该键值对在新数组的下标,即该键值对应该被插入到新数组第几个链表
                    e.next = newTable[i];    // 把结点的next指针指向新数组的第i个链表头结点
                    newTable[i] = e;    // 新数组第i个链表的头结点前移，指向当前结点
                    e = next;        // 把指向当前结点的指针后移
                } while (e != null);
            }
        }
    }

  • 其中最关键的就是其中的 do while()循环，这里面就是会发生循环链表的代码。

现在先走一遍正常扩容的流程,假设有下面这个HashMap, 假设数组大小为2

img

现在需要对它进行扩容，扩容后数组大小为原来的两倍，创建一个大小为4的数组

img

假设a、b两个数扩容后刚好又hash冲突了，即又在同一个链表中，所在下标为3；c在下标为1的链表中。下面开始扩容。

e指针指向了老数组的第1个链表

执行上面的do while循环，第一轮循环：

img

第二轮循环：

img

第三轮也是最后一轮循环，前面已经假设结点 c 将在新数组中的第二个链表

img

至此，老数组中的健值对已全部拷贝到新数组中

多线程环境中扩容

假设在第 二 次循环中的第二步（执行完e.next = newTable[i]；）后当前线程的时间片刚好用完了，当前线程被挂起，这时刚好又有一个线程 P2 也来执行扩容操作，它并不会从第二步开始执行，而是重新从第一步开始执行，加入新线程后的扩容图为

img

可以看到，线程2扩容之后的newTable中的单链表形成了一个环，后续执行get操作的时候，会触发死循环，引起CPU的100%问题。

扩容后，元素是如何重新分布的

  • HashMap的初始化是在插入第一个元素时调用resize() 完成的

  • 不指定容量，默认容量为16

  • 指定容量也不一定按照你的值来，会经过tableSizeFor转成不小于输入值的2的n次幂

    tableSizeFor转换成2的n次幂不是直接赋值给capacity，而是先将值暂时保存在threshold，见源码457，然后在put第一个元素resize时，婉转的传递给newCap

  • put元素时，元素的位置取决于数组的长度和key的hash值按位与的结果 i = (n - 1) & hash

  • 如果这里没有元素直接放在这里

  • 如果有，判断是不是键冲突，如果一样就新值覆盖旧值

  • 如果有且不是键冲突，则将其放在元素的next位置，判断元素长度是否大于8，大于8进行树化

  • 只有当size大于了扩容阈值 size > threshold， 才会触发扩容，扩容前，当前元素已经放好了

  • 扩容时，容量和扩容阈值都翻倍，必须小于 1<<30

  • 扩容时，元素在新表中的位置分情况

  • 当元素只是孤家寡人即元素的next==null时，位置为e.hash & (newCap - 1)

  • 当元素有next节点时，该链表上的元素分两类

    • e.hash & oldCap = 0的，在新表中与旧表中的位置一样
    • e.hash & oldCap != 0的，位置为旧表位置+旧表容量

  • 当前节点时树的话

    • (e.hash & bit) == 0 在新表中与旧表中的位置一样
    • (e.hash & bit) != 0 位置为旧表位置+旧表容量
    • 在新的newCap中，判断阶段如果节点数小于6进行树退化，重新树化