java - 为什么 HashMap 在指定精确容量时再次调整大小()?

标签 java optimization data-structures hashmap cpu

代码胜于 Eloquent ,因此:

final int size = 100;
Map<Integer, String> m = new HashMap<>(size);
for (int i = 0; i < size; i++) m.put(i, String.valueOf(i));

为什么 HashMap 在内部调用 resize() 21 2 次!(感谢 Andreas 确定 JVM 在内部使用 HashMap,21 个调用中有 19 个来自其他进程)

我的应用程序仍然不能接受两次 resize() 调用。我需要对此进行优化。

如果我是一名新的 Java 开发人员,我对 HashMap 构造函数中“容量”的第一个直觉猜测是它是我(HashMap 的消费者)将要放入的元素数量的容量 map 。但事实并非如此。

如果我想优化我对 HashMap 的使用,使其根本不需要调整自身大小,那么我需要足够深入地了解 HashMap 的内部结构,以便准确了解 HashMap 桶数组需要的稀疏程度。我认为这很奇怪。 HashMap 应该隐式地为你做这件事。这是 OOP 中封装的全部要点。

注意:我已经确认 resize() 是我的应用程序用例的瓶颈,因此我的目标是减少对 resize() 的调用次数。

问题:

如果我知道条目的确切数量,我将事先放入 map 中。我选择什么容量,以防止任何 额外调用resize() 操作?像 size * 10 这样的东西?我还想知道为什么 HashMap 是这样设计的。

编辑:很多人问我为什么需要进行这种优化。我的应用程序在 hashmap.resize() 中花费了大量的 CPU 时间。我的应用程序使用的散列映射的初始化容量等于我们放入其中的元素数量。因此,如果我们可以减少 resize() 调用(通过选择更好的初始容量),那么我的应用程序性能就会提高。

最佳答案

默认加载因子为 0.75 ,即 3/4 ,这意味着当添加了 100 个值中的 75 个时,将调整内部哈希表的大小。

仅供引用: resize()只被调用两次。添加第一个值时一次,当它达到 75% 时一次。

为防止调整大小,您需要确保第 100 个值不会导致调整大小,即 size <= capacity * 0.75又名 size <= capacity * 3/4又名 size * 4/3 <= capacity , 所以可以肯定的是:

capacity = size * 4/3 + 1

size = 100 , 这意味着 capacity = 134 .

关于java - 为什么 HashMap 在指定精确容量时再次调整大小()?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52671362/

相关文章:

java - 从 URL 加载图像并限制文件大小

java - setEntityMethod 和 SetRequestEntityMethod 之间的区别

ios - 未对齐的 UILabel

data-structures - 具有随机访问的自排序数据结构

java - 为什么 Spring Web 服务中 Autowiring 依赖项的注入(inject)失败?

java - Spring @RestController 注释,带有来自 beans.xml 的根上下文

c - 消除GOT寄存器的冗余负载?

android - 为什么我们已经有了/data/dalvik-cache,还要把*.odex文件放在/system/app下?

algorithm - 使用 BST 搜索多个字段

arrays - Cocoa 中的循环链表