HashMap重新散列/调整容量

Question

HashMap 的文档中有这样一句话：

如果初始容量大于最大条目数除以负载因子，就不会发生任何重新哈希操作。

请注意文档中使用的是重新哈希而不是重新调整大小——即使只有在内部存储桶的大小增加为原来的两倍时才会发生重新哈希。

当然，HashMap 提供了这样一个构造函数，我们可以在其中定义这个初始容量。

构造一个具有指定初始容量和默认负载因子（0.75）的空 HashMap。

好的，看起来很简单：

// these are NOT chosen randomly...    
List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY", 
          "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");

int maxNumberOfEntries = list.size(); // 9
double loadFactor = 0.75;

int capacity = (int) (maxNumberOfEntries / loadFactor + 1); // 13

容量为13（实际上是16，这是下一个二次幂），这样我们就保证了文档部分关于不重新哈希的内容。好的，让我们来测试一下，但首先介绍一种将进入HashMap并查看值的方法：

private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable {

    Field table = map.getClass().getDeclaredField("table");
    table.setAccessible(true);
    Object[] nodes = ((Object[]) table.get(map));

    // first put
    if (nodes == null) {
        // not incrementing currentResizeCalls because
        // of lazy init; or the first call to resize is NOT actually a "resize"
        map.put(key, value);
        return;
    }

    int previous = nodes.length;
    map.put(key, value);
    int current = ((Object[]) table.get(map)).length;

    if (previous != current) {
        ++HashMapResize.currentResizeCalls;
        System.out.println(nodes.length + "   " + current);
    }
}

现在让我们来测试一下：

static int currentResizeCalls = 0;

public static void main(String[] args) throws Throwable {

    List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY",
            "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
    int maxNumberOfEntries = list.size(); // 9
    double loadFactor = 0.75;
    int capacity = (int) (maxNumberOfEntries / loadFactor + 1);

    Map<String, String> map = new HashMap<>(capacity);

    list.forEach(x -> {
        try {
            HashMapResize.debugResize(map, x, x);
        } catch (Throwable throwable) {
            throwable.printStackTrace();
        }
    });

    System.out.println(HashMapResize.currentResizeCalls);

}

好的，resize 被调用了，因此条目被重新哈希，这与文档所说的不同。

---

正如所说，这些键并非随机选择。它们被设置为触发 static final int TREEIFY_THRESHOLD = 8; 属性 - 当一个桶被转换成一个树时。但实际上并非如此，因为我们还需要达到 MIN_TREEIFY_CAPACITY = 64 才能出现树形结构；在那之前 resize 会发生，或者一个桶的大小增加一倍；从而重新哈希条目。

我只能暗示为什么 HashMap 文档中的那个句子是错误的，因为在 Java 8 之前，一个桶没有被转换成一棵树。因此该属性将保持不变，从 Java 8 开始就不再是这样了。由于我不确定这一点，我不会将其添加为答案。

- Eugene

---

有趣的发现——[官方]文档并不完美；这很可能是文档和实现之间出现了分歧。 - user2864740

@user2864740 如果你想的话，你也可以在这里投票（https://dev59.com/1FcO5IYBdhLWcg3wsTjM）。虽然这是一个老问题，但仍然没有答案。 - Eugene

嗯...问题是什么？ - Jorn Vernee

@JornVernee 哎呀，问题是，这真的是文档缺陷吗？ Stuart 给出的答案是“是的”。 - Eugene

无关的：你给了正确的提示。我发现我的“小”辅助项目...没有重新编译。我改用另一个项目，设置为使用Java 7语言级别，是的，它可以编译成Java 7。所以很遗憾，我的问题没有继续存在的意义。所以我不得不删除它。我真的很讨厌那些被点赞的问题，因为我有太多的0分或更低的分数，都是因为报复性的投票者...但你在这里的问题：不错！ - GhostCat

Answer 1

文档中的这段话，

如果初始容量大于最大条目数除以负载因子，那么永远不会发生重新散列操作。

实际上是在JDK 8之前添加树形存储机制之前编写的（见JEP 180）。您可以在JDK 1.6 HashMap文档中找到此文本。事实上，这段文本可以追溯到引入集合框架（包括HashMap）的JDK 1.2时期。您可以在网络上找到JDK 1.2文档的非官方版本，或者您可以从存档下载版本以自行查看。

