问题描述
我正在尝试找出特定情况下的最佳容量和负载系数.我想我明白了它的要点，但我仍然会感谢比我更有知识的人的确认.:)
I'm trying to figure out the optimal capacity and load factor for a specific case. I think I got the gist of it, but I'd still be thankful for a confirmation from someone more knowledgable than me. :)
如果我知道我的 HashMap 将被填满以包含 100 个对象，并且大部分时间将花费 100 个对象，我猜测最佳值是初始容量 100 和负载因子 1?或者我需要容量 101，还是有其他问题?
If I know that my HashMap will fill up to contain, say, 100 objects, and will spend most of the time having 100 objects, I'm guessing that the optimal values are initial capacity 100 and load factor 1? Or do I need capacity 101, or are there any other gotchas?
好的，我留出几个小时进行了一些测试.结果如下:
OK, I set aside a few hours and did some testing. Here are the results:
- 奇怪的是，容量、容量+1、容量+2、容量-1 甚至容量-10 都会产生完全相同的结果.我预计至少容量 1 和容量 10 会产生更差的结果.
- 使用初始容量(而不是使用默认值 16)可以显着提高 put() - 速度提高 30%.
- 使用 1 的负载因子可以为少量对象提供相同的性能，而为大量对象 (>100000) 提供更好的性能.然而，这并没有与对象的数量成比例地提高；我怀疑还有其他因素会影响结果.
- get() 性能对于不同数量的对象/容量会有所不同，但尽管可能因情况而异，但通常不受初始容量或负载因子的影响.
我也添加了一些图表.这是说明负载因子 0.75 和 1 之间差异的一个例子，在我初始化 HashMap 并将其填充到最大容量的情况下.在 y 尺度上是以毫秒为单位的时间(越低越好)，x 尺度是大小(对象数).由于大小呈线性变化，因此所需时间也呈线性增长.
Adding some charts on my part as well. Here's the one illustrating difference between load factor 0.75 and 1, in cases where I initialize HashMap and fill it up to full capacity. On y scale is time in ms (lower is better), and x scale is size (number of objects). Since size changes linearly, the time required grows linearly as well.
那么，让我们看看我得到了什么.以下两个图表显示了负载因子的差异.第一个图表显示了当 HashMap 被填满时会发生什么；由于调整大小，负载因子 0.75 的性能更差.然而，情况并非总是更糟，而且有各种各样的颠簸和跳跃——我猜 GC 在这方面发挥了重要作用.负载因子 1.25 的性能与 1 相同，因此不包含在图表中.
So, let's see what I got. The following two charts show the difference in load factors. First chart shows what happens when HashMap is filled to capacity; load factor 0.75 performs worse because of resizing. However, it's not consistently worse, and there are all sorts of bumps and hops - I guess that GC has a major play in this. Load factor 1.25 performs the same as 1, so it's not included in the chart.
此图表证明 0.75 因调整大小而变差；如果我们将 HashMap 填充到一半容量，0.75 并不差，只是......不同(它应该使用更少的内存并且具有更好的迭代性能).
This chart proves that 0.75 was worse due to resizing; if we fill the HashMap to half capacity, 0.75 is not worse, just... different (and it should use less memory and have unnoticably better iteration performance).
还有一件事我想展示.这是获得所有三个负载因子和不同 HashMap 大小的性能.除了负载因子为 1 的一个峰值之外，始终保持不变，但有一点变化.我真的很想知道那是什么(可能是 GC，但谁知道).
One more thing I want to show. This is get performance for all three load factors and different HashMap sizes. Consistently constant with a little variation, except for one spike for load factor 1. I'd really want to know what that is (probably GC, but who knows).
这里是感兴趣的人的代码:
And here's the code for those interested:
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(" ");
}
}
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(" ");
}
}
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);
}
}
推荐答案
好吧，为了解决这个问题，我创建了一个测试应用程序来运行几个场景并获得一些可视化的结果.以下是测试的完成方式:
Alright, to put this thing to rest, I've created a test app to run a couple of scenarios and get some visualizations of the results. Here's how the tests are done:
- 已经尝试了许多不同的集合大小:一百、一千和十万个条目.
- 使用的键是由 ID 唯一标识的类的实例.每个测试都使用唯一的键，并以递增的整数作为 ID.
equals方法只使用 ID，因此没有键映射会覆盖另一个. - 密钥会获得一个哈希码，该哈希码由其 ID 的模块剩余部分与某个预设数字组成.我们将该数字称为哈希限制.这使我能够控制预期的哈希冲突的数量.例如，如果我们的集合大小为 100，我们将拥有 ID 范围为 0 到 99 的键.如果哈希限制为 100，则每个键将具有唯一的哈希码.如果哈希限制为 50，则密钥 0 将具有与密钥 50 相同的哈希码，1 将具有与 51 相同的哈希码等.换句话说，每个密钥的预期哈希冲突数是集合大小除以哈希限制.
- 对于集合大小和哈希限制的每种组合，我使用不同设置初始化的哈希映射来运行测试.这些设置是负载因子，以及表示为集合设置因子的初始容量.例如，一个集合大小为 100 且初始容量因子为 1.25 的测试将初始化一个初始容量为 125 的哈希映射.
- 每个键的值只是一个新的
Object. - 每个测试结果都封装在一个 Result 类的实例中.在所有测试结束时，结果按总体性能从最差到最好的顺序排列.
- put 和 get 的平均时间是按每 10 个 puts/get 计算的.
- 所有测试组合都运行一次，以消除 JIT 编译影响.之后，将运行测试以获得实际结果.
- A number of different collection sizes have been tried: one hundred, one thousand and one hundred thousand entries.
- The keys used are instances of a class that are uniquely identified by an ID. Each test uses unique keys, with incrementing integers as IDs. The
equalsmethod only uses the ID, so no key mapping overwrites another one. - The keys get a hash code that consists of the module remainder of their ID against some preset number. We'll call that number the hash limit. This allowed me to control the number of hash collisions that would be expected. For example, if our collection size is 100, we'll have keys with IDs ranging from 0 to 99. If the hash limit is 100, every key will have a unique hash code. If the hash limit is 50, key 0 will have the same hash code as key 50, 1 will have the same hash code as 51 etc. In other words, the expected number of hash collisions per key is the collection size divided by the hash limit.
- For each combination of collection size and hash limit, I've run the test using hash maps initialized with different settings. These settings are the load factor, and an initial capacity that is expressed as a factor of the collection setting. For example, a test with a collection size of 100 and an initial capacity factor of 1.25 will initialize a hash map with an initial capacity of 125.
- The value for each key is simply a new
Object. - Each test result is encapsulated in an instance of a Result class. At the end of all tests, the results are ordered from worst overall performance to best.
- The average time for puts and gets is calculated per 10 puts/gets.
- All test combinations are run once to eliminate JIT compilation influence. After that, the tests are run for actual results.
课程如下:
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:emp 中创建文件夹和文件.在其他平台上运行时，调整此项.
Running this might take a while. The results are printed out on standard out. You might notice I've commented out a line. That line calls a visualizer that outputs visual representations of the results to png files. The class for this is given below. If you wish to run it, uncomment the appropriate line in the code above. Be warned: the visualizer class assumes you're running on Windows and will create folders and files in C:emp. When running on another platform, adjust this.
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 次获取)的输出图像.这些图像是二维的热图".根据初始容量和负载系数的组合显示一种颜色.
- 图像中的颜色基于从最佳结果到最差结果的标准化范围内的平均时间，范围从饱和绿色到饱和红色.换句话说，最好的时间是全绿的，而最差的时间是全红的.两个不同的时间测量值决不能使用相同的颜色.
- 颜色图是针对 put 和 get 单独计算的，但包含其各自类别的所有测试.
- 图表在 x 轴上显示初始容量，在 y 轴上显示负载系数.
事不宜迟，让我们来看看结果.我将从 puts 的结果开始.
Without further ado, let's take a look at the results. I'll start with the results for puts.
放置结果
集合大小:100.哈希限制:50.这意味着每个哈希码应该出现两次，并且在哈希映射中每隔一个键就会发生冲突.
Collection size: 100. Hash limit: 50. This means each hash code should occur twice and every other key collides in the hash map.
嗯，这并不是一开始就很好.我们看到有一个大的热点，初始容量比集合大小高 25%，负载因子为 1.左下角的性能不太好.
Well, that doesn't start off very good. We see that there's a big hotspot for an initial capacity 25% above the collection size, with a load factor of 1. The lower left corner doesn't perform too well.
集合大小:100.哈希限制:90.十分之一的键具有重复的哈希码.
Collection size: 100. Hash limit: 90. One in ten keys has a duplicate hash code.
这是一个稍微现实一点的场景，没有完美的哈希函数，但仍然有 10% 的过载.热点没有了，但低初始容量和低负载率的组合显然行不通.
This is a slightly more realistic scenario, not having a perfect hash function but still 10% overload. The hotspot is gone, but the combination of a low initial capacity with a low load factor obviously doesn't work.
集合大小:100.哈希限制:100.每个键作为自己唯一的哈希码.如果有足够的桶，则不会发生冲突.
Collection size: 100. Hash limit: 100. Each key as its own unique hash code. No collisions expected if there are enough buckets.
负载因子为 1 的初始容量为 100 似乎很好.令人惊讶的是，较高的初始容量和较低的负载率并不一定是好的.
An initial capacity of 100 with a load factor of 1 seems fine. Surprisingly, a higher initial capacity with a lower load factor isn't necessarily good.
集合大小:1000.哈希限制:500.这里变得越来越严重，有 1000 个条目.就像在第一个测试中一样，有 2 比 1 的哈希重载.
Collection size: 1000. Hash limit: 500. It's getting more serious here, with 1000 entries. Just like in the first test, there's a hash overload of 2 to 1.
左下角还是不行.但在较低初始计数/高负载因子和较高初始计数/低负载因子的组合之间似乎存在对称性.
The lower left corner is still not doing well. But there seems to be a symmetry between the combo of lower initial count/high load factor and higher initial count/low load factor.
集合大小:1000.哈希限制:900.这意味着十分之一的哈希码会出现两次.关于碰撞的合理场景.
Collection size: 1000. Hash limit: 900. This means one in ten hash codes will occur twice. Reasonable scenario regarding collisions.
初始容量太低且负载因子高于 1 的不太可能的组合发生了一些非常有趣的事情，这是相当违反直觉的.否则，还是挺对称的.
There's something very funny going on with the unlikely combo of an initial capacity that's too low with a load factor above 1, which is rather counter-intuitive. Otherwise, still quite symmetrical.
集合大小:1000.哈希限制:990.一些冲突，但只有少数.在这方面相当现实.
Collection size: 1000. Hash limit: 990. Some collisions, but only a few. Quite realistic in this respect.
我们在这里有一个很好的对称性.左下角仍然不是最理想的，但 1000 初始容量/1.0 负载系数与 1250 初始容量/0.75 负载系数的组合处于同一水平.
We've got a nice symmetry here. Lower left corner is still sub-optimal, but the combos 1000 init capacity/1.0 load factor versus 1250 init capacity/0.75 load factor are at the same level.
集合大小:1000.哈希限制:1000.没有重复的哈希码，但现在样本大小为 1000.
Collection size: 1000. Hash limit: 1000. No duplicate hash codes, but now with a sample size of 1000.
这里不多说了.较高的初始容量与 0.75 的负载因子的组合似乎略优于 1000 个初始容量与负载因子 1 的组合.
Not much to be said here. The combination of a higher initial capacity with a load factor of 0.75 seems to slightly outperform the combination of 1000 initial capacity with a load factor of 1.
集合大小:100_000.哈希限制:10_000.好吧，现在情况越来越严重了，每个键的样本大小为 10 万和 100 个哈希码重复.
Collection size: 100_000. Hash limit: 10_000. Alright, it's getting serious now, with a sample size of one hundred thousand and 100 hash code duplicates per key.
哎呀！我认为我们找到了较低的频谱.加载因子为 1 的集合大小的初始容量在这里做得非常好，但除此之外，它遍布整个商店.
Yikes! I think we found our lower spectrum. An init capacity of exactly the collection size with a load factor of 1 is doing really well here, but other than that it's all over the shop.
集合大小:100_000.哈希限制:90_000.比之前的测试更真实一点，这里我们的哈希码过载了 10%.
Collection size: 100_000. Hash limit: 90_000. A bit more realistic than the previous test, here we've got a 10% overload in hash codes.
左下角仍然不可取.较高的初始容量效果最佳.
The lower left corner is still undesirable. Higher initial capacities work best.
集合大小:100_000.哈希限制:99_000.好剧本，这个.具有 1% 哈希码过载的大型集合.
Collection size: 100_000. Hash limit: 99_000. Good scenario, this. A large collection with a 1% hash code overload.
使用确切的集合大小作为加载因子为 1 的初始化容量在这里胜出！不过，稍大一点的初始化容量也能很好地工作.
Using the exact collection size as init capacity with a load factor of 1 wins out here! Slightly larger init capacities work quite well, though.
集合大小:100_000.哈希限制:100_000.大的那个.具有完美哈希函数的最大集合.
Collection size: 100_000. Hash limit: 100_000. The big one. Largest collection with a perfect hash function.
这里有一些令人惊讶的东西.在负载系数为 1 的情况下，具有 50% 额外空间的初始容量获胜.
Some surprising stuff here. An initial capacity with 50% additional room at a load factor of 1 wins.
好的，看跌期权就是这样.现在，我们将检查获取.请记住，以下地图都是相对于最佳/最差获取时间的，不再考虑放置时间.
Alright, that's it for the puts. Now, we'll check the gets. Remember, the below maps are all relative to best/worst get times, the put times are no longer taken into account.
获得结果
集合大小:100.哈希限制:50.这意味着每个哈希码应该出现两次，并且每个其他键都应该在哈希映射中发生冲突.
Collection size: 100. Hash limit: 50. This means each hash code should occur twice and every other key was expected to collide in the hash map.
呃……什么?
集合大小:100.哈希限制:90.十分之一的键具有重复的哈希码.
Collection size: 100. Hash limit: 90. One in ten keys has a duplicate hash code.
哇，耐莉！这是与提问者的问题相关的最可能的情况，显然负载因子为 1 的初始容量为 100 是这里最糟糕的事情之一！我发誓我没有伪造这个.
Whoa Nelly! This is the most likely scenario to correlate with the asker's question, and apparently an initial capacity of 100 with a load factor of 1 is one of the worst things here! I swear I didn't fake this.
集合大小:100.哈希限制:100.每个键作为自己唯一的哈希码.预计不会发生冲突.
Collection size: 100. Hash limit: 100. Each key as its own unique hash code. No collisions expected.
这看起来更平静一些.总体结果基本相同.
This looks a bit more peaceful. Mostly the same results across the board.
集合大小:1000.哈希限制:500.就像在第一个测试中一样，哈希重载为 2 比 1，但现在有更多条目.
Collection size: 1000. Hash limit: 500. Just like in the first test, there's a hash overload of 2 to 1, but now with a lot more entries.
看起来任何设置都会在这里产生不错的结果.
Looks like any setting will yield a decent result here.
集合大小:1000.哈希限制:900.这意味着十分之一的哈希码会出现两次.关于碰撞的合理场景.
Collection size: 1000. Hash limit: 900. This means one in ten hash codes will occur twice. Reasonable scenario regarding collisions.
就像这个设置的 put 一样，我们在一个奇怪的地方遇到了异常.
And just like with the puts for this setup, we get an anomaly in a strange spot.
集合大小:1000.哈希限制:990.一些冲突，但只有少数.在这方面相当现实.
Collection size: 1000. Hash limit: 990. Some collisions, but only a few. Quite realistic in this respect.
到处都有不错的性能，除了高初始容量和低负载率的组合.我希望看跌期权是这样的，因为可能需要两个哈希映射调整大小.但是为什么会这样呢?
Decent performance everywhere, save for the combination of a high initial capacity with a low load factor. I'd expect this for the puts, since two hash map resizes might be expected. But why on the gets?
集合大小:1000.哈希限制:1000.没有重复的哈希码，但现在样本大小为 1000.
Collection size: 1000. Hash limit: 1000. No duplicate hash codes, but now with a sample size of 1000.
完全不引人注意的可视化.无论如何，这似乎都有效.
A wholly unspectacular visualization. This seems to work no matter what.
集合大小:100_000.哈希限制:10_000.再次进入 100K，大量哈希码重叠.
Collection size: 100_000. Hash limit: 10_000. Going into the 100K again, with a whole lot of hash code overlap.
它看起来并不漂亮，虽然坏点非常本地化.这里的性能似乎很大程度上取决于设置之间的某种协同作用.
It doesn't look pretty, although the bad spots are very localized. Performance here seems to depend largely on a certain synergy between settings.
集合大小:100_000.哈希限制:90_000.比之前的测试更真实一点，这里我们的哈希码过载了 10%.
Collection size: 100_000. Hash limit: 90_000. A bit more realistic than the previous test, here we've got a 10% overload in hash codes.
差异很大，虽然如果你眯着眼睛可以看到一个指向右上角的箭头.
Much variance, although if you squint you can see an arrow pointing to the upper right corner.
集合大小:100_000.哈希限制:99_000.好剧本，这个.具有 1% 哈希码过载的大型集合.
Collection size: 100_000. Hash limit: 99_000. Good scenario, this. A large collection with a 1% hash code overload.
非常混乱.在这里很难找到很多结构.
Very chaotic. It's hard to find much structure here.
集合大小:100_000.哈希限制:100_000.大的那个.具有完美哈希函数的最大集合.
Collection size: 100_000. Hash limit: 100_000. The big one. Largest collection with a perfect hash function.
还有其他人认为这开始看起来像 Atari 图形吗?这似乎有利于集合大小的初始容量，-25% 或 +50%.
Anyone else thinks this is starting to look like Atari graphics? This seems to favour an initial capacity of exactly the collection size, -25% or +50%.
好吧，现在该下结论了……
Alright, it's time for conclusions now...
- 关于放置时间:您希望避免初始容量低于预期的映射条目数.如果事先知道确切的数字，则该数字或略高于它的数字似乎效果最好.由于较早的哈希映射调整大小，高负载因子可以抵消较低的初始容量.对于更高的初始容量，它们似乎并不那么重要.
- 关于获取时间:这里的结果有点混乱.没有太多可以总结的.它似乎在很大程度上依赖于哈希码重叠、初始容量和负载因子之间的细微比率，一些据称糟糕的设置表现良好，而良好的设置表现糟糕.
- 当谈到关于 Java 性能的假设时，我显然满脑子都是废话.事实是，除非您将设置完美地调整为
HashMap的实现，否则结果将无处不在.如果要从中删除一件事，那就是默认初始大小 16 对于除最小地图之外的任何东西都有些愚蠢，因此如果您对大小顺序有任何想法，请使用设置初始大小的构造函数会的. - 我们在这里以纳秒为单位进行测量.在我的机器上，每 10 个 put 的最佳平均时间是 1179 ns，而最差的平均时间是 5105 ns.每 10 次获取的最佳平均时间为 547 ns，最差为 3484 ns.这可能是 6 倍的差异，但我们说的时间不到一毫秒.在比原始海报想象的要大得多的系列上.
- Regarding put times: you'll wish to avoid initial capacities that are lower than the expected number of map entries. If an exact number is known beforehand, that number or something slightly above it seems to work best. High load factors can offset lower initial capacities due to earlier hash map resizes. For higher initial capacities, they don't seem to matter that much.
- Regarding get times: results are slightly chaotic here. There's not much to conclude. It seems to rely very much on subtle ratios between hash code overlap, initial capacity and load factor, with some supposedly bad setups performing well and good setups performing awfully.
- I'm apparently full of crap when it comes to assumptions about Java performance. The truth is, unless you are perfectly tuning your settings to the implementation of
HashMap, the results are going to be all over the place. If there's one thing to take away from this, it's that the default initial size of 16 is a bit dumb for anything but the smallest maps, so use a constructor that sets the initial size if you have any sort of idea about what order of size it's going to be. - We're measuring in nanoseconds here. The best average time per 10 puts was 1179 ns and the worst 5105 ns on my machine. The best average time per 10 gets was 547 ns and the worst 3484 ns. That may be a factor 6 difference, but we're talking less than a millisecond. On collections that are vastly larger than what the original poster had in mind.
嗯，就是这样.我希望我的代码没有一些可怕的疏忽，使我在这里发布的所有内容都无效.这很有趣，而且我了解到，最终您可能完全依赖 Java 来完成它的工作，而不是期望与微小的优化有很大的不同.这并不是说某些东西不应该避免，而是我们主要讨论的是在 for 循环中构造冗长的字符串，使用错误的数据结构并制作 O(n^3) 算法.
Well, that's it. I hope my code doesn't have some horrendous oversight that invalidates everything I've posted here. This has been fun, and I've learned that in the end you may just as well rely on Java to do its job than to expect much difference from tiny optimizations. That is not to say that some stuff shouldn't be avoided, but then we're mostly talking about constructing lengthy Strings in for loops, using the wrong datastructures and making O(n^3) algorithms.
这篇关于固定大小的 HashMap 的最佳容量和负载因子是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！