java - 固定大小的 HashMap 的最佳容量和负载因子是多少？

Question

我试图找出特定情况下的最佳容量和负载系数。我想我明白了它的要点，但我仍然会感谢比我更博学的人的确认。 :)

如果我知道我的 HashMap 将填满以包含 100 个对象，并且大部分时间将花费 100 个对象，那么我猜测最佳值是初始容量 100 和负载因子 1？或者我需要容量 101，还是有其他问题？

编辑:好的，我留出了几个小时并做了一些测试。结果如下:

奇怪的是，容量、容量+1、容量+2、容量-1甚至容量-10都产生完全相同的结果。我预计至少容量 1 和容量 10 会给出更糟糕的结果。

使用初始容量(而不是使用默认值 16)可显着改善 put() - 最多可提高 30%。

使用负载因子 1 为少量对象提供相同的性能，并为大量对象(> 100000)提供更好的性能。但是，这不会与对象的数量成正比；我怀疑还有其他因素会影响结果。

get() 性能对于不同数量的对象/容量略有不同，但尽管可能因情况而异，但通常不受初始容量或负载因子的影响。

EDIT2:我也添加了一些图表。这是一个说明负载因子 0.75 和 1 之间差异的示例，在我初始化 HashMap 并将其填满的情况下。在 y 尺度上是以毫秒为单位的时间(越低越好)，而 x 尺度是大小(对象数量)。由于大小呈线性变化，因此所需时间也呈线性增长。

所以，让我们看看我得到了什么。以下两个图表显示了负载因子的差异。第一个图表显示了当 HashMap 被填满时会发生什么；由于调整大小，负载因子 0.75 的性能更差。然而，它并不是一直更糟，并且有各种各样的颠簸和跳跃 - 我想 GC 在这方面发挥着重要作用。负载因子 1.25 的性能与 1 相同，因此它不包含在图表中。



该图表证明 0.75 由于调整大小而更糟；如果我们将 HashMap 填充到一半容量，0.75 并不会更糟，只是......不同(它应该使用更少的内存并且具有明显更好的迭代性能)。



我还想展示一件事。这是获得所有三个负载因子和不同 HashMap 大小的性能。除了负载因子 1 的一个峰值外，始终保持不变，但有一点变化。我真的很想知道那是什么(可能是 GC，但谁知道呢)。



这是那些感兴趣的人的代码:

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {

  // capacity - numbers high as 10000000 require -mx1536m -ms1536m JVM parameters
  public static final int CAPACITY = 10000000;
  public static final int ITERATIONS = 10000;

  // set to false to print put performance, or to true to print get performance
  boolean doIterations = false;

  private Map<Integer, String> cache;

  public void fillCache(int capacity) {
    long t = System.currentTimeMillis();
    for (int i = 0; i <= capacity; i++)
      cache.put(i, "Value number " + i);

    if (!doIterations) {
      System.out.print(System.currentTimeMillis() - t);
      System.out.print("\t");
    }
  }

  public void iterate(int capacity) {
    long t = System.currentTimeMillis();

    for (int i = 0; i <= ITERATIONS; i++) {
      long x = Math.round(Math.random() * capacity);
      String result = cache.get((int) x);
    }

    if (doIterations) {
      System.out.print(System.currentTimeMillis() - t);
      System.out.print("\t");
    }
  }

  public void test(float loadFactor, int divider) {
    for (int i = 10000; i <= CAPACITY; i+= 10000) {
      cache = new HashMap<Integer, String>(i, loadFactor);
      fillCache(i / divider);
      if (doIterations)
        iterate(i / divider);
    }
    System.out.println();
  }

  public static void main(String[] args) {
    HashMapTest test = new HashMapTest();

    // fill to capacity
    test.test(0.75f, 1);
    test.test(1, 1);
    test.test(1.25f, 1);

    // fill to half capacity
    test.test(0.75f, 2);
    test.test(1, 2);
    test.test(1.25f, 2);
  }

}

Answer 1

好的，为了让这件事停下来，我创建了一个测试应用程序来运行几个场景并获得一些结果的可视化。以下是测试的完成方式:

尝试了许多不同的集合大小:一百、一千和十万个条目。

使用的 key 是由 ID 唯一标识的类的实例。每个测试都使用唯一的键，并以递增的整数作为 ID。 equals 方法只使用 ID，所以没有键映射覆盖另一个。

