java – HashMap rehash / resize capacity
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – HashMap rehash / resize capacity，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7894字，纯文字阅读大概需要12分钟。
内容图文
HashMap有一个来自它的文档的短语：
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
注意文档如何重新表示,而不是调整大小 – 即使重新调整只会在调整大小时发生;那就是当桶的内部大小增加两倍时.
当然,HashMap提供了这样一个构造函数,我们可以在其中定义这个初始容量.
Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
好的,似乎很容易：
// 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的幂),这样我们保证文档部分不重复.好的,让我们测试一下,但首先介绍一个将进入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被调用,因此条目重新散列,而不是文档说的.
如上所述,密钥不是随机选择的.这些设置是为了触发静态最终int TREEIFY_THRESHOLD = 8; property – 将存储桶转换为树时.不是真的,因为我们还需要点击MIN_TREEIFY_CAPACITY = 64才能显示树;直到重新调整大小,或者一个桶的大小加倍;因此,条目的重复发生.
我只能暗示为什么HashMap文档在那个句子中是错误的,因为在java-8之前,一个桶没有被转换为树;因此,从java-8开始,属性将保持不再是真实的.由于我不确定这一点,所以我不会将此作为答案添加.
解决方法:
文档中的行,
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
确实是在JDK 8(JEP 180)中添加tree-bin实现之前的日期.您可以在JDK 1.6 HashMap documentation中看到此文本.实际上,当引入集合框架(包括HashMap)时,本文可以追溯到JDK 1.2.您可以在网络上找到JDK 1.2文档的非官方版本,或者如果您想亲自查看,可以从archives下载该版本.
我相信这个文档是正确的,直到添加了tree-bin实现.但是,正如您所观察到的,现在存在不正确的情况.如果条目数除以负载因子超过容量(实际上是表长度),则策略不仅仅是可以进行大小调整.如您所述,如果单个存储桶中的条目数超过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,则此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 < 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计算)都是0 mod 64.
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
内容总结
以上是互联网集市为您收集整理的java – HashMap rehash / resize capacity全部内容，希望文章能够帮你解决java – HashMap rehash / resize capacity所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。