我认为直到添加树形存储机制之前，这份文档都是正确的。然而，正如您所观察到的，现在存在一些情况下它是不正确的。策略不仅是当条目数除以负载因子超过容量（实际上是表长度）时才会发生调整大小。就像您所指出的那样，如果单个桶中的条目数超过TREEIFY_THRESHOLD（当前为8），但表长度小于MIN_TREEIFY_CAPACITY（当前为64），也会发生调整大小。

您可以在HashMap的treeifyBin()方法中看到这个决策。

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {

当单个桶中的条目超过TREEIFY_THRESHOLD时，就会到达代码中的此点。如果表大小等于或大于MIN_TREEIFY_CAPACITY，则对该桶进行树化；否则，只需调整表的大小。

请注意，在小表大小下，这可能会导致桶中的条目比TREEIFY_THRESHOLD要多得多。这并不是很难证明。首先，一些反射HashMap-dumping代码：

// run with --add-opens java.base/java.util=ALL-UNNAMED

static Class<?> classNode;
static Class<?> classTreeNode;
static Field fieldNodeNext;
static Field fieldHashMapTable;

static void init() throws ReflectiveOperationException {
    classNode = Class.forName("java.util.HashMap$Node");
    classTreeNode = Class.forName("java.util.HashMap$TreeNode");
    fieldNodeNext = classNode.getDeclaredField("next");
    fieldNodeNext.setAccessible(true);
    fieldHashMapTable = HashMap.class.getDeclaredField("table");
    fieldHashMapTable.setAccessible(true);
}

static void dumpMap(HashMap<?, ?> map) throws ReflectiveOperationException {
    Object[] table = (Object[])fieldHashMapTable.get(map);
    System.out.printf("map size = %d, table length = %d%n", map.size(), table.length);
    for (int i = 0; i < table.length; i++) {
        Object node = table[i];
        if (node == null)
            continue;
        System.out.printf("table[%d] = %s", i,
            classTreeNode.isInstance(node) ? "TreeNode" : "BasicNode");

        for (; node != null; node = fieldNodeNext.get(node))
            System.out.print(" " + node);
        System.out.println();
    }
}

现在，让我们添加一堆字符串，它们都属于同一个桶。这些字符串被选择为它们的哈希值，由HashMap计算得出，都是模64余0。

public static void main(String[] args) throws ReflectiveOperationException {
    init();
    List<String> list = List.of(
        "LBCDD", "IKBNU", "WZQAG", "MKEAZ", "BBCHF", "KRQHE", "ZZMWH", "FHLVH",
        "ZFLXM", "TXXPE", "NSJDQ", "BXDMJ", "OFBCR", "WVSIG", "HQDXY");

    HashMap<String, String> map = new HashMap<>(1, 10.0f);

    for (String s : list) {
        System.out.println("===> put " + s);
        map.put(s, s);
        dumpMap(map);
    }
}

从初始表大小为1和荒谬的负载因子开始，这将8个条目放入孤立的存储桶中。然后，每次添加另一个条目时，表格会调整大小（加倍），但所有条目最终都会进入同一个存储桶。最终，这导致了一个大小为64的表，其中一个桶具有线性节点链（“基本节点”）长度为14，在添加下一个条目之前，最终将其转换为树形结构。

程序的输出如下所示：

===> put LBCDD
map size = 1, table length = 1
table[0] = BasicNode LBCDD=LBCDD
===> put IKBNU
map size = 2, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU
===> put WZQAG
map size = 3, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG
===> put MKEAZ
map size = 4, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ
===> put BBCHF
map size = 5, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF
===> put KRQHE
map size = 6, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE
===> put ZZMWH
map size = 7, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH
===> put FHLVH
map size = 8, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH
===> put ZFLXM
map size = 9, table length = 2
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM
===> put TXXPE
map size = 10, table length = 4
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE
===> put NSJDQ
map size = 11, table length = 8
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ
===> put BXDMJ
map size = 12, table length = 16
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ
===> put OFBCR
map size = 13, table length = 32
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR
===> put WVSIG
map size = 14, table length = 64
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG
===> put HQDXY
map size = 15, table length = 64
table[0] = TreeNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG HQDXY=HQDXY

- Stuart Marks

---

我喜欢这个代码，我也很喜欢你的答案，但是现在这句话不应该从HashMap文档中删除吗？ - Eugene

@Eugene 是的，文档可能需要进行调整。这似乎是一个小问题，即仅仅是一个小的措辞改变，而不是树形箱与调整大小策略的完整文档等。另一个错误[JDK-8211831]刚刚被发现，要求更新HashMap文档，所以我将同时修复这个问题。请参见我在那里的评论。 - Stuart Marks