key 获得一个哈希码，该哈希码由其 ID 的模块余数与某个预设数字组成。我们将该数字称为哈希限制。这使我能够控制预期的哈希冲突数量。例如，如果我们的集合大小为 100，我们将拥有 ID 范围为 0 到 99 的键。如果哈希限制为 100，则每个键都将具有唯一的哈希码。如果哈希限制为 50，则键 0 将具有与键 50 相同的哈希码，1 将具有与 51 相同的哈希码等。换句话说，每个键的预期哈希冲突数是集合大小除以哈希限制。

对于集合大小和哈希限制的每种组合，我使用不同设置初始化的哈希映射运行测试。这些设置是负载因子，以及表示为集合设置因子的初始容量。例如，一个集合大小为 100 且初始容量因子为 1.25 的测试将初始化一个初始容量为 125 的哈希映射。

每个键的值只是一个新的 Object 。

每个测试结果都封装在一个Result类的实例中。在所有测试结束时，结果按整体性能从最差到最好的顺序排列。

puts 和gets 的平均时间是按每10 次puts/gets 计算的。

所有测试组合运行一次，消除JIT编译影响。之后，运行测试以获得实际结果。

这是类(class):

package hashmaptest;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class HashMapTest {

    private static final List<Result> results = new ArrayList<Result>();

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

        //First entry of each array is the sample collection size, subsequent entries
        //are the hash limits
        final int[][] sampleSizesAndHashLimits = new int[][] {
            {100, 50, 90, 100},
            {1000, 500, 900, 990, 1000},
            {100000, 10000, 90000, 99000, 100000}
        };
        final double[] initialCapacityFactors = new double[] {0.5, 0.75, 1.0, 1.25, 1.5, 2.0};
        final float[] loadFactors = new float[] {0.5f, 0.75f, 1.0f, 1.25f};

        //Doing a warmup run to eliminate JIT influence
        for(int[] sizeAndLimits : sampleSizesAndHashLimits) {
            int size = sizeAndLimits[0];
            for(int i = 1; i < sizeAndLimits.length; ++i) {
                int limit = sizeAndLimits[i];
                for(double initCapacityFactor : initialCapacityFactors) {
                    for(float loadFactor : loadFactors) {
                        runTest(limit, size, initCapacityFactor, loadFactor);
                    }
                }
            }

        }

        results.clear();

        //Now for the real thing...
        for(int[] sizeAndLimits : sampleSizesAndHashLimits) {
            int size = sizeAndLimits[0];
            for(int i = 1; i < sizeAndLimits.length; ++i) {
                int limit = sizeAndLimits[i];
                for(double initCapacityFactor : initialCapacityFactors) {
                    for(float loadFactor : loadFactors) {
                        runTest(limit, size, initCapacityFactor, loadFactor);
                    }
                }
            }

        }

        Collections.sort(results);

        for(final Result result : results) {
            result.printSummary();
        }

//      ResultVisualizer.visualizeResults(results);

    }

    private static void runTest(final int hashLimit, final int sampleSize,
            final double initCapacityFactor, final float loadFactor) {

        final int initialCapacity = (int)(sampleSize * initCapacityFactor);

        System.out.println("Running test for a sample collection of size " + sampleSize 
            + ", an initial capacity of " + initialCapacity + ", a load factor of "
            + loadFactor + " and keys with a hash code limited to " + hashLimit);
        System.out.println("====================");

        double hashOverload = (((double)sampleSize/hashLimit) - 1.0) * 100.0;

        System.out.println("Hash code overload: " + hashOverload + "%");

        //Generating our sample key collection.
        final List<Key> keys = generateSamples(hashLimit, sampleSize);

        //Generating our value collection
        final List<Object> values = generateValues(sampleSize);

        final HashMap<Key, Object> map = new HashMap<Key, Object>(initialCapacity, loadFactor);

        final long startPut = System.nanoTime();

        for(int i = 0; i < sampleSize; ++i) {
            map.put(keys.get(i), values.get(i));
        }

        final long endPut = System.nanoTime();

        final long putTime = endPut - startPut;
        final long averagePutTime = putTime/(sampleSize/10);

        System.out.println("Time to map all keys to their values: " + putTime + " ns");
        System.out.println("Average put time per 10 entries: " + averagePutTime + " ns");

        final long startGet = System.nanoTime();

        for(int i = 0; i < sampleSize; ++i) {
            map.get(keys.get(i));
        }

        final long endGet = System.nanoTime();

        final long getTime = endGet - startGet;
        final long averageGetTime = getTime/(sampleSize/10);

        System.out.println("Time to get the value for every key: " + getTime + " ns");
        System.out.println("Average get time per 10 entries: " + averageGetTime + " ns");

        System.out.println("");

        final Result result = 
            new Result(sampleSize, initialCapacity, loadFactor, hashOverload, averagePutTime, averageGetTime, hashLimit);

        results.add(result);

        //Haha, what kind of noob explicitly calls for garbage collection?
        System.gc();

        try {
            Thread.sleep(200);
        } catch(final InterruptedException e) {}

    }

    private static List<Key> generateSamples(final int hashLimit, final int sampleSize) {

        final ArrayList<Key> result = new ArrayList<Key>(sampleSize);

        for(int i = 0; i < sampleSize; ++i) {
            result.add(new Key(i, hashLimit));
        }

        return result;

    }

    private static List<Object> generateValues(final int sampleSize) {

        final ArrayList<Object> result = new ArrayList<Object>(sampleSize);

        for(int i = 0; i < sampleSize; ++i) {
            result.add(new Object());
        }

        return result;

    }

    private static class Key {

        private final int hashCode;
        private final int id;

        Key(final int id, final int hashLimit) {

            //Equals implies same hashCode if limit is the same
            //Same hashCode doesn't necessarily implies equals

            this.id = id;
            this.hashCode = id % hashLimit;

        }

        @Override
        public int hashCode() {
            return hashCode;
        }

        @Override
        public boolean equals(final Object o) {
            return ((Key)o).id == this.id;
        }

    }

    static class Result implements Comparable<Result> {

        final int sampleSize;
        final int initialCapacity;
        final float loadFactor;
        final double hashOverloadPercentage;
        final long averagePutTime;
        final long averageGetTime;
        final int hashLimit;

        Result(final int sampleSize, final int initialCapacity, final float loadFactor, 
                final double hashOverloadPercentage, final long averagePutTime, 
                final long averageGetTime, final int hashLimit) {

            this.sampleSize = sampleSize;
            this.initialCapacity = initialCapacity;
            this.loadFactor = loadFactor;
            this.hashOverloadPercentage = hashOverloadPercentage;
            this.averagePutTime = averagePutTime;
            this.averageGetTime = averageGetTime;
            this.hashLimit = hashLimit;

        }

        @Override
        public int compareTo(final Result o) {

            final long putDiff = o.averagePutTime - this.averagePutTime;
            final long getDiff = o.averageGetTime - this.averageGetTime;

            return (int)(putDiff + getDiff);
        }

        void printSummary() {

            System.out.println("" + averagePutTime + " ns per 10 puts, "
                + averageGetTime + " ns per 10 gets, for a load factor of "
                + loadFactor + ", initial capacity of " + initialCapacity
                + " for " + sampleSize + " mappings and " + hashOverloadPercentage 
                + "% hash code overload.");

        }

    }

}

