HashMap重新散列/调整容量

A HashMap有一个来自它的文档的短语:

如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.

注意文档怎么说的老调重弹,没有调整 -即使翻版只会当调整大小会发生; 那就是当桶的内部大小增加两倍时.

当然HashMap,我们可以提供这样一个构造函数来定义这个初始容量.

使用指定的初始容量和默认加载因子(0.75)构造一个空的HashMap.

好的,似乎很容易:

// these are NOT chosen randomly...    
List 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的幂),这样我们保证文档部分不重复.好吧,让我们测试一下,但首先介绍一个方法,进入HashMap并查看值:

private static  void debugResize(Map 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 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 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开始,属性将保持不再是真实的.由于我不确定这一点,所以我不会将此作为答案添加.

文档中的行,

如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.

确实是在JDK 8(JEP 180)中添加了tree-bin实现之前的日期.您可以在JDK 1.6 HashMap文档中看到此文本.事实上,当引入集合框架(包括HashMap)时,本文可以追溯到JDK 1.2.您可以在JDK 1.2文档的非官方版本的网络上,也可以从下载版本档案,如果你想看到自己.

我相信这个文档是正确的,直到添加了tree-bin实现.但是,正如您所观察到的,现在存在不正确的情况.如果条目数除以负载因子超过容量(实际上是表长度),则策略不仅仅是可以进行大小调整.如您所述,如果单个存储桶中的条目数超过TREEIFY_THRESHOLD(当前为8),但表长度小于MIN_TREEIFY_CAPACITY(当前为64),则也会发生调整大小.

您可以在treeifyBin()HashMap 的方法中看到此决定.

    if (tab == null || (n = tab.length) 

当一个存储桶中有多个TREEIFY_THRESHOLD个条目时,就会达到代码中的这一点.如果表格大小等于或高于MIN_TREEIFY_CAPACITY,则此bin将被树化; 否则,表格只是调整大小.

请注意,在小表格大小的情况下,这可以使条目的条目数比TREEIFY_THRESHOLD的条目多得多.这非常难以证明.首先,一些反思的HashMap转储代码:

// 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 

现在,让我们添加一堆字符串,这些字符串都属于同一个存储桶.选择这些字符串使得它们的哈希值(由HashMap计算)都是0 mod 64.

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

    HashMap 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

        
我喜欢这些代码,我喜欢你的答案,*但是*现在不应该从HashMap文档中删除这句话吗？ 
@Eugene是的,应该调整文档.这似乎是一个小问题,即只是一个小的措辞变化,而不是完整的树箱文件与调整大小政策等.另一个错误[JDK-8211831](https://bugs.openjdk.java.net/浏览/ JDK-8211831)刚刚请求HashMap文档更新,所以我会同时解决这个问题.看那里的评论.