- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
HashMap
的文档中有这样的短语:
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
注意文档是如何说 rehash,而不是 resize - 即使 rehash 只会在调整大小时发生;那是当桶的内部大小变成两倍大的时候。
当然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
- 二次幂),这样我们保证文档部分不会重复。好的,让我们测试一下,但首先介绍一个方法,该方法将进入 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
被调用,因此条目被重新散列,而不是文档所说的。
如上所述, key 不是随机选择的。这些设置是为了在存储桶转换为树时触发 static final int TREEIFY_THRESHOLD = 8;
属性。不是真的,因为我们还需要点击 MIN_TREEIFY_CAPACITY = 64
才能出现树;直到 resize
发生,或者桶的大小增加了一倍;因此会发生条目的重新散列。
我只能提示为什么 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) 中添加树箱实现之前。您可以在 JDK 1.6 HashMap documentation 中看到此文本.事实上,这篇文章可以追溯到 JDK 1.2,当时引入了 Collections Framework(包括 HashMap)。您可以在网上找到 JDK 1.2 文档的非官方版本,或者您可以从 archives 下载一个版本。如果你想亲眼看看。
我相信这个文档在添加树箱实现之前是正确的。但是,正如您所观察到的,现在有些情况下它是不正确的。该策略不仅是如果条目数除以负载因子超过容量(实际上是表长度),则会发生大小调整。正如您所指出的,如果单个存储桶中的条目数超过 TREEIFY_THRESHOLD(当前为 8)但表长度小于 MIN_TREEIFY_CAPACITY(当前为 64),则可能也发生调整大小。
您可以在 treeifyBin()
中看到此决定HashMap的方法。
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-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 计算)均为 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容量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52692803/
在某些时候我们需要增加散列的大小,通常我们只是重新散列,这会导致整个散列的重新构造。 有没有更好的解决方案,当我们增加尺寸时,我们不需要重新构造整个东西? 最佳答案 你可以使用 http://en.w
我正在实现一个哈希表,而不使用任何内置的 java HashTable 功能,并收到以下行的编译时错误: newHashTable.add(reHashValueIndex, bucket.get(j
我们有一个运行着多个数据库的 MySQL 服务器,用于不同类型的数据。其中之一是 wordpress 数据库。 我可以连接正常,“显示数据库”,“使用苹果”,“使用橙子”等(用水果代替我们的实际数据库
HashMap 的文档中有这样的短语: If the initial capacity is greater than the maximum number of entries divided by
我正在使用Kibana 4在ElasticSearch上查询唯一计数。 我想prevent rehash on field,,因为该字段已经被散列了。 如何使Kibana使用"rehash": fal
我对散列和重新散列有些困惑。以下是我的理解,如有错误请指正。 从图片上看,bucket实际上是Entry类的数组,以链表的形式存储元素。每个新的键值对,其键具有与条目数组桶相同的哈希码,将作为条目对象
我不明白为什么 hastable 的 rehash 复杂度在最坏的情况下可能是二次的: http://www.cplusplus.com/reference/unordered_set/unorder
我了解 unordered_ STL 容器保留多个桶,桶的数量根据容器中元素的数量而变化。插入时,如果超过一定的限制,容器将重新散列以使用更多的桶,因此每个桶都不太满并且搜索速度更快。这会使迭代器无效
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎不是关于 a specific programming problem, a softwa
我们的数据库有很多表和很多列。命令行 mysql 客户端需要很长时间才能连接,除非我通过它 -A。我不想每次都输入它,所以我尝试添加 my.cnf 选项 no-auto-rehash。 在我必须使用
我试图让我的 Ruby 1.9.3 运行我的 Octopress 安装。 当我输入时: rbenv rehash 我遇到了一个错误: rbenv: cannot rehash: /Users/m
C++ unordered_map 的rehash() 和reserve() 方法有什么区别?为什么需要两种不同的方法? 最佳答案 区别在于目的,尽管两者都在做类似的事情。 rehash 获取现有映射
我不明白为什么它不是线性的。 关于多重集的类似问题有一个很好的答案: why hastable's rehash complexity may be quadratic in worst case 但
我正在将用户从遗留用户存储迁移到我的 ASP.NET 5.0 Web 应用程序中的 ASP.NET Identity 2.0。我有一种验证遗留哈希的方法,但我想在登录时将它们升级到 ASP.NET I
我正在尝试在安装新 gem 后重新哈希 rbenv它在我的 ubuntu 服务器上给了我这些错误 rbenv: cannot rehash: /home/deployer/.rbenv/shims/
我是一名优秀的程序员,十分优秀!