运行这可能需要一段时间。结果打印在标准输出上。你可能注意到我注释掉了一行。该行调用一个可视化器，将结果的可视化表示输出到 png 文件。下面给出了这个类。如果您想运行它，请取消注释上面代码中的相应行。请注意:可视化器类假定您在 Windows 上运行，并将在 C:\temp 中创建文件夹和文件。在其他平台上运行时，请调整此项。

package hashmaptest;

import hashmaptest.HashMapTest.Result;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.imageio.ImageIO;

public class ResultVisualizer {

    private static final Map<Integer, Map<Integer, Set<Result>>> sampleSizeToHashLimit = 
        new HashMap<Integer, Map<Integer, Set<Result>>>();

    private static final DecimalFormat df = new DecimalFormat("0.00");

    static void visualizeResults(final List<Result> results) throws IOException {

        final File tempFolder = new File("C:\\temp");
        final File baseFolder = makeFolder(tempFolder, "hashmap_tests");

        long bestPutTime = -1L;
        long worstPutTime = 0L;
        long bestGetTime = -1L;
        long worstGetTime = 0L;

        for(final Result result : results) {

            final Integer sampleSize = result.sampleSize;
            final Integer hashLimit = result.hashLimit;
            final long putTime = result.averagePutTime;
            final long getTime = result.averageGetTime;

            if(bestPutTime == -1L || putTime < bestPutTime)
                bestPutTime = putTime;
            if(bestGetTime <= -1.0f || getTime < bestGetTime)
                bestGetTime = getTime;

            if(putTime > worstPutTime)
                worstPutTime = putTime;
            if(getTime > worstGetTime)
                worstGetTime = getTime;

            Map<Integer, Set<Result>> hashLimitToResults = 
                sampleSizeToHashLimit.get(sampleSize);
            if(hashLimitToResults == null) {
                hashLimitToResults = new HashMap<Integer, Set<Result>>();
                sampleSizeToHashLimit.put(sampleSize, hashLimitToResults);
            }
            Set<Result> resultSet = hashLimitToResults.get(hashLimit);
            if(resultSet == null) {
                resultSet = new HashSet<Result>();
                hashLimitToResults.put(hashLimit, resultSet);
            }
            resultSet.add(result);

        }

        System.out.println("Best average put time: " + bestPutTime + " ns");
        System.out.println("Best average get time: " + bestGetTime + " ns");
        System.out.println("Worst average put time: " + worstPutTime + " ns");
        System.out.println("Worst average get time: " + worstGetTime + " ns");

        for(final Integer sampleSize : sampleSizeToHashLimit.keySet()) {

            final File sizeFolder = makeFolder(baseFolder, "sample_size_" + sampleSize);

            final Map<Integer, Set<Result>> hashLimitToResults = 
                sampleSizeToHashLimit.get(sampleSize);

            for(final Integer hashLimit : hashLimitToResults.keySet()) {

                final File limitFolder = makeFolder(sizeFolder, "hash_limit_" + hashLimit);

                final Set<Result> resultSet = hashLimitToResults.get(hashLimit);

                final Set<Float> loadFactorSet = new HashSet<Float>();
                final Set<Integer> initialCapacitySet = new HashSet<Integer>();

                for(final Result result : resultSet) {
                    loadFactorSet.add(result.loadFactor);
                    initialCapacitySet.add(result.initialCapacity);
                }

                final List<Float> loadFactors = new ArrayList<Float>(loadFactorSet);
                final List<Integer> initialCapacities = new ArrayList<Integer>(initialCapacitySet);

                Collections.sort(loadFactors);
                Collections.sort(initialCapacities);

                final BufferedImage putImage = 
                    renderMap(resultSet, loadFactors, initialCapacities, worstPutTime, bestPutTime, false);
                final BufferedImage getImage = 
                    renderMap(resultSet, loadFactors, initialCapacities, worstGetTime, bestGetTime, true);

                final String putFileName = "size_" + sampleSize + "_hlimit_" + hashLimit + "_puts.png";
                final String getFileName = "size_" + sampleSize + "_hlimit_" + hashLimit + "_gets.png";

                writeImage(putImage, limitFolder, putFileName);
                writeImage(getImage, limitFolder, getFileName);

            }

        }

    }

