Jaka jest optymalna pojemność i współczynnik obciążenia dla mapy HashMap o stałym rozmiarze?

Próbuję znaleźć optymalną pojemność i współczynnik obciążenia dla konkretnego przypadku. Myślę, że zrozumiałem sedno, ale nadal byłbym wdzięczny za potwierdzenie od kogoś bardziej kompetentnego niż ja. :)

Jeśli wiem, że moja HashMap zapełni się, aby pomieścić, powiedzmy, 100 obiektów i spędza większość czasu mając 100 obiektów, to domyślam się, że optymalne wartości to początkowa pojemność 100 i współczynnik obciążenia 1? Czy potrzebuję pojemności 101, czy są jakieś inne problemy?

EDYCJA: OK, odłożyłem kilka godzin i zrobiłem kilka testów. Oto wyniki:

• Co ciekawe, pojemność, pojemność + 1, pojemność + 2, pojemność-1, a nawet pojemność-10 dają dokładnie takie same wyniki. Spodziewałbym się, że przynajmniej pojemność-1 i pojemność-10 dadzą gorsze wyniki.
• Korzystanie z pojemności początkowej (w przeciwieństwie do domyślnej wartości 16) daje zauważalną poprawę metody put () - do 30% szybciej.
• Użycie współczynnika obciążenia równego 1 zapewnia taką samą wydajność w przypadku małej liczby obiektów i lepszą wydajność w przypadku większej liczby obiektów (> 100000). Jednak nie poprawia się to proporcjonalnie do liczby obiektów; Podejrzewam, że jest dodatkowy czynnik wpływający na wyniki.
• Wydajność get () jest nieco inna dla różnej liczby obiektów / pojemności, ale chociaż może się nieznacznie różnić w zależności od przypadku, generalnie nie ma na nią wpływu pojemność początkowa ani współczynnik obciążenia.

EDIT2: Dodanie również niektórych wykresów z mojej strony. Oto ten ilustrujący różnicę między współczynnikiem obciążenia 0,75 a 1, w przypadkach, gdy inicjuję HashMap i wypełniam go do pełnej pojemności. Skala y to czas w ms (mniejszy jest lepszy), a skala x to rozmiar (liczba obiektów). Ponieważ rozmiar zmienia się liniowo, wymagany czas również rośnie liniowo.

Zobaczmy więc, co mam. Poniższe dwa wykresy przedstawiają różnice współczynników obciążenia. Pierwszy wykres pokazuje, co się dzieje, gdy HashMap jest wypełniony do pełna; współczynnik obciążenia 0,75 działa gorzej z powodu zmiany rozmiaru. Jednak konsekwentnie nie jest gorzej i jest wiele rodzajów wybojów i podskoków - myślę, że GC ma w tym dużą rolę. Współczynnik obciążenia 1,25 działa tak samo jak 1, więc nie jest uwzględniony w wykresie.

Ten wykres dowodzi, że 0,75 było gorsze z powodu zmiany rozmiaru; jeśli wypełnimy HashMap do połowy pojemności, 0.75 nie jest gorsze, tylko ... inne (i powinno zużywać mniej pamięci i mieć niezauważalnie lepszą wydajność iteracji).

Jeszcze jedna rzecz, którą chcę pokazać. To uzyskuje wydajność dla wszystkich trzech współczynników obciążenia i różnych rozmiarów HashMap. Konsekwentnie stała z niewielkimi zmianami, z wyjątkiem jednego skoku dla współczynnika obciążenia 1. Naprawdę chciałbym wiedzieć, co to jest (prawdopodobnie GC, ale kto wie).

A oto kod dla zainteresowanych:

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);
  }

}

W porządku, żeby to uspokoić, stworzyłem aplikację testową, aby uruchomić kilka scenariuszy i uzyskać wizualizacje wyników. Oto jak przeprowadzane są testy:

