HashMap 重新散列/调整容量

Question

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

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

请注意文档如何说rehash，而不是调整大小- 即使 rehash 只会在调整大小时发生；那是当桶的内部大小变成两倍大时。

当然也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- 下一个 2 的幂），这样我们就可以保证文档部分没有重新哈希。好的，让我们测试一下，但首先介绍一个方法，该方法将进入 aHashMap并查看值：

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);

好吧，resize被调用，因此条目被重新哈希，而不是文档所说的。

如上所述，密钥不是随机选择的。这些设置是为了触发static final int TREEIFY_THRESHOLD = 8;属性 - 当一个桶转换为一棵树时。不是真的，因为我们还需要击中MIN_TREEIFY_CAPACITY = 64树才能出现；直到resize发生这种情况，或者桶的大小增加了一倍；因此会发生条目的重新散列。

我只能暗示为什么HashMap那句话中的文档是错误的，因为在java-8之前，bucket 没有转换为 Tree；因此，该属性将保持不变，从 java-8 开始就不再正确了。由于我不确定这一点，因此我不会将其添加为答案。

Answer 1

文档中的那一行，如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。确实可以追溯到在 JDK 8 ( JEP 180 ) 中添加 tree-bin 实现之前。您可以在JDK 1.6 HashMap 文档中看到此文本。事实上，本文可以追溯到 JDK 1.2 引入集合框架（包括 HashMap）时。您可以在网络上找到 JDK 1.2 文档的非官方版本，或者如果您想亲自查看，也可以从档案中下载一个版本。我相信在添加 tree-bin 实现之前，此文档是正确的。但是，正如您所观察到的，现在有些情况是不正确的。如果条目数除以负载因子超过容量（实际上是表长度），则策略不仅可以调整大小。正如您所指出的，如果单个存储桶中的条目数超过 TREEIFY_THRESHOLD（当前为 8）但表长度小于 MIN_TREEIFY_CAPACITY（当前为 64），也会发生大小调整。你可以在treeifyBin()HashMap的方法中看到这个决定。&nbsp; &nbsp; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)&nbsp; &nbsp; &nbsp; &nbsp; resize();&nbsp; &nbsp; else if ((e = tab[index = (n - 1) & hash]) != null) {当单个存储桶中的条目超过 TREEIFY_THRESHOLD 时，就会到达代码中的这一点。如果表大小等于或大于 MIN_TREEIFY_CAPACITY，则此 bin 被树化；否则，表格只是调整大小。请注意，在小表大小下，这可能会使 bin 的条目比 TREEIFY_THRESHOLD 多。这并不是很难证明。首先，一些反射 HashMap 转储代码：// run with --add-opens java.base/java.util=ALL-UNNAMEDstatic Class<?> classNode;static Class<?> classTreeNode;static Field fieldNodeNext;static Field fieldHashMapTable;static void init() throws ReflectiveOperationException {&nbsp; &nbsp; classNode = Class.forName("java.util.HashMap$Node");&nbsp; &nbsp; classTreeNode = Class.forName("java.util.HashMap$TreeNode");&nbsp; &nbsp; fieldNodeNext = classNode.getDeclaredField("next");&nbsp; &nbsp; fieldNodeNext.setAccessible(true);&nbsp; &nbsp; fieldHashMapTable = HashMap.class.getDeclaredField("table");&nbsp; &nbsp; fieldHashMapTable.setAccessible(true);}static void dumpMap(HashMap<?, ?> map) throws ReflectiveOperationException {&nbsp; &nbsp; Object[] table = (Object[])fieldHashMapTable.get(map);&nbsp; &nbsp; System.out.printf("map size = %d, table length = %d%n", map.size(), table.length);&nbsp; &nbsp; for (int i = 0; i < table.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; Object node = table[i];&nbsp; &nbsp; &nbsp; &nbsp; if (node == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("table[%d] = %s", i,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; classTreeNode.isInstance(node) ? "TreeNode" : "BasicNode");&nbsp; &nbsp; &nbsp; &nbsp; for (; node != null; node = fieldNodeNext.get(node))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(" " + node);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; }}现在，让我们添加一堆都属于同一个桶的字符串。选择这些字符串，使得它们的哈希值，由 HashMap 计算，都是 0 mod 64。public static void main(String[] args) throws ReflectiveOperationException {&nbsp; &nbsp; init();&nbsp; &nbsp; List<String> list = List.of(&nbsp; &nbsp; &nbsp; &nbsp; "LBCDD", "IKBNU", "WZQAG", "MKEAZ", "BBCHF", "KRQHE", "ZZMWH", "FHLVH",&nbsp; &nbsp; &nbsp; &nbsp; "ZFLXM", "TXXPE", "NSJDQ", "BXDMJ", "OFBCR", "WVSIG", "HQDXY");&nbsp; &nbsp; HashMap<String, String> map = new HashMap<>(1, 10.0f);&nbsp; &nbsp; for (String s : list) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("===> put " + s);&nbsp; &nbsp; &nbsp; &nbsp; map.put(s, s);&nbsp; &nbsp; &nbsp; &nbsp; dumpMap(map);&nbsp; &nbsp; }}从初始表大小 1 和荒谬的负载因子开始，这将 8 个条目放入单独的存储桶中。然后，每次添加另一个条目时，表都会调整大小（加倍），但所有条目最终都在同一个存储桶中。这最终会产生一个大小为 64 的表，其中一个桶具有长度为 14 的线性节点链（“基本节点”），然后添加下一个条目最终将其转换为树。程序的输出如下：===> put LBCDDmap size = 1, table length = 1table[0] = BasicNode LBCDD=LBCDD===> put IKBNUmap size = 2, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU===> put WZQAGmap size = 3, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG===> put MKEAZmap size = 4, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ===> put BBCHFmap size = 5, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF===> put KRQHEmap size = 6, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE===> put ZZMWHmap size = 7, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH===> put FHLVHmap size = 8, table length = 1table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH===> put ZFLXMmap size = 9, table length = 2table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM===> put TXXPEmap size = 10, table length = 4table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE===> put NSJDQmap size = 11, table length = 8table[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 BXDMJmap size = 12, table length = 16table[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 OFBCRmap size = 13, table length = 32table[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 WVSIGmap size = 14, table length = 64table[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 HQDXYmap size = 15, table length = 64table[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