    private static File makeFolder(final File parent, final String folder) throws IOException {

        final File child = new File(parent, folder);

        if(!child.exists())
            child.mkdir();

        return child;

    }

    private static BufferedImage renderMap(final Set<Result> results, final List<Float> loadFactors,
            final List<Integer> initialCapacities, final float worst, final float best,
            final boolean get) {

        //[x][y] => x is mapped to initial capacity, y is mapped to load factor
        final Color[][] map = new Color[initialCapacities.size()][loadFactors.size()];

        for(final Result result : results) {
            final int x = initialCapacities.indexOf(result.initialCapacity);
            final int y = loadFactors.indexOf(result.loadFactor);
            final float time = get ? result.averageGetTime : result.averagePutTime;
            final float score = (time - best)/(worst - best);
            final Color c = new Color(score, 1.0f - score, 0.0f);
            map[x][y] = c;
        }

        final int imageWidth = initialCapacities.size() * 40 + 50;
        final int imageHeight = loadFactors.size() * 40 + 50;

        final BufferedImage image = 
            new BufferedImage(imageWidth, imageHeight, BufferedImage.TYPE_3BYTE_BGR);

        final Graphics2D g = image.createGraphics();

        g.setColor(Color.WHITE);
        g.fillRect(0, 0, imageWidth, imageHeight);

        for(int x = 0; x < map.length; ++x) {

            for(int y = 0; y < map[x].length; ++y) {

                g.setColor(map[x][y]);
                g.fillRect(50 + x*40, imageHeight - 50 - (y+1)*40, 40, 40);

                g.setColor(Color.BLACK);
                g.drawLine(25, imageHeight - 50 - (y+1)*40, 50, imageHeight - 50 - (y+1)*40);

                final Float loadFactor = loadFactors.get(y);
                g.drawString(df.format(loadFactor), 10, imageHeight - 65 - (y)*40);

            }

            g.setColor(Color.BLACK);
            g.drawLine(50 + (x+1)*40, imageHeight - 50, 50 + (x+1)*40, imageHeight - 15);

            final int initialCapacity = initialCapacities.get(x);
            g.drawString(((initialCapacity%1000 == 0) ? "" + (initialCapacity/1000) + "K" : "" + initialCapacity), 15 + (x+1)*40, imageHeight - 25);
        }

        g.drawLine(25, imageHeight - 50, imageWidth, imageHeight - 50);
        g.drawLine(50, 0, 50, imageHeight - 25);

        g.dispose();

        return image;

    }