• Wypróbowano kilka różnych rozmiarów kolekcji: sto, tysiąc i sto tysięcy wpisów.
• Użyte klucze to instancje klasy, które są jednoznacznie identyfikowane przez identyfikator. Każdy test używa unikalnych kluczy, z rosnącymi liczbami całkowitymi jako identyfikatorami. equalsMetoda wykorzystuje tylko identyfikator, więc żaden klawisz mapowanie zastępuje inną.
• Klucze otrzymują kod skrótu, który składa się z pozostałej części identyfikatora modułu w stosunku do pewnego wstępnie ustawionego numeru. Nazwiemy ten numer limitem skrótu . Pozwoliło mi to kontrolować liczbę oczekiwanych kolizji hashów. Na przykład, jeśli rozmiar naszej kolekcji to 100, będziemy mieć klucze z identyfikatorami w zakresie od 0 do 99. Jeśli limit skrótu wynosi 100, każdy klucz będzie miał unikalny kod skrótu. Jeśli limit skrótu wynosi 50, klucz 0 będzie miał ten sam kod skrótu co klucz 50, 1 będzie miał ten sam kod skrótu co 51 itd. Innymi słowy, oczekiwana liczba kolizji skrótu na klucz to rozmiar kolekcji podzielony przez skrót limit.
• Dla każdej kombinacji rozmiaru kolekcji i limitu mieszania uruchomiłem test przy użyciu map skrótów zainicjowanych z różnymi ustawieniami. Te ustawienia to współczynnik obciążenia i początkowa pojemność wyrażona jako współczynnik ustawienia zbierania. Na przykład test z rozmiarem kolekcji 100 i początkowym współczynnikiem pojemności 1,25 zainicjuje mapę skrótów o początkowej pojemności 125.
• Wartość każdego klucza jest po prostu nowa Object.
• Każdy wynik testu jest hermetyzowany w wystąpieniu klasy Result. Na końcu wszystkich testów wyniki są sortowane od najgorszych do najlepszych.
• Średni czas na puts i get jest obliczany na 10 puts / gets.
• Wszystkie kombinacje testowe są uruchamiane raz, aby wyeliminować wpływ kompilacji JIT. Następnie testy są uruchamiane w celu uzyskania rzeczywistych wyników.

Oto klasa:

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.");

        }

    }

}

Uruchomienie tego może chwilę potrwać. Wyniki są drukowane standardowo. Możesz zauważyć, że zakomentowałem linię. Ta linia wywołuje wizualizator, który wyświetla wizualne reprezentacje wyników do plików png. Klasa do tego jest podana poniżej. Jeśli chcesz go uruchomić, odkomentuj odpowiednią linię w powyższym kodzie. Uwaga: klasa visualizer zakłada, że ​​pracujesz w systemie Windows i utworzy foldery i pliki w C: \ temp. Podczas biegania na innej platformie dostosuj to.

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);

    }

}

Wizualizowane dane wyjściowe są następujące:

• Testy są podzielone najpierw według rozmiaru kolekcji, a następnie według limitu skrótu.
• Dla każdego testu istnieje obraz wyjściowy przedstawiający średni czas wprowadzenia (na 10 wejść) i średni czas uzyskania (na 10 wejść). Obrazy są dwuwymiarowymi „mapami ciepła”, które pokazują kolor według kombinacji początkowej pojemności i współczynnika obciążenia.
• Kolory na obrazach są oparte na średnim czasie w znormalizowanej skali od najlepszego do najgorszego wyniku, od nasyconej zieleni do nasyconej czerwieni. Innymi słowy, najlepszy czas będzie w pełni zielony, a najgorszy - w pełni czerwony. Dwa różne pomiary czasu nigdy nie powinny mieć tego samego koloru.
• Mapy kolorów są obliczane osobno dla pozycji put i get, ale obejmują wszystkie testy dla odpowiednich kategorii.
• Wizualizacje pokazują początkową nośność na ich osi x, a współczynnik obciążenia na osi y.

Bez zbędnych ceregieli spójrzmy na wyniki. Zacznę od wyników dla puttów.

Umieść wyniki

Rozmiar kolekcji: 100. Limit skrótu: 50. Oznacza to, że każdy kod skrótu powinien wystąpić dwukrotnie, a każdy inny klucz koliduje na mapie skrótów.

Cóż, to nie zaczyna się zbyt dobrze. Widzimy, że istnieje duży hotspot dla początkowej pojemności 25% powyżej rozmiaru kolekcji, przy współczynniku obciążenia 1. Lewy dolny róg nie działa zbyt dobrze.

Rozmiar kolekcji: 100. Limit skrótu: 90. Jeden na dziesięć kluczy ma zduplikowany kod skrótu.

