[java] 고정 크기 HashMap에 대한 최적의 용량 및로드 계수는 무엇입니까?

좋습니다.이 문제를 해결하기 위해 몇 가지 시나리오를 실행하고 결과를 시각화 할 수있는 테스트 앱을 만들었습니다. 테스트가 수행되는 방법은 다음과 같습니다.

• 다양한 컬렉션 크기가 시도되었습니다 : 백, 천, 십만 항목.
• 사용되는 키는 ID로 고유하게 식별되는 클래스의 인스턴스입니다. 각 테스트는 정수를 ID로 증분하는 고유 키를 사용합니다. 이 equals방법은 ID 만 사용하므로 키 매핑이 다른 ID를 덮어 쓰지 않습니다.
• 키는 일부 사전 설정 번호에 대한 ID의 나머지 모듈로 구성된 해시 코드를 얻습니다. 이 숫자를 해시 제한이라고 합니다. 이를 통해 예상되는 해시 충돌 수를 제어 할 수있었습니다. 예를 들어 컬렉션 크기가 100이면 0에서 99 사이의 ID를 가진 키가 있습니다. 해시 제한이 100이면 모든 키는 고유 한 해시 코드를 갖게됩니다. 해시 제한이 50 인 경우 키 0은 키 50과 동일한 해시 코드를 갖고 1은 51과 동일한 해시 코드를 갖습니다. 즉, 키당 예상되는 해시 충돌 수는 컬렉션 크기를 해시로 나눈 값입니다. 한도.
• 컬렉션 크기와 해시 제한의 각 조합에 대해 다른 설정으로 초기화 된 해시 맵을 사용하여 테스트를 실행했습니다. 이러한 설정은 부하 계수이며 수집 설정의 계수로 표현되는 초기 용량입니다. 예를 들어, 컬렉션 크기가 100이고 초기 용량 계수가 1.25 인 테스트는 초기 용량이 125 인 해시 맵을 초기화합니다.
• 각 키의 값은 단순히 새로운 Object.
• 각 테스트 결과는 Result 클래스의 인스턴스에 캡슐화됩니다. 모든 테스트가 끝나면 결과는 최악의 전체 성능에서 최고로 정렬됩니다.
• 풋 및 겟의 평균 시간은 풋 / 겟 10 회당 계산됩니다.
• 모든 테스트 조합은 JIT 컴파일 영향을 제거하기 위해 한 번 실행됩니다. 그 후 실제 결과에 대한 테스트가 실행됩니다.

수업은 다음과 같습니다.

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 파일로 출력하는 시각화 도우미를 호출합니다. 이에 대한 클래스는 다음과 같습니다. 실행하려면 위 코드에서 해당 줄의 주석 처리를 제거하십시오. 경고 : Visualizer 클래스는 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. 이는 각 해시 코드가 두 번 발생하고 다른 모든 키가 해시 맵에서 충돌해야 함을 의미합니다.

글쎄요, 그게 좋은 시작은 아닙니다. 컬렉션 크기보다 25 % 더 큰 초기 용량에 대한 큰 핫스팟이 있고로드 계수 1이 있음을 알 수 있습니다. 왼쪽 하단 모서리가 너무 잘 수행되지 않습니다.

---

컬렉션 크기 : 100. 해시 제한 : 90. 키 열 개 중 하나에 중복 된 해시 코드가 있습니다.

이것은 완전한 해시 함수가 없지만 여전히 10 %의 과부하가 걸리는 약간 더 현실적인 시나리오입니다. 핫스팟은 사라졌지 만 낮은 초기 용량과 낮은 부하 계수의 조합은 분명히 작동하지 않습니다.

---

컬렉션 크기 : 100. 해시 제한 : 100. 각 키는 고유 한 해시 코드입니다. 버킷이 충분하면 충돌이 예상되지 않습니다.

부하 계수가 1 인 초기 용량 100은 괜찮아 보입니다. 놀랍게도 초기 용량이 높고 부하율이 낮다고해서 반드시 좋은 것은 아닙니다.

---

컬렉션 크기 : 1000. 해시 제한 : 500. 여기서는 1000 개의 항목으로 더욱 심각 해지고 있습니다. 첫 번째 테스트와 마찬가지로 2 대 1의 해시 오버로드가 있습니다.

왼쪽 하단 모서리는 여전히 잘 작동하지 않습니다. 그러나 낮은 초기 계수 / 높은 부하 계수와 높은 초기 계수 / 낮은 하중 계수의 조합 사이에는 대칭이있는 것 같습니다.

---

