HashMap链表插入方式为何从头插改成尾插

发表于 更新于 分类于

HashMap是我们最常用的一个类，我们也知道这个类是非线程安全的，尤其是在 Java1.7 中，还有可能出现环，造成死循环，通过这篇文章，你可以了解到为什么会出现这种问题。

Java7 的 HashMap 原理是 数组 + 链表，如果 hash 一致，就头插到链表中，头插就是导致成环的关键原因。Java8就改成了尾插，保持相对位置一致。

源码解析

下面先贴出涉及的方法，一些会在注释上解释。

你可以快速在这个网站上查找 Java1.7 HashMap 的源码http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/e947a98ea3c1/src/share/classes/java/util/HashMap.java， 而不必去下载源代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 当需要扩容时，会执行此方法，参数是新的容量
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];
    // 重新hash，进行迁移数据
    transfer(newTable);
    // 将原本的数组指向新的扩容数组
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}


/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    // 对老数组内的元素进行遍历
    for (int j = 0; j < src.length; j++) {
        // src[j]是该链表的头
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;  // 代码块①
                int i = indexFor(e.hash, newCapacity);
                // 将原先的头取出来 并添到 e 的后面
                e.next = newTable[i]; // 代码块②
                // 将 e 设置为头元素
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

/**
 * Returns index for hash code h.
 */
// 找到此 hash 值对应的数组下标
static int indexFor(int h, int length) {
    return h & (length-1);
}

举个栗子

举个在多线程情况下会产生环的例子：

  1. 图一展示了初始状态，容量为2，现在有 a、b 两个元素。（请忽略怎么没扩容这样的细节）
    图一
  2. 现在有两个线程同时要添加一个，且都会引发扩容。
  3. 线程1先执行，在执行完代码块①后停下来，让线程2去执行。此时，线程1看到的状态是如图二所示的，此时还没开始重新hash迁移数据。
    图二
  4. 线程2执行，且执行完了所有的步骤，那么在线程2中的状态如下：（假设a、b新hash出来的下标是3）
    1. 第一次循环: e=a, next=e.next=b, i=2(假设), newTable[2]=a, e=b
    2. 第二次循环: e=b, next=b.next=null, i=2, newTable[2]=b, e=null
    3. 循环结束
      图三
  5. 接下来又是线程1，从代码块①之后开始执行，状态如下：
    1. 第一次循环: e=a, next=e.next=b, i=2(假设), newTable[2]=a, e=b
    2. 第二次循环: e=b, next=b.next=a, i=2, newTable[2]=b, e=a ，这里出现了错误，由于线程2导致 b.next = a，正确情况应该是 null，导致了第三次循环
    3. 第三此循环: e=a, next=a.next=null, i=2, e.next=newTable2 ，在执行代码块②时产生环， newTable[2]=e=a ，又把头换成a了
    4. 循环结束

图四