Jest to nieco bardziej realistyczny scenariusz, który nie ma idealnej funkcji skrótu, ale nadal jest przeciążony o 10%. Hotspot zniknął, ale połączenie małej pojemności początkowej z niskim współczynnikiem obciążenia oczywiście nie działa.

Wielkość kolekcji: 100. Limit mieszania: 100. Każdy klucz jako jego własny, unikalny kod skrótu. Nie oczekuje się kolizji, jeśli jest wystarczająca liczba łyżek.

Początkowa pojemność 100 przy współczynniku obciążenia 1 wydaje się w porządku. Zaskakujące jest, że wyższa pojemność początkowa przy niższym współczynniku obciążenia niekoniecznie jest dobra.

Wielkość kolekcji: 1000. Limit haszowania: 500. Tutaj robi się poważniej, z 1000 wpisów. Podobnie jak w pierwszym teście, występuje przeciążenie hashujące od 2 do 1.

Lewy dolny róg nadal nie radzi sobie dobrze. Wydaje się jednak, że istnieje symetria między kombinacją niższej liczby początkowej / wyższego współczynnika obciążenia i wyższego współczynnika początkowego / niskiego obciążenia.

Wielkość kolekcji: 1000. Limit mieszania: 900. Oznacza to, że jeden na dziesięć kodów skrótów wystąpi dwukrotnie. Rozsądny scenariusz dotyczący kolizji.

Jest coś bardzo zabawnego z nieprawdopodobną kombinacją początkowej pojemności, która jest zbyt niska przy współczynniku obciążenia powyżej 1, co jest raczej sprzeczne z intuicją. W przeciwnym razie nadal dość symetrycznie.

Wielkość kolekcji: 1000. Limit hash: 990. Trochę kolizji, ale tylko kilka. Całkiem realistyczne pod tym względem.

Mamy tutaj niezłą symetrię. Lewy dolny róg jest nadal nieoptymalny, ale kombinacje 1000 init pojemność / 1,0 współczynnik obciążenia w porównaniu z 1250 init pojemność / 0,75 współczynnik obciążenia są na tym samym poziomie.

Wielkość kolekcji: 1000. Limit mieszania: 1000. Brak zduplikowanych kodów skrótu, ale teraz z wielkością próbki 1000.

Niewiele do powiedzenia. Wydaje się, że połączenie wyższej nośności początkowej ze współczynnikiem obciążenia 0,75 nieznacznie przewyższa połączenie 1000 nośności początkowej ze współczynnikiem obciążenia 1.

Wielkość kolekcji: 100_000. Limit skrótu: 10_000. W porządku, teraz robi się poważnie, z próbką o wielkości stu tysięcy i 100 duplikatów kodu skrótu na klucz.

Yikes! Myślę, że znaleźliśmy nasze niższe spektrum. Zdolność inicjowania o wielkości kolekcji i współczynniku obciążenia równym 1 radzi sobie tutaj naprawdę dobrze, ale poza tym jest w całym sklepie.

Wielkość kolekcji: 100_000. Limit skrótu: 90_000. Trochę bardziej realistyczne niż w poprzednim teście, tutaj mamy 10% przeciążenie w kodach hashujących.

Lewy dolny róg jest nadal niepożądany. Wyższe początkowe pojemności działają najlepiej.

Wielkość kolekcji: 100_000. Limit skrótu: 99_000. To dobry scenariusz. Duża kolekcja z 1% przeciążeniem kodu skrótu.

Użycie dokładnego rozmiaru kolekcji jako pojemności początkowej przy współczynniku obciążenia 1 wygrywa tutaj! Nieco większe możliwości inicjalizacji działają jednak całkiem dobrze.

Wielkość kolekcji: 100_000. Limit skrótu: 100_000. Duży. Największa kolekcja z doskonałą funkcją skrótu.

Oto kilka zaskakujących rzeczy. Wydajność początkowa z 50% dodatkowym pomieszczeniem przy współczynniku obciążenia 1 wygrywa.

W porządku, to wszystko dla puttów. Teraz sprawdzimy, czy dostaje. Pamiętaj, że wszystkie poniższe mapy odnoszą się do najlepszych / najgorszych czasów zdobycia, czasy wstawiania nie są już brane pod uwagę.

Uzyskać rezultaty

Rozmiar kolekcji: 100. Limit skrótu: 50. Oznacza to, że każdy kod skrótu powinien wystąpić dwa razy, a każdy inny klucz miał kolidować na mapie skrótów.