    private static void writeImage(final BufferedImage image, final File folder, 
            final String filename) throws IOException {

        final File imageFile = new File(folder, filename);

        ImageIO.write(image, "png", imageFile);

    }

}

可视化输出如下:

测试首先按集合大小划分，然后按哈希限制划分。

对于每个测试，都有一个关于平均放置时间(每 10 次放置)和平均获取时间(每 10 次放置)的输出图像。这些图像是二维“热图”，根据初始容量和负载因子的组合显示颜色。

图像中的颜色基于从最佳到最差结果的标准化范围内的平均时间，范围从饱和绿色到饱和红色。换句话说，最好的时间将是完全绿色的，而最坏的时间将是完全红色的。两个不同的时间测量值不应具有相同的颜色。

颜色图是针对 puts 和 gets 分别计算的，但包含它们各自类别的所有测试。

可视化在其 x 轴上显示初始容量，在 y 轴上显示负载因子。

事不宜迟，让我们来看看结果。我将从看跌期权的结果开始。

把结果

集合大小:100。散列限制:50。这意味着每个散列代码应该出现两次，并且在散列映射中每隔一个键就会发生冲突。



嗯，这开始不是很好。我们看到初始容量比集合大小高 25% 时有一个很大的热点，负载因子为 1。左下角的表现不太好。

集合大小:100。哈希限制:90。十分之一的键具有重复的哈希代码。



这是一个稍微更现实的场景，没有完美的散列函数，但仍然有 10% 的过载。热点消失了，但低初始容量和低负载系数的组合显然不起作用。

集合大小:100。哈希限制:100。每个键作为自己唯一的哈希码。如果有足够的桶，预计不会发生冲突。



初始容量为 100，负载因子为 1 似乎没问题。令人惊讶的是，具有较低负载系数的较高初始容量不一定是好的。

集合大小:1000。哈希限制:500。这里越来越严重，有 1000 个条目。就像在第一个测试中一样，有一个 2 比 1 的哈希过载。



左下角仍然做得不好。但是在较低的初始计数/高负载因子和较高的初始计数/低负载因子的组合之间似乎存在对称性。

集合大小:1000。哈希限制:900。这意味着十分之一的哈希码会出现两次。关于碰撞的合理场景。



发生了一些非常有趣的事情，即初始容量过低且负载因子高于 1 的不太可能的组合，这是相当违反直觉的。否则，仍然相当对称。

集合大小:1000。哈希限制:990。一些冲突，但只有少数。在这方面很现实。



我们这里有很好的对称性。左下角仍然是次优的，但组合 1000 初始容量/1.0 负载因子与 1250 初始容量/0.75 负载因子处于同一水平。

集合大小:1000。哈希限制:1000。没有重复的哈希代码，但现在样本大小为 1000。



这里不多说了。更高的初始容量与 0.75 的负载因子的组合似乎略胜于 1000 初始容量与负载因子 1 的组合。

集合大小:100_000。哈希限制:10_000。好的，现在事情变得严重了，每个键的样本大小为 10 万和 100 个哈希码重复。



哎呀!我想我们找到了我们的低频谱。负载因子为 1 的集合大小的初始容量在这里做得非常好，但除此之外，它遍布整个商店。

集合大小:100_000。哈希限制:90_000。比之前的测试更现实一点，这里我们有 10% 的哈希码过载。



左下角还是不行的。较高的初始容量效果最好。

集合大小:100_000。哈希限制:99_000。好场景，这个。具有 1% 哈希码过载的大型集合。



