指定精确容量时，为什么HashMap resize（）再次出现？

Question

代码比文字更重要，所以：

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在内部调用了21次！（感谢Andreas发现JVM在内部使用哈希映射，21个CAL中有19个来自其他进程）

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

如果我是一名新的java开发人员，我对HashMap构造函数中“容量”的第一个直观猜测是，它是我（HashMap的消费者）将放入映射中的元素数量的容量。但事实并非如此。

如果我想优化HashMap的使用，使其完全不需要调整自身大小，那么我需要充分了解HashMap的内部结构，以准确了解HashMap bucket数组需要有多稀疏。在我看来这很奇怪。HashMap应该隐式地为您实现这一点。这是OOP中封装的全部要点。

注意：我已经确认resize（）是我的应用程序用例的瓶颈，所以这就是为什么我的目标是减少对resize（）的调用次数。

问题是：

如果我事先知道要放入地图的条目的确切数量。我选择了什么容量来防止任何额外的调用resize（）操作？类似size*10的东西？我还想了解一些为什么HashMap是这样设计的背景知识。

编辑：我被问到很多为什么这个优化是必要的。我的应用程序在hashmap中花费了大量的CPU时间。调整大小（）。我的应用程序使用的哈希映射被初始化，其容量等于我们放入其中的元素数。因此，如果我们可以减少resize（）调用（通过选择更好的初始容量），那么我的应用程序性能就会提高。

Answer 1

这很容易证明：

private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable {

    Field table = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { table }, true);
    Object[] nodes = ((Object[]) table.get(map));

    // first put
    if (nodes == null) {
        map.put(key, value);
        return;
    }

    map.put(key, value);

    Field field = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { field }, true);
    int x = ((Object[]) field.get(map)).length;
    if (nodes.length != x) {
        ++currentResizeCalls;
    }
}

和一些用法：

static int currentResizeCalls = 0;

public static void main(String[] args) throws Throwable {

    int size = 100;
    Map<Integer, String> m = new HashMap<>(size);
    for (int i = 0; i < size; i++) {
        DeleteMe.debugResize(m, i, String.valueOf(i));
    }

    System.out.println(DeleteMe.currentResizeCalls);
}     

我只记录了实际调整大小所需的时间，因为第一个调用正在初始化；按照文件规定：

初始化或加倍表大小

你的第二点要有趣得多。哈希映射定义了容量，现在容量是多少？这并不明显：

对于HashMap，capacity是调整大小之前的存储桶数，对于ConcurrentHashMap是执行调整大小之前的条目数。

因此，不要在内部调用resize，在使用HashMap的情况下，使用以下公式：

(int)(1.0 + (long)initialCapacity / LOAD_FACTOR)

但这并不理想，假设您想要1024条目而不调整大小，通过使用该公式，您可以获得1367桶，这些桶在内部四舍五入为2的幂，因此2048-嗯，比您要求的要多得多。

对于CHM，直接指定尺寸。在前面的代码中使用一个简单的修改很容易证明：

 // use CHM instead of HashMap
 Map<Integer, String> m = new ConcurrentHashMap<>(size);

这将导致调整大小为零，实际上是html" target="_blank">数组的两倍。但有时，即使是CHM内部代码也很混乱，几乎不需要修补。

Answer 2

如有疑问，请阅读文档。HashMap的文档很好地解释了初始容量和负载因子之间的权衡。

根据留档ifinit容量=（maxEntry/loadFactor）1，添加条目时不会发生重新散列操作。在这种情况下，maxEntry是您指定的100，loadFactor将是.75的默认加载因子。

但是除了设置初始大小以避免重复（resize（））之外，您还应该仔细阅读HashMap的文档，以便正确调整它，同时考虑初始容量和负载因子。

如果您关心的是查找成本而不是空间，那么可以尝试使用较低的加载因子，如。5或更低。在这种情况下，您将使用以下两个参数创建哈希映射：

final float loadFactor = 0.5;
final int maxEntries   = 100;
final int initCapacity = (int) maxEntries / loadFactor + 1;
new HashMap<>(initCapacity, loadFactor);

（重点矿山）

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。负载因子是在自动增加哈希表容量之前，允许哈希表达到的满度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新刷新（即，重建内部数据结构），以便哈希表的存储桶数约为两倍
<作为一般规则，默认负载系数（0.75）在时间和空间成本之间提供了良好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置初始容量时，应考虑map中的预期条目数及其负载系数，以尽量减少再灰烬操作的次数。如果初始容量大于最大入口数除以负载系数，则不会发生再灰化操作。

Answer 3

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

仅供参考：resize（）只调用两次。添加第一个值时调用一次，当它达到75%满时调用一次。

为了防止调整大小，您需要确保第100个值不会导致调整大小，即size

capacity = size * 4/3 + 1

使用size=100，这意味着容量=134。