Ech ... Co?

Rozmiar kolekcji: 100. Limit skrótu: 90. Jeden na dziesięć kluczy ma zduplikowany kod skrótu.

Whoa Nelly! Jest to najbardziej prawdopodobny scenariusz, który koreluje z pytaniem pytającego i najwyraźniej początkowa pojemność 100 przy współczynniku obciążenia 1 jest tutaj jedną z najgorszych rzeczy! Przysięgam, że tego nie udawałem.

Wielkość kolekcji: 100. Limit mieszania: 100. Każdy klucz jako jego własny, unikalny kod skrótu. Nie oczekuje się kolizji.

To wygląda trochę spokojniej. W większości te same wyniki we wszystkich dziedzinach.

Wielkość kolekcji: 1000. Limit haszowania: 500. Podobnie jak w pierwszym teście, przeciążenie hashem wynosi od 2 do 1, ale teraz jest dużo więcej wpisów.

Wygląda na to, że każde ustawienie przyniesie tutaj przyzwoity wynik.

Wielkość kolekcji: 1000. Limit mieszania: 900. Oznacza to, że jeden na dziesięć kodów skrótów wystąpi dwukrotnie. Rozsądny scenariusz dotyczący kolizji.

I tak jak w przypadku putsów dla tej konfiguracji, otrzymujemy anomalię w dziwnym miejscu.

Wielkość kolekcji: 1000. Limit hash: 990. Trochę kolizji, ale tylko kilka. Całkiem realistyczne pod tym względem.

Przyzwoita wydajność wszędzie, z wyjątkiem połączenia dużej pojemności początkowej z niskim współczynnikiem obciążenia. Spodziewałbym się tego w przypadku putsów, ponieważ można się spodziewać dwóch zmian rozmiarów mapy skrótów. Ale dlaczego na początku?

Wielkość kolekcji: 1000. Limit mieszania: 1000. Brak zduplikowanych kodów skrótu, ale teraz z wielkością próbki 1000.

Całkowicie nie spektakularna wizualizacja. To wydaje się działać bez względu na wszystko.

Wielkość kolekcji: 100_000. Limit skrótu: 10_000. Przechodząc ponownie do 100K, z wieloma nakładającymi się kodami skrótu.

Nie wygląda ładnie, chociaż złe miejsca są bardzo zlokalizowane. Wydaje się, że tutaj wydajność w dużej mierze zależy od pewnej synergii między ustawieniami.

Wielkość kolekcji: 100_000. Limit skrótu: 90_000. Trochę bardziej realistyczne niż w poprzednim teście, tutaj mamy 10% przeciążenie w kodach hashujących.

Duża różnorodność, chociaż jeśli zmrużysz oczy, zobaczysz strzałkę skierowaną w prawy górny róg.

Wielkość kolekcji: 100_000. Limit skrótu: 99_000. To dobry scenariusz. Duża kolekcja z 1% przeciążeniem kodu skrótu.

Bardzo chaotyczny. Trudno tu znaleźć wiele struktur.

Wielkość kolekcji: 100_000. Limit skrótu: 100_000. Duży. Największa kolekcja z doskonałą funkcją skrótu.

Czy ktoś jeszcze myśli, że to zaczyna wyglądać jak grafika Atari? Wydaje się, że faworyzuje to początkową pojemność dokładnie taką, jak wielkość zbioru, -25% lub + 50%.

W porządku, teraz czas na wnioski ...

