고정 크기 해시 맵에 대한 최적의 용량과 부하 계수는 얼마입니까?
특정 사례에 가장 적합한 용량과 부하 계수를 알아내려고 합니다.요지는 알 것 같지만, 그래도 저보다 지식이 있는 분으로부터 확인을 받고 싶습니다. :)
해시맵에 최대 100개의 객체가 포함되어 대부분의 시간을 100개의 객체로 보낼 수 있다는 것을 알게 되면 최적의 값은 초기 용량 100과 부하 계수 1이 될 것으로 추측됩니다.아니면 용량 101이 필요합니까, 아니면 다른 gotcha가 필요합니까?
편집: 네, 몇 시간 정도 시간을 두고 몇 가지 테스트를 실시했습니다.결과는 다음과 같습니다.
- 이상하게도 용량, 용량+1, 용량+2, 용량-1, 용량-10 모두 정확히 동일한 결과를 산출합니다.적어도 capacity-1과 capacity-10은 결과가 나빠질 것으로 예상됩니다.
- (기본값 16이 아닌) 초기 용량을 사용하면 put()이 최대 30% 빠르게 향상됩니다.
- 부하율을 1로 하면 적은 수의 오브젝트에서는 동일한 퍼포먼스를 얻을 수 있으며, 많은 수의 오브젝트에서는 퍼포먼스가 향상됩니다(100000 이상).그러나 이것은 개체 수에 비례하여 개선되는 것이 아니라 결과에 영향을 미치는 추가 요인이 있을 것으로 생각됩니다.
- get() 퍼포먼스는 오브젝트 수/용량마다 약간 다르지만 일반적으로 초기 용량이나 부하 계수의 영향을 받지 않습니다.
EDIT2: 제 파트에도 차트를 추가합니다.다음은 HashMap을 초기화하고 최대 용량까지 채우는 경우의 로드 팩터 0.75와 1의 차이를 보여 줍니다.y 척도는 ms 단위의 시간(낮을수록 좋음)이고 x 척도는 크기(객체 수)입니다.크기가 선형적으로 변화하기 때문에 필요한 시간도 선형적으로 증가합니다.
내가 뭘 가졌는지 보자다음 두 차트는 하중 계수의 차이를 보여 줍니다.첫 번째 차트는 HashMap이 최대 용량으로 채워지면 어떻게 되는지 보여 줍니다. 로드 계수 0.75는 크기 조정으로 인해 성능이 저하됩니다.하지만, 그것은 일관되게 나쁜 것은 아니고, 온갖 종류의 요철과 깡충깡충 뛰기도 한다 - 나는 GC가 이것에 큰 역할을 한다고 생각한다.하중 계수 1.25는 1과 동일한 성능을 수행하므로 관리도에 포함되지 않습니다.
이 차트는 크기 조정으로 인해 0.75가 더 나빴다는 것을 나타냅니다. HashMap을 절반 용량으로 채우면 0.75가 더 나빴다는 것은 아닙니다. 단지...(메모리를 적게 사용하고 반복 퍼포먼스가 눈에 띄게 향상됩니다)
한 가지 더 보여드리고 싶은 게 있어요.이는 3가지 로드 팩터와 다양한 해시 맵사이즈 모두에 대해 퍼포먼스를 가져옵니다.하중 계수 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);
}
}
이 문제를 해결하기 위해 몇 가지 시나리오를 실행하고 결과를 시각화하는 테스트 앱을 만들었습니다.테스트 방법은 다음과 같습니다.
- 10만, 10만, 10만 엔트리의 다양한 컬렉션 사이즈가 시도되고 있습니다.
- 사용되는 키는 ID에 의해 일의로 식별되는 클래스의 인스턴스입니다. 로서 를 사용합니다.
equals메서드는 ID만 사용하기 때문에 키 매핑은 다른 ID를 덮어쓰지 않습니다. - 키는 ID의 나머지 모듈로 구성된 해시 코드를 미리 설정된 숫자에 대해 가져옵니다.이 숫자를 해시 한계라고 합니다.이를 통해 예상되는 해시 충돌 수를 제어할 수 있습니다.예를 들어 수집 크기가 100인 경우 ID가 0~99인 키가 있습니다.해시 제한이 100인 경우 모든 키에 고유한 해시 코드가 있습니다.해시 제한이 50인 경우 키 0은 키 50과 동일한 해시 코드를 가지며, 1은 51 등과 같은 해시 코드를 가집니다.즉, 키당 예상되는 해시 충돌 수는 수집 크기를 해시 제한으로 나눈 값입니다.
- 수집 크기와 해시 제한의 각 조합에 대해 다른 설정으로 초기화된 해시 맵을 사용하여 테스트를 실행했습니다.이러한 설정은 부하 계수 및 수집 설정의 계수로 표현되는 초기 용량입니다.예를 들어 수집 크기가 100이고 초기 용량 계수가 1.25인 테스트는 초기 용량 125의 해시 맵을 초기화합니다.
- 키입니다.
Object. - 각 테스트 결과는 결과 클래스의 인스턴스에 캡슐화됩니다.모든 테스트가 끝나면 결과는 전체 성능이 가장 나쁜 것부터 가장 좋은 것 순으로 정렬됩니다.
- 풋과 취득의 평균 시간은 10개의 풋/게트당 계산됩니다.
- 모든 테스트 조합을 한 번 실행하여 J를 제거합니다.IT 컴파일에 의한 영향.그 후 실제 결과를 위해 테스트가 실행됩니다.
수업은 다음과 같습니다.
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개당)에 관한 출력 이미지가 있습니다.이미지는 초기 용량과 부하 계수의 조합당 색상을 보여주는 2차원 "히트 맵"입니다.
- 이미지의 색상은 최상의 결과에서 최악의 결과까지의 정규화된 척도의 평균 시간을 기준으로 하며, 포화 녹색에서 포화 빨간색까지 다양합니다.즉, 가장 좋은 시간은 완전히 녹색이고 가장 나쁜 시간은 완전히 빨간색입니다.두 개의 다른 시간 측정치가 같은 색을 띠면 안 됩니다.
- 색상 지도는 풋과 겟에 대해 별도로 계산되지만, 각각의 범주에 대한 모든 테스트를 포함합니다.
- 시각화는 x축의 초기 용량과 y축의 부하 계수를 보여줍니다.
더 이상 떠들지 말고 결과를 봅시다.퍼트 결과부터 시작하겠습니다.
결과를 기입하다
수집 크기: 100. 해시 제한: 50.즉, 각 해시 코드는 2회 발생하고 다른 모든 키가 해시 맵에서 충돌합니다.
시작부터 좋지 않군초기 용량이 컬렉션 크기보다 25% 이상 크고 부하 계수가 1인 큰 핫스팟이 있습니다.왼쪽 하단 모서리가 잘 작동하지 않습니다.
수집 크기: 100. 해시 제한: 90.10개 중 1개의 키에 중복된 해시 코드가 있습니다.
이것은 완전한 해시함수는 아니지만 과부하가 10%인 조금 더 현실적인 시나리오입니다.핫스팟은 사라졌지만 낮은 초기 용량과 낮은 부하 계수의 조합은 분명히 작동하지 않습니다.
수집 크기: 100. 해시 제한: 100. 각 키는 고유한 해시 코드입니다.버킷이 충분한 경우 충돌이 예상되지 않습니다.
초기 용량 100, 부하 계수 1이면 충분할 것 같습니다.의외로 초기 용량이 크고 부하 팩터가 낮다고 해서 반드시 좋은 것은 아닙니다.
컬렉션 크기: 1000.해시 제한: 500.점점 더 심각해지고 있어요 1000개의 엔트리가 있어요첫 번째 테스트와 마찬가지로 해시 과부하가 2:1입니다.
왼쪽 하단 모서리가 아직 잘 작동하지 않습니다.그러나 낮은 초기 카운트/고부하 계수와 높은 초기 카운트/저부하 계수의 조합 사이에는 대칭성이 있는 것으로 보입니다.
컬렉션 크기: 1000.해시 제한: 900.즉, 해시 코드 10개 중1개가 2회 발생합니다.충돌에 관한 합리적인 시나리오.
초기 용량이 너무 낮고 부하 계수가 1을 초과하면 직관에 반하는 매우 흥미로운 조합이 발생합니다.그렇지 않으면, 여전히 꽤 대칭적이죠.
컬렉션 크기: 1000.해시 한계치: 990. 충돌도 있지만, 몇 가지뿐입니다.이 점에 있어서는 꽤 현실적이다.
여기 대칭이 잘 맞네요왼쪽 하단 모서리는 여전히 최적이지 않지만 콤보 1000 init capacity/1.0 로드팩터와 1250 init capacity/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 capacity가 약간 큰 경우는, 꽤 잘 동작합니다.
컬렉션 크기: 100_000.해시 제한: 100_000.큰 거.완벽한 해시 함수를 가진 가장 큰 컬렉션입니다.
여기 놀라운 것들이 있어요.부하율 1로 50%의 추가 공간이 있는 초기 용량.
좋아, 퍼트는 여기까지.자, 이제 확인해보겠습니다.다음 맵은 모두 베스트/최악의 get time에 상대적인 것으로, put time은 더 이상 고려되지 않습니다.
결과를 얻다
수집 크기: 100. 해시 제한: 50.즉, 각 해시 코드가 2회 발생하고 다른 모든 키가 해시 맵에서 충돌할 것으로 예상됩니다.
어... 뭐?
수집 크기: 100. 해시 제한: 90.10개 중 1개의 키에 중복된 해시 코드가 있습니다.
와 넬리!이것은 질문자의 질문과 관련된 가장 가능성이 높은 시나리오이며, 초기 용량이 100이고 부하 계수가 1인 것은 여기서 가장 나쁜 것 중 하나입니다.맹세컨데 이건 가짜가 아니야
수집 크기: 100. 해시 제한: 100. 각 키는 고유한 해시 코드입니다.충돌이 예상되지 않았습니다.
이게 좀 더 평화로워 보이네요.거의 모든 면에서 같은 결과입니다.
컬렉션 크기: 1000.해시 제한: 500. 첫 번째 테스트와 마찬가지로 해시 오버로드가 2대 1로 발생하지만 지금은 엔트리가 많아졌습니다.
어떤 설정으로든 괜찮은 결과를 얻을 수 있을 것 같네요.
컬렉션 크기: 1000.해시 제한: 900.즉, 해시 코드 10개 중1개가 2회 발생합니다.충돌에 관한 합리적인 시나리오.
그리고 이 셋업을 위한 풋과 마찬가지로, 우리는 이상한 곳에서 변칙적인 것을 발견합니다.
컬렉션 크기: 1000.해시 한계치: 990. 충돌도 있지만, 몇 가지뿐입니다.이 점에 있어서는 꽤 현실적이다.
어디에서나 뛰어난 퍼포먼스를 발휘.초기 용량이 크고 부하가 낮은 것을 조합하여 비용을 절약할 수고를 덜 수 있습니다.2개의 해시 맵사이즈가 예상될 수 있기 때문에, 퍼트에서는 이것을 예상할 수 있습니다.하지만 왜 도망치려 하지?
컬렉션 크기: 1000.해시 제한: 1000.중복된 해시 코드는 없지만 샘플 크기가 1000입니다.
전혀 눈에 띄지 않는 시각화입니다.이건 무슨 일이 있어도 되는 것 같아.
컬렉션 크기: 100_000.해시 제한: 10_000.해시 코드가 많이 겹쳐서 다시 10만 달러를 돌파하는 거죠
단점은 국소적인 부분이긴 하지만 예쁘지는 않아요.여기서의 퍼포먼스는, 설정간의 시너지에 크게 좌우되는 것 같습니다.
컬렉션 크기: 100_000.해시 제한: 90_000.이전 테스트보다 좀 더 현실적이죠, 여기 해시 코드에 10% 과부하가 있습니다.
많은 차이가 있지만, 눈을 가늘게 뜨면 오른쪽 상단 모서리를 가리키는 화살표가 보입니다.
컬렉션 크기: 100_000.해시 제한: 99_000.좋은 시나리오야, 이거요.해시 코드 오버로드가 1%인 대규모 컬렉션입니다.
너무 혼란스러워.이곳에서는 많은 구조를 찾기가 어렵다.
컬렉션 크기: 100_000.해시 제한: 100_000.큰 거.완벽한 해시 함수를 가진 가장 큰 컬렉션입니다.
이게 아타리 그래픽처럼 보이기 시작했다고 생각하는 사람?이것은 정확히 컬렉션 크기의 초기 용량인 -25% 또는 +50%를 선호하는 것 같습니다.
자, 이제 결론을 내릴 시간입니다...
- 풋 타임에 대해서: 맵 엔트리의 예상 수보다 작은 초기 용량은 피하고 싶습니다.정확한 숫자를 미리 알고 있다면 그 숫자나 그보다 약간 높은 것이 가장 효과적일 것 같습니다.높은 부하 계수는 이전 해시 맵 크기 조정으로 인해 낮은 초기 용량을 상쇄할 수 있습니다.초기 용량이 더 큰 경우에는 그다지 중요하지 않은 것 같습니다.
- 취득 시간에 대해서:여기서는 결과가 약간 혼란스럽습니다.결론 내릴 게 별로 없어요.해시 코드 오버랩, 초기 용량 및 로드 팩터 간의 미묘한 비율에 크게 의존하고 있는 것 같습니다.일부 나쁜 설정은 정상적으로 동작하고 좋은 설정은 매우 높은 성능을 발휘합니다.
- 자바 성능에 관한 추측에 관해선 헛소리만 늘어놓는 것 같아요. 설정을 한, 이 설정을 이 않는 한,
HashMap을 사용하다여기서 한 가지 중요한 점은 기본 초기 크기인 16은 가장 작은 맵을 제외한 모든 맵에 대해 약간 멍청하다는 것입니다. 따라서 초기 크기를 설정하는 컨스트럭터를 사용하십시오. 어떤 크기의 순서가 될 지 알고 있다면. - 여기서 나노초 단위로 측정하고 있습니다.10개의 퍼트당 최고 평균 시간은 1179ns였고, 기계에서는 최저 5105ns였습니다.10 get당 가장 좋은 평균 시간은 547 ns, 가장 나쁜 평균 시간은 3484 ns였습니다.그게 6배 차이일 수도 있지만, 1밀리초 미만입니다.원래 포스터가 생각했던 것보다 훨씬 더 큰 컬렉션에 대한 것입니다.
음, 바로 그겁니다.내 코드에 내가 여기에 올린 모든 것을 무효로 하는 끔찍한 실수가 없었으면 좋겠어.이것은 즐거웠습니다.결국 작은 최적화와 큰 차이를 기대하기보다는 Java에 의존하여 작업을 수행하는 것이 낫다는 것을 알게 되었습니다.그렇다고 해서 회피해서는 안 되는 것도 있지만, 루프에 대해 긴 스트링을 구축하고 잘못된 데이터 구조를 사용하며 O(n^3) 알고리즘을 만드는 것이 대부분입니다.
이건 꽤 훌륭한 실타래야. 하지만 네가 놓치고 있는 중요한 게 하나 있어.당신이 말했다:
이상하게도 용량, 용량+1, 용량+2, 용량-1, 용량-10 모두 정확히 동일한 결과를 산출합니다.적어도 capacity-1과 capacity-10은 결과가 나빠질 것으로 예상됩니다.
소스코드는 초기 용량을 내부적으로 2의 곱 다음으로 높입니다.즉, 예를 들어 513, 600, 700, 800, 900, 1000 및 1024의 초기 용량이 모두 동일한 초기 용량(1024)을 사용합니다.그렇다고 해서 @G_H에 의한 테스트가 무효가 되는 것은 아닙니다.그러나 결과를 분석하기 전에 이것이 이루어지고 있음을 인식해야 합니다.그리고 그것이 몇몇 테스트의 이상한 행동을 설명해준다.
/**
* 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();
}
서 HashMapJava 문서:
일반적으로 기본 부하 계수(.75)는 시간과 공간 비용 간의 균형을 잘 유지합니다.값이 클수록 공간 오버헤드는 감소하지만 검색 비용은 증가합니다(get 및 put을 포함한 HashMap 클래스의 대부분의 작업에 반영됨).초기 용량을 설정할 때 맵 내의 예상 엔트리 수와 부하 계수를 고려하여 재해시 작업 횟수를 최소화해야 합니다.초기 용량이 최대 엔트리 수를 로드 팩터로 나눈 값보다 클 경우 재해시 작업은 발생하지 않습니다.
따라서 100개의 엔트리를 예상하는 경우에는 0.75의 하중률과 100/0.75의 초기 용량이 가장 적합합니다.그것은 134로 귀결된다.
저는 왜 부하율이 높을수록 조회 비용이 더 큰지 잘 모르겠습니다.HashMap이 더 많은 "crowded"라고 해서 동일한 버킷에 더 많은 개체가 배치되는 것은 아닙니다.내가 틀리지 않았다면 그건 그들의 해시코드에 달려있겠지.따라서 적절한 해시 코드가 퍼진다고 가정할 때 대부분의 경우 로드 팩터에 관계없이 O(1)가 되어야 하지 않을까요?
편집: 글을 올리기 전에 더 읽어봐야 합니다...물론 해시 코드는 일부 내부 인덱스에 직접 매핑할 수 없습니다.현재 용량에 맞는 값으로 줄여야 합니다.즉, 초기 용량이 클수록 해시 충돌 수가 줄어들 것으로 예상됩니다.로드 팩터가 1인 객체 세트의 크기(또는 +1)를 정확하게 선택하면 맵의 크기가 조정되지 않습니다.그러나 검색 및 삽입 성능이 저하됩니다.크기 조정은 여전히 비교적 빠르고 한 번만 수행되며, 지도와 관련된 거의 모든 작업에 대해 조회가 수행됩니다.따라서 빠른 검색에 최적화해야 합니다.JavaDoc의 설명에 따라 필요한 용량을 최적의 부하율(0.75)로 나누어 초기 용량으로 사용하는 것으로 크기를 조정할 필요가 없는 것과 결합할 수 있습니다.반올림하지 않도록 1을 더합니다.
★★★★★★★★★★★★★★★★★로 해 주세요.101사실 꼭 필요한지는 모르겠지만, 굳이 알아낼 필요는 없을 것 같아요.
...을 추가...더하기만 하면 됩니다.1.
편집: 내 답변에 대한 몇 가지 정당성.
저는 의 째, 각, 각, 버, 버, 버, 버, 을 가정합니다.HashMap 이상 것이다100; 이 경우 부하계수를 그대로 두어야 합니다.마찬가지로 퍼포먼스에 관심이 있는 경우에는 부하 계수를 그대로 둡니다.메모리 문제가 있는 경우는, 정적 사이즈를 설정해 절약할 수 있습니다.많은 정보를 메모리에 주입하거나 많은 맵을 저장하거나 힙스페이스스트레스 사이즈의 맵을 작성하는 경우, 이것은 아마 실행할 가치가 있을 것입니다.
둘째, 값을 선택합니다.101가독성이 뛰어나기 때문에...나중에 당신의 코드를 보고 당신이 초기 용량을100로딩할 때100자바독을 읽고 정확하게 도달했을 때 크기가 조정되지 않도록 해야 합니다.100물론 거기서 답을 찾을 수 없기 때문에 출처를 봐야 합니다.이건 그럴 가치가 없어...그냥 두세요.101모두가 행복해하고 아무도 소스코드를 찾지 않고 있습니다.java.util.HashMap호라.
셋째로, 이 설정은HashMap부하계수에서 예상한 용량만큼 정확하게1 "lookup and insertion performance"는 굵은 글씨로 표시되더라도 사실이 아닙니다.
...가 있는 경우n버킷을 임의로 할당하면n로의 항목.nbuckets, yeah, 결국엔 같은 버킷에 아이템이 있을 거야, 물론...하지만 그게 세상의 끝은 아니야실제로는, 단지 몇 가지 더 동등한 비교일 뿐입니다.사실, 거기엔 특별한게 있어.다른 대안이 할당하는 것을 고려할 때 거의 차이가 없습니다.n로의 항목.n/0.75양동이
내 말을 믿을 필요 없어...
빠른 테스트 코드:
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.
참조: ↑ — 이 →| ←에 대한 설정은 서로 크게 다릅니다.
나의 원래 답변(첫 번째 수평선 위 비트)에 대해서는 대부분의 경우 이런 유형의 미세 최적화는 좋지 않기 때문에 일부러 입버릇처럼 말했다.
구현 측면에서 Google Guava는 편리한 공장 방식을 가지고 있습니다.
Maps.newHashMapWithExpectedSize(expectedSize)
즉, 다음 공식을 사용하여 용량을 계산합니다.
capacity = expectedSize / 0.75F + 1.0F
언급URL : https://stackoverflow.com/questions/7115445/what-is-the-optimal-capacity-and-load-factor-for-a-fixed-size-hashmap
'programing' 카테고리의 다른 글
| 상위 구성 요소에서 하위 구성 요소로 데이터 개체 전달 (0) | 2022.10.07 |
|---|---|
| 주피터 노트북의 인라인 플롯을 크게 하는 방법 (0) | 2022.10.07 |
| Java 8: Java.util.function의 TriFunction(및 kin)은 어디에 있습니까?아니면 대체방법이 뭐죠? (0) | 2022.10.07 |
| Scheduled Executor Service를 사용하여 매일 특정 시간에 특정 작업을 실행하는 방법 (0) | 2022.10.07 |
| MySQL에 임의 날짜 삽입/업데이트 (0) | 2022.10.06 |