使用确切的集合大小作为初始容量，负载因子为 1 在这里胜出!不过，稍微大一点的 init 容量也能很好地工作。

集合大小:100_000。哈希限制:100_000。大的那个。具有完美散列函数的最大集合。



这里有一些令人惊讶的东西。在负载系数为 1 的情况下，初始容量增加 50% 的额外空间。

好的，这就是看跌期权。现在，我们将检查获取。请记住，下面的 map 都是相对于最佳/最差获取时间的，不再考虑放置时间。

获取结果

集合大小:100。哈希限制:50。这意味着每个哈希代码应该出现两次，并且每个其他键都应该在哈希映射中发生冲突。



呃……什么？

集合大小:100。哈希限制:90。十分之一的键具有重复的哈希代码。



哇尼莉!这是与提问者的问题相关的最有可能的情况，显然初始容量为 100 且负载因子为 1 是这里最糟糕的事情之一!我发誓我没有伪造这个。

集合大小:100。哈希限制:100。每个键作为自己唯一的哈希码。预计不会发生碰撞。



这看起来更平静一些。几乎所有的结果都是一样的。

集合大小:1000。散列限制:500。就像在第一个测试中一样，散列重载为 2 比 1，但现在有更多条目。



看起来任何设置都会在这里产生不错的结果。

集合大小:1000。哈希限制:900。这意味着十分之一的哈希码会出现两次。关于碰撞的合理场景。



就像这个设置的看跌期权一样，我们在一个奇怪的地方得到了一个异常。

集合大小:1000。哈希限制:990。一些冲突，但只有少数。在这方面很现实。



到处都有不错的性能，除了高初始容量和低负载系数的组合。我希望这适用于看跌期权，因为可能需要调整两个哈希图的大小。但为什么要得到呢？

集合大小:1000。哈希限制:1000。没有重复的哈希代码，但现在样本大小为 1000。



一个完全不引人注目的可视化。这似乎无论如何都有效。

集合大小:100_000。哈希限制:10_000。再次进入 100K，大量哈希码重叠。



它看起来并不漂亮，虽然坏点非常局部。这里的性能似乎在很大程度上取决于设置之间的某种协同作用。

集合大小:100_000。哈希限制:90_000。比之前的测试更现实一点，这里我们有 10% 的哈希码过载。



差异很大，但如果你眯着眼睛，你会看到一个指向右上角的箭头。

集合大小:100_000。哈希限制:99_000。好场景，这个。具有 1% 哈希码过载的大型集合。



很乱。在这里很难找到很多结构。

集合大小:100_000。哈希限制:100_000。大的那个。具有完美散列函数的最大集合。



其他人认为这开始看起来像 Atari 图形吗？这似乎有利于精确集合大小的初始容量，-25% 或 +50%。

好了，现在是下结论的时候了……

关于放置时间:您希望避免初始容量低于预期的 map 条目数。如果事先知道一个确切的数字，那么这个数字或稍高于它的数字似乎效果最好。由于较早的哈希映射调整大小，高负载因子可以抵消较低的初始容量。对于更高的初始容量，它们似乎没有那么重要。

关于获取时间:这里的结果有点困惑。没什么好总结的。它似乎非常依赖于哈希码重叠、初始容量和负载因子之间的微妙比率，一些据说不好的设置表现良好，而好的设置表现得非常糟糕。

当谈到关于 Java 性能的假设时，我显然充满了废话。事实是，除非您将设置完美地调整为 HashMap 的实现，否则结果将无处不在。如果有一点需要注意，那就是默认的初始大小 16 对于除了最小的 map 之外的任何东西都有些愚蠢，因此如果您对大小的顺序有任何想法，请使用设置初始大小的构造函数这将是。

我们在这里以纳秒为单位进行测量。在我的机器上，每 10 次 put 的最佳平均时间是 1179 ns，最差的 5105 ns。每 10 次获取的最佳平均时间为 547 ns，最差为 3484 ns。这可能是 6 倍的差异，但我们说的是不到一毫秒。在比原始海报想象的要大得多的系列上。

嗯，就是这样。我希望我的代码没有一些可怕的疏忽使我在这里发布的所有内容无效。这很有趣，而且我了解到，最终您最好还是依靠 Java 来完成它的工作，而不是期望与微小的优化有很大不同。这并不是说不应该避免某些东西，但是我们主要讨论的是在 for 循环中构造冗长的字符串、使用错误的数据结构和制作 O(n^3) 算法。