文档中的这段话,
如果初始容量大于最大条目数除以负载因子,那么永远不会发生重新散列操作。
实际上是在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代码:
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