什么是固定大小的HashMap的最佳容量和负载因子？
我试图找出一个特定情况下的最佳容量和负载因数。 我想我已经掌握了它的要点，但是我仍然要感谢比我更有认识的人的确认。 🙂
如果我知道我的HashMap将会填满100个对象，并且大部分时间会花费100个对象，那么我猜测最佳值是初始容量100和负载因子1？ 或者我需要容量101，还是还有其他问题？
编辑：好的，我搁置了几个小时，做了一些testing。 结果如下：
- 奇怪的是，容量，容量+1，容量+2，容量-1甚至容量-10都会产生完全相同的结果。 我希望至less能力1和能力10能给出更坏的结果。
- 使用初始容量（而不是使用默认值16）可以提供显着的put（）改进 – 速度提高多达30％。
- 使用1的负载因子可以为less量对象提供相同的性能，而对于大量对象（> 100000）则可以获得更好的性能。 但是，这并不能与对象的数量成比例地提高。 我怀疑还有其他因素会影响结果。
- 对于不同数量的对象/容量，get（）性能有点不同，但是，虽然它可能会略有不同，但通常不受初始容量或负载因素的影响。
编辑2：在我的部分也添加一些图表。 这里是一个说明负载因子0.75和1之间的区别，在我初始化HashMap并填充满容量的情况下。 在y尺度上，以ms为单位的时间（越低越好），x尺度是尺寸（对象的数量）。 由于尺寸线性变化，所需时间也线性增长。
所以，让我们看看我得到了什么。 以下两个图表显示了负载因素的差异。 第一个图表显示了当HashMap被填充到容量时会发生什么; 加载因子0.75由于resize而变差。 然而，这并不总是更糟糕，而且还有各种各样的颠簸和跳跃 – 我猜测GC在这方面有一个重大的发挥。 负载系数1.25与1相同，因此不包含在图表中。
这个图表certificate0.75因resize而变差; 如果我们将HashMap填充到一半的容量，0.75不会更差，只是…不同（应该使用更less的内存，并具有不可思议的更好的迭代性能）。
还有一件事我想展示。 这是获得所有三个加载因子和不同的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); } } 好吧，为了让这个东西rest，我创build了一个testing应用程序来运行几个场景，并获得一些结果的可视化。 以下是testing的结果：
- 已经尝试了许多不同的collections大小：一百一十万一千个条目。
- 使用的密钥是由ID唯一标识的类的实例。 每个testing使用唯一键，将整数作为ID递增。
equals方法只使用ID，所以没有键映射覆盖另一个。 - 这些密钥得到一个哈希码，该哈希码由其ID号的模块剩余部分组成。 我们将这个数字称为散列限制 。 这使我能够控制预期的散列冲突的数量。 例如，如果我们的集合大小为100，那么我们将拥有ID为0到99的密钥。如果哈希限制为100，那么每个密钥都将具有唯一的哈希码。 如果散列限制是50，则密钥0将具有与密钥50相同的散列代码，1将具有与51等同的散列代码。换句话说，每个密钥的散列冲突的预期数目是散列集合的大小除以散列限制。
- 对于集合大小和散列限制的每个组合，我已经使用初始化为不同设置的哈希映射运行testing。 这些设置是加载因子，以及作为收集设置的因子表示的初始容量。 例如，集合大小为100，初始容量因子为1.25的testing将初始化初始容量为125的哈希映射。
- 每个键的值只是一个新的
Object。 - 每个testing结果都封装在Result类的一个实例中。 在所有testing结束时，结果从最坏的整体性能sorting到最好。
- put和gets的平均时间是每10次计算得出的。
- 所有testing组合都运行一次以消除JIT编译影响。 之后，testing运行实际结果。
这是这个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中创build文件夹和文件。 在另一个平台上运行时，请调整它。
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); } }
可视化输出如下：
- testing首先按收集大小划分，然后按散列限制划分。
- 对于每个testing，有一个关于平均放置时间（每10放）和平均放置时间（每10放）的输出图像。 这些图像是二维“热图”，显示初始容量和负载率的组合。
- 图像中的颜色基于从最佳到最差结果的归一化尺度上的平均时间，从饱和绿到饱和红。 换句话说，最好的时间将是完全的绿色，而最糟糕的时间将是完全的红色。 两个不同的时间测量不应该有相同的颜色。
- 颜色贴图是分别计算投入和获取的，但包含所有testing的各自类别。
- 可视化显示其x轴上的初始容量，以及y轴上的负载因子。
不用再说了，我们来看看结果。 我将从put的结果开始。
把结果
收集大小：100.哈希限制：50.这意味着每个哈希代码应该出现两次，每个其他的密钥在哈希映射中发生冲突。
那么，这并不是很好。 我们看到，有一个大的热点，初始容量比集合大小高25％，负载因子为1.左下angular的performance不佳。
收集大小：100.哈希值限制：90.十个密钥中有一个具有重复的哈希码。
这是一个稍微更现实的场景，没有一个完美的散列函数，但仍有10％的过载。 热点消失了，但是初始容量低和负载因数低的组合显然不起作用。
collections大小：100。哈希限制：100。每个键作为自己独特的哈希码。 如果有足够的水桶，不会有碰撞。
载荷系数为1的初始容量为100似乎很好。 令人惊讶的是，具有较低负载因子的较高初始容量不一定是好的。
收集规模：1000.哈希限制：500.这里越来越严重，有1000个条目。 就像在第一个testing中，有一个2到1的哈希过载。
左下angular还是不太好。 但是初始计数/高负荷系数较低和初始计数/较低负荷系数较高的组合似乎是对称的。
收集大小：1000.哈希限制：900.这意味着十个哈希码中将有一个会发生两次。 碰撞的合理情况。
有一些非常有趣的事情发生在初始容量不太可能的情况下，负载因子高于1的容量太低，这与直觉相反。 否则，还是挺对称的。
收集规模：1000.哈希限制：990.一些碰撞，但只有less数。 在这方面相当现实。
我们在这里有一个很好的对称性。 左下angular仍然不是最佳状态，但组合1000初始容量/1.0负载系数与1250初始容量/0.75负载系数处于同一水平。
集合大小：1000.哈希限制：1000.没有重复的哈希代码，但现在样本大小为1000。
这里说的不多。 较高的初始容量与0.75的负载系数的组合看起来略微优于1000个初始容量与负载系数1的组合。
collections大小：100_000。 哈希限制：10_000。 好吧，现在情况变得严重了，每个密钥的样本量为十万个和100个散列码重复。
哎呀！ 我认为我们发现了我们较低的频谱。 一个负载因子为1的集合大小的初始容量在这里performance得非常好，但除此之外，它已遍布整个商店。
collections大小：100_000。 哈希限制：90_000。 比以前的testing更现实一些，这里我们已经有了10％的散列码过载。
左下angular仍然是不可取的。 较高的初始容量效果最好。
collections大小：100_000。 哈希限制：99_000。 好的场景，这个。 一个哈希码过载1％的大集合。
以负载因子1作为初始容量使用确切的收集大小在这里胜出！ 虽然稍微大一点的初始化能力工作得很好。
collections大小：100_000。 哈希限制：100_000。 大的那个。 具有完美散列函数的最大集合。
这里有些令人惊讶的东西。 初始容量为50％的额外空间，负载系数为1。
好吧，这就是投入。 现在，我们将检查获取。 记住，下面的地图都是相对于最佳/最差的获得时间，投入时间不再考虑。
获得结果
收集大小：100.哈希限制：50.这意味着每个哈希代码应该出现两次，其他所有的密钥都要在哈希映射中碰撞。
呃…什么？
收集大小：100.哈希值限制：90.十个密钥中有一个具有重复的哈希码。
哇，耐莉！ 这是与提问者的问题相关的最可能的情况，显然最初的容量为100，负载因子为1是这里最糟糕的事情之一！ 我发誓我没有假的。
collections大小：100。哈希限制：100。每个键作为自己独特的哈希码。 没有碰撞预计。
这看起来更和平一些。 大致相同的结果全线。
集合大小：1000.哈希限制：500.就像在第一个testing中，哈希超载为2比1，但现在有更多的条目。
看起来像任何设置将产生一个体面的结果在这里。
收集大小：1000.哈希限制：900.这意味着十个哈希码中将有一个会发生两次。 碰撞的合理情况。
就像这样的设置，我们在一个奇怪的地方出现exception。
收集规模：1000.哈希限制：990.一些碰撞，但只有less数。 在这方面相当现实。
除了具有较高的初始容量和较低的负载因数的组合外，其他地方都有不俗的performance。 我期望这个投入，因为两个哈希映射resize可能是预期的。 但是为什么呢？
集合大小：1000.哈希限制：1000.没有重复的哈希代码，但现在样本大小为1000。
一个完全不引人注目的可视化。 这似乎工作，不pipe是什么。
collections大小：100_000。 哈希限制：10_000。 再次进入100K，有很多哈希码重叠。
它看起来不漂亮，虽然不好的地方是非常本地化的。 这里的performance似乎很大程度上取决于设置之间的某种协同作用。
collections大小：100_000。 哈希限制：90_000。 比以前的testing更现实一些，这里我们已经有了10％的散列码过载。
很大的差异，虽然如果你斜视你可以看到一个箭头指向右上angular。
collections大小：100_000。 哈希限制：99_000。 好的场景，这个。 一个哈希码过载1％的大集合。
非常混乱。 这里很难find很多结构。
collections大小：100_000。 哈希限制：100_000。 大的那个。 具有完美散列函数的最大集合。
任何人都认为这开始看起来像Atarigraphics？ 这似乎有利于收集大小的初始能力，即-25％或+ 50％。
好的，现在是时候得出结论了
- 关于投放时间：您将希望避免初始能力低于预期的地图条目数量。 如果事先知道确切的数字，那么这个数字或稍高于它的东西似乎是最好的。 由于较早的哈希映射resize，高负载因子可以抵消较低的初始容量。 对于更高的初始能力，他们似乎并不重要。
- 关于获得时间：结果在这里有点混乱。 没有太多的结论。 它似乎非常依赖于哈希码重叠，初始容量和负载因子之间的微妙比率，以及一些据说糟糕的设置性能良好，并且设置良好。
- 当谈到关于Java性能的假设时，我显然充满了垃圾。 事实是，除非你完全调整你的设置来实现
HashMap，否则结果将会遍布整个地方。 如果有一件事要做，那就是16的默认初始大小对于除了最小的地图之外的任何东西都是有点愚蠢的，所以如果您对于大小的顺序有什么样的想法，可以使用一个构造函数来设置初始大小这将是。 - 我们在这里测量纳秒。 每10次放置的最佳平均时间是1179纳秒，而我的机器最差的是5105纳秒。 每10次获得的最佳平均时间是547纳秒，最差的是3484纳秒。 这可能是一个因素6的差异，但我们说不到一毫秒。 在比原来的海报头脑大得多的藏品上。
那么，就是这样。 我希望我的代码没有一些可怕的监督，使我在这里发布的一切无效。 这很有趣，而且我已经了解到，最终你可能会依靠Java来完成工作，而不是期望与微小的优化有很大的区别。 这并不是说某些东西不应该被避免，但是我们主要讨论的是在循环中构造冗长的string，使用错误的数据结构和O（n ^ 3）algorithm。
这是一个相当不错的主题，除了有一个关键的东西你失踪。 你说：
奇怪的是，容量，容量+1，容量+2，容量-1甚至容量-10都会产生完全相同的结果。 我希望至less能力1和能力10能给出更坏的结果。
源代码跳转初始容量是内部次高功耗。 这意味着，例如，初始容量513,600,700,800,900,1000和1024将全部使用相同的初始容量（1024）。 虽然这不会使@G_H所做的testing无效，但在分析结果之前应该意识到这一点。 这确实解释了一些testing的奇怪行为。
这是JDK源代码的构造函数：
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
跟101一起去吧 我实际上并不确定这是否有必要，但是不可能一劳永逸找出答案。
…只需添加1 。
编辑：我的答案的一些理由。
首先，我假设你的HashMap不会超过100 ; 如果是这样，则应该保持原来的负载因子。 同样，如果您担心的是性能问题， 请按原样保留负载因数 。 如果你关心的是内存，你可以通过设置静态大小来保存一些内存。 如果你在内存中占用很多东西，这可能是值得的。 即存储许多地图，或创build堆空间应力大小的地图。
其次，我select了值101因为它提供了更好的可读性…如果我之后查看代码，看到你已经将初始容量设置为100并且用100元素加载它，那么我要去必须通读Javadoc，以确保在达到100时不会resize。 当然，我不会在那里find答案，所以我不得不看源头。 这是不值得的…只是把它留下来，每个人都很高兴，没有人在寻找java.util.HashMap的源代码。 Hoorah。
第三，声称在负载因子为1 将 HashMap设置为您所期望的确切容量将会导致您的查找和插入性能 “不正确，即使它是以粗体显示的。
…如果你有n桶，你随机把n物品分配到n桶里，那么你最终会得到同一个桶里的物品，当然……但那不是世界末日…在实践中，这只是一个更多的等于比较。 实际上，尤其是， 当你考虑替代方法是将n项目分配到n/0.75桶时，差别不大。
没有必要把我的话…
快速testing代码：
static Random r = new Random(); public static void main(String[] args){ int[] tests = {100, 1000, 10000}; int runs = 5000; float lf_sta = 1f; float lf_dyn = 0.75f; for(int t:tests){ System.err.println("=======Test Put "+t+""); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); long norm_put = testInserts(map, t, runs); System.err.print("Norm put:"+norm_put+" ms. "); int cap_sta = t; map = new HashMap<Integer,Integer>(cap_sta, lf_sta); long sta_put = testInserts(map, t, runs); System.err.print("Static put:"+sta_put+" ms. "); int cap_dyn = (int)Math.ceil((float)t/lf_dyn); map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn); long dyn_put = testInserts(map, t, runs); System.err.println("Dynamic put:"+dyn_put+" ms. "); } for(int t:tests){ System.err.println("=======Test Get (hits) "+t+""); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); fill(map, t); long norm_get_hits = testGetHits(map, t, runs); System.err.print("Norm get (hits):"+norm_get_hits+" ms. "); int cap_sta = t; map = new HashMap<Integer,Integer>(cap_sta, lf_sta); fill(map, t); long sta_get_hits = testGetHits(map, t, runs); System.err.print("Static get (hits):"+sta_get_hits+" ms. "); int cap_dyn = (int)Math.ceil((float)t/lf_dyn); map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn); fill(map, t); long dyn_get_hits = testGetHits(map, t, runs); System.err.println("Dynamic get (hits):"+dyn_get_hits+" ms. "); } for(int t:tests){ System.err.println("=======Test Get (Rand) "+t+""); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); fill(map, t); long norm_get_rand = testGetRand(map, t, runs); System.err.print("Norm get (rand):"+norm_get_rand+" ms. "); int cap_sta = t; map = new HashMap<Integer,Integer>(cap_sta, lf_sta); fill(map, t); long sta_get_rand = testGetRand(map, t, runs); System.err.print("Static get (rand):"+sta_get_rand+" ms. "); int cap_dyn = (int)Math.ceil((float)t/lf_dyn); map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn); fill(map, t); long dyn_get_rand = testGetRand(map, t, runs); System.err.println("Dynamic get (rand):"+dyn_get_rand+" ms. "); } } public static long testInserts(HashMap<Integer,Integer> map, int test, int runs){ long b4 = System.currentTimeMillis(); for(int i=0; i<runs; i++){ fill(map, test); map.clear(); } return System.currentTimeMillis()-b4; } public static void fill(HashMap<Integer,Integer> map, int test){ for(int j=0; j<test; j++){ if(map.put(r.nextInt(), j)!=null){ j--; } } } public static long testGetHits(HashMap<Integer,Integer> map, int test, int runs){ long b4 = System.currentTimeMillis(); ArrayList<Integer> keys = new ArrayList<Integer>(); keys.addAll(map.keySet()); for(int i=0; i<runs; i++){ for(int j=0; j<test; j++){ keys.get(r.nextInt(keys.size())); } } return System.currentTimeMillis()-b4; } public static long testGetRand(HashMap<Integer,Integer> map, int test, int runs){ long b4 = System.currentTimeMillis(); for(int i=0; i<runs; i++){ for(int j=0; j<test; j++){ map.get(r.nextInt()); } } return System.currentTimeMillis()-b4; }
检测结果：
=======Test Put 100 Norm put:78 ms. Static put:78 ms. Dynamic put:62 ms. =======Test Put 1000 Norm put:764 ms. Static put:763 ms. Dynamic put:748 ms. =======Test Put 10000 Norm put:12921 ms. Static put:12889 ms. Dynamic put:12873 ms. =======Test Get (hits) 100 Norm get (hits):47 ms. Static get (hits):31 ms. Dynamic get (hits):32 ms. =======Test Get (hits) 1000 Norm get (hits):327 ms. Static get (hits):328 ms. Dynamic get (hits):343 ms. =======Test Get (hits) 10000 Norm get (hits):3304 ms. Static get (hits):3366 ms. Dynamic get (hits):3413 ms. =======Test Get (Rand) 100 Norm get (rand):63 ms. Static get (rand):46 ms. Dynamic get (rand):47 ms. =======Test Get (Rand) 1000 Norm get (rand):483 ms. Static get (rand):499 ms. Dynamic get (rand):483 ms. =======Test Get (Rand) 10000 Norm get (rand):5190 ms. Static get (rand):5362 ms. Dynamic get (rand):5236 ms.
re: ↑ — there's about this →||← much difference between the different settings .
With respect to my original answer (the bit above the first horizontal line), it was deliberately glib because in most cases , this type of micro-optimising is not good .
From the HashMap JavaDoc:
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
So if you're expecting 100 entries, perhaps a load factor of 0.75 and an initial capacity of ceiling(100/0.75) would be best. That comes down to 134.
I have to admit, I'm not certain why lookup cost would be greater for a higher load factor. Just because the HashMap is more "crowded" doesn't mean that more objects will be placed in the same bucket, right? That only depends on their hash code, if I'm not mistaken. So assuming a decent hash code spread, shouldn't most cases still be O(1) regardless of load factor?
EDIT: I should read more before posting… Of course the hash code cannot directly map to some internal index. It must be reduced to a value that fits the current capacity. Meaning that the greater your initial capacity, the smaller you can expect the number of hash collisions to be. Choosing an initial capacity exactly the size (or +1) of your object set with a load factor of 1 will indeed make sure that your map is never resized. However, it will kill your lookup and insertion performance . A resize is still relatively quick and would only occur maybe once, while lookups are done on pretty much any relevant work with the map. As a result, optimizing for quick lookups is what you really want here. You can combine that with never having to resize by doing as the JavaDoc says: take your required capacity, divide by an optimal load factor (eg 0.75) and use that as the initial capacity, with that load factor. Add 1 to make sure rounding doesn't get you.