컬렉션 크기 : 1000. 해시 제한 : 900. 이것은 10 개의 해시 코드 중 하나가 두 번 발생 함을 의미합니다. 충돌에 관한 합리적인 시나리오.

로드 팩터가 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 % 추가 공간이있는 초기 용량이 이깁니다.

---

좋아, 그게 풋내기 다. 이제 겟을 확인하겠습니다. 아래지도는 모두 최고 / 최악의 획득 시간에 상대적이며 풋 시간은 더 이상 고려되지 않습니다.

결과 얻기

---

컬렉션 크기 : 100. 해시 제한 : 50. 이는 각 해시 코드가 두 번 발생하고 다른 모든 키가 해시 맵에서 충돌 할 것으로 예상됨을 의미합니다.

어 … 뭐?

---

컬렉션 크기 : 100. 해시 제한 : 90. 키 열 개 중 하나에 중복 된 해시 코드가 있습니다.

워 넬리! 이것은 질문자의 질문과 관련이있을 가능성이 가장 높은 시나리오이며, 부하 계수가 1 인 초기 용량 100은 여기서 최악의 상황 중 하나입니다! 나는 이것을 위조하지 않았다고 맹세합니다.

---

컬렉션 크기 : 100. 해시 제한 : 100. 각 키는 고유 한 해시 코드입니다. 예상되는 충돌이 없습니다.

이것은 좀 더 평화로워 보입니다. 전반적으로 거의 동일한 결과입니다.

---

컬렉션 크기 : 1000. 해시 제한 : 500. 첫 번째 테스트와 마찬가지로 해시 오버로드가 2 대 1이지만 이제는 더 많은 항목이 있습니다.

모든 설정이 여기에서 괜찮은 결과를 낳을 것 같습니다.

---

컬렉션 크기 : 1000. 해시 제한 : 900. 이것은 10 개의 해시 코드 중 하나가 두 번 발생 함을 의미합니다. 충돌에 관한 합리적인 시나리오.

그리고이 설정의 풋과 마찬가지로 이상한 지점에서 이상 현상이 발생합니다.

---

컬렉션 크기 : 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 %의 초기 용량을 선호하는 것 같습니다.

---

좋습니다. 이제 결론을 내릴 시간입니다 …

• 넣기 시간과 관련하여 : 예상되는 맵 항목 수보다 적은 초기 용량을 피하는 것이 좋습니다. 정확한 숫자를 미리 알고 있다면 그 숫자 또는 약간 위의 숫자가 가장 잘 작동하는 것 같습니다. 높은 부하 요인은 초기 해시 맵 크기 조정으로 인해 낮은 초기 용량을 상쇄 할 수 있습니다. 더 높은 초기 용량의 경우 그다지 중요하지 않은 것 같습니다.
• GET 시간과 관련하여 : 여기서 결과는 약간 혼란 스럽습니다. 결론이별로 없습니다. 해시 코드 겹침, 초기 용량 및로드 팩터 사이의 미묘한 비율에 크게 의존하는 것 같습니다.
• Java 성능에 대한 가정에 관해서는 분명히 쓰레기로 가득 차 있습니다. 사실은의 구현에 맞게 설정을 완벽하게 조정하지 않는 한 HashMap결과가 모든 곳에 나타날 것입니다. 여기서 빼야 할 것이 있다면, 기본 초기 크기 인 16은 가장 작은지도를 제외하고는 조금 멍청하다는 것입니다. 따라서 어떤 크기의 순서에 대한 아이디어가 있다면 초기 크기를 설정하는 생성자를 사용하십시오. 곧 될거야.
• 여기서는 나노초 단위로 측정하고 있습니다. 10 개 풋당 최고 평균 시간은 1179ns이고 내 컴퓨터에서 최악의 5105ns였습니다. 10 회당 최고 평균 시간은 547ns이고 최악의 경우 3484ns입니다. 그것은 요소 6 차이 일 수 있지만 우리는 1 밀리 초 미만으로 이야기하고 있습니다. 원래 포스터가 생각했던 것보다 훨씬 더 큰 컬렉션.

글쎄, 그게 다야. 내 코드에 내가 여기에 게시 한 모든 것을 무효화하는 끔찍한 감독이 없기를 바랍니다. 이것은 재미 있었고 결국에는 작은 최적화와 많은 차이를 기대하는 것보다 Java에 의존하여 작업을 수행 할 수 있다는 것을 알게되었습니다. 그것은 어떤 것들을 피해서는 안된다는 말은 아니지만, 우리는 주로 for 루프에서 긴 문자열을 구성하고, 잘못된 데이터 구조를 사용하고, O (n ^ 3) 알고리즘을 만드는 것에 대해 이야기하고 있습니다.