• Jeśli chodzi o czasy wstawiania: będziesz chciał uniknąć początkowej pojemności, która jest mniejsza niż spodziewana liczba wpisów na mapie. Jeśli wcześniej znana jest dokładna liczba, wydaje się, że ta liczba lub coś nieco powyżej wydaje się działać najlepiej. Wysokie współczynniki obciążenia mogą zrównoważyć mniejsze początkowe pojemności z powodu wcześniejszych zmian rozmiarów mapy skrótów. W przypadku wyższych pojemności początkowych nie wydają się one mieć większego znaczenia.
• Jeśli chodzi o czasy uzyskiwania: wyniki są tutaj nieco chaotyczne. Nie ma wiele do podsumowania. Wydaje się, że w dużym stopniu opiera się na subtelnych stosunkach między nakładaniem się kodu skrótu, początkową pojemnością i współczynnikiem obciążenia, przy czym niektóre rzekomo złe konfiguracje działają dobrze, a dobre działają okropnie.
• Najwyraźniej jestem pełen bzdur, jeśli chodzi o założenia dotyczące wydajności Javy. Prawda jest taka, że ​​jeśli nie dostroisz perfekcyjnie swoich ustawień do implementacji HashMap, wyniki będą wszędzie. Jeśli jest jeszcze jedna rzecz, którą można z tego wyciągnąć, jest to, że domyślny rozmiar początkowy 16 jest nieco głupi dla wszystkiego innego niż najmniejsze mapy, więc użyj konstruktora, który ustawia rozmiar początkowy, jeśli masz jakiekolwiek pojęcie o kolejności rozmiaru To będzie.
• Tutaj mierzymy w nanosekundach. Najlepszy średni czas na 10 wejść to 1179 ns, a najgorszy 5105 ns na moim komputerze. Najlepszy średni czas na 10 otrzymów wyniósł 547 ns, a najgorszy 3484 ns. Może to być różnica czynnikowa 6, ale mówimy o mniej niż milisekundach. Na kolekcjach, które są znacznie większe niż to, co miał na myśli oryginalny plakat.

Cóż, to wszystko. Mam nadzieję, że mój kod nie zawiera jakiegoś strasznego przeoczenia, które unieważnia wszystko, co tutaj zamieściłem. Było to zabawne i nauczyłem się, że w końcu równie dobrze można polegać na Javie, aby wykonać swoją pracę, niż oczekiwać dużej różnicy po drobnych optymalizacjach. Nie oznacza to, że niektórych rzeczy nie należy unikać, ale wtedy mówimy głównie o konstruowaniu długich ciągów znaków w pętlach for, używaniu niewłaściwych struktur danych i tworzeniu algorytmu O (n ^ 3).

To całkiem niezły wątek, z wyjątkiem jednej kluczowej rzeczy, której brakuje. Powiedziałeś:

Co ciekawe, pojemność, pojemność + 1, pojemność + 2, pojemność-1, a nawet pojemność-10 dają dokładnie takie same wyniki. Spodziewałbym się, że przynajmniej pojemność-1 i pojemność-10 dadzą gorsze wyniki.

Kod źródłowy przeskakuje wewnętrznie pojemność początkową o następną najwyższą potęgę z dwóch. Oznacza to, że na przykład początkowe pojemności 513, 600, 700, 800, 900, 1000 i 1024 będą używać tej samej początkowej pojemności (1024). Nie unieważnia to jednak testów wykonanych przez @G_H, należy jednak zdawać sobie sprawę, że robi się to przed analizą jego wyników. I wyjaśnia dziwne zachowanie niektórych testów.

Oto konstruktor właściwy dla źródła 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();
}

Po prostu idź z 101. Właściwie nie jestem pewien, czy jest to potrzebne, ale nie może być warte wysiłku, aby kiedykolwiek się dowiedzieć.

... po prostu dodaj 1.

EDYCJA: Pewne uzasadnienie mojej odpowiedzi.

Po pierwsze, zakładam, że HashMapnie wyrośniecie poza 100; jeśli tak, należy pozostawić współczynnik obciążenia bez zmian. Podobnie, jeśli zależy Ci na wydajności, pozostaw współczynnik obciążenia bez zmian . Jeśli martwisz się pamięcią, możesz trochę zaoszczędzić, ustawiając rozmiar statyczny. To może być może być warto robić jeśli wkuwania wiele rzeczy w pamięci; tj. przechowują wiele map lub tworzą mapy o wymiarach obciążających przestrzeń sterty.

Po drugie, wybieram wartość, 101ponieważ zapewnia lepszą czytelność ... jeśli później patrzę na twój kod i widzę, że ustawiłeś początkową pojemność na 100i ładujesz go 100elementami, będę musiał przeczytaj Javadoc, aby upewnić się, że nie zmieni rozmiaru, gdy osiągnie dokładnie 100. Oczywiście nie znajdę tam odpowiedzi, więc będę musiał poszukać źródła. To nie jest tego warte ... po prostu zostaw to, 101a wszyscy są szczęśliwi i nikt nie przegląda kodu źródłowego java.util.HashMap. Hura.

Po trzecie, twierdzenie, że ustawienie HashMapdokładnej pojemności zgodnej z oczekiwaniami ze współczynnikiem obciążenia 1 „ zabije wydajność wyszukiwania i wstawiania ” jest po prostu nieprawdziwe, nawet jeśli zostało zaznaczone pogrubioną czcionką.

... jeśli masz nwiadra i losowo przypisujesz nprzedmioty do nkoszy, tak, skończysz z przedmiotami w tym samym koszyku, jasne ... ale to nie koniec świata ... w praktyce, to tylko kilka więcej równa się porównaniom. W rzeczywistości jest esp. mała różnica, jeśli weźmiesz pod uwagę, że alternatywą jest przypisywanie nelementów do n/0.75koszy.

Nie musisz wierzyć mi na słowo ...

Kod szybkiego testu:

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;
}

Wyniki testów:

=======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: ↑ - jest o tym → || ← duża różnica między różnymi ustawieniami .

W odniesieniu do mojego pierwotnego odpowiedzi (bitu powyżej pierwszej linii poziomej), został celowo GLib ponieważ w większości przypadków , tego rodzaju mikro-optymalizacja nie jest dobre .

Pod względem implementacji Google Guava ma wygodną metodę fabryczną

Maps.newHashMapWithExpectedSize(expectedSize)

Który oblicza pojemność za pomocą wzoru

capacity = expectedSize / 0.75F + 1.0F

Z HashMapJavaDoc:

Zgodnie z ogólną zasadą domyślny współczynnik obciążenia (0,75) zapewnia dobry kompromis między kosztami czasu i miejsca. Wyższe wartości zmniejszają narzut miejsca, ale zwiększają koszt wyszukiwania (odzwierciedlony w większości operacji klasy HashMap, w tym get and put). Oczekiwaną liczbę wpisów na mapie i jej współczynnik obciążenia należy wziąć pod uwagę przy ustalaniu jej początkowej pojemności, aby zminimalizować liczbę operacji ponownego mieszania. Jeśli początkowa pojemność jest większa niż maksymalna liczba wpisów podzielona przez współczynnik obciążenia, żadne operacje ponownego mieszania nie będą nigdy wykonywane.

Więc jeśli spodziewasz się 100 wpisów, być może najlepszy byłby współczynnik obciążenia 0,75 i początkowa nośność sufitu (100 / 0,75). To sprowadza się do 134.

Muszę przyznać, że nie jestem pewien, dlaczego koszt wyszukiwania byłby większy przy wyższym współczynniku obciążenia. To, że HashMap jest bardziej „zatłoczona”, nie oznacza, że ​​więcej obiektów zostanie umieszczonych w tym samym wiadrze, prawda? To zależy tylko od ich kodu skrótu, jeśli się nie mylę. Zakładając więc przyzwoity rozkład kodu skrótu, czy w większości przypadków nie powinien nadal wynosić O (1), niezależnie od współczynnika obciążenia?

EDYCJA: Powinienem przeczytać więcej przed wysłaniem ... Oczywiście kod skrótu nie może bezpośrednio mapować do jakiegoś wewnętrznego indeksu. Należy go zredukować do wartości, która odpowiada aktualnej wydajności. Oznacza to, że im większa początkowa pojemność, tym mniejsza może być liczba kolizji z haszowaniem. Wybranie początkowej pojemności dokładnie odpowiadającej rozmiarowi (lub +1) obiektu ustawionemu ze współczynnikiem obciążenia 1 rzeczywiście zapewni, że rozmiar mapy nigdy nie zostanie zmieniony. Jednak spowoduje to utratę wydajności wyszukiwania i wstawiania. Zmiana rozmiaru jest nadal stosunkowo szybka i może nastąpić tylko raz, podczas gdy wyszukiwania są wykonywane na prawie każdej istotnej pracy z mapą. W rezultacie optymalizacja pod kątem szybkiego wyszukiwania jest tym, czego naprawdę potrzebujesz. Możesz to połączyć z brakiem konieczności zmiany rozmiaru, postępując zgodnie z zaleceniami JavaDoc: weź wymaganą pojemność, podziel przez optymalny współczynnik obciążenia (np. 0,75) i użyj tego jako pojemności początkowej, z tym współczynnikiem obciążenia. Dodaj 1, aby mieć pewność, że zaokrąglanie Cię nie dostanie.