Was ist die optimale Kapazität und der optimale Auslastungsfaktor für eine HashMap mit fester Größe?

Ich versuche, die optimale Kapazität und den optimalen Auslastungsfaktor für einen bestimmten Fall herauszufinden. Ich glaube, ich habe das Wesentliche verstanden, aber ich wäre trotzdem dankbar für eine Bestätigung von jemandem, der besser informiert ist als ich. :) :)

Wenn ich weiß, dass meine HashMap beispielsweise 100 Objekte enthält und die meiste Zeit mit 100 Objekten verbracht wird, schätze ich, dass die optimalen Werte die Anfangskapazität 100 und der Lastfaktor 1 sind. Oder brauche ich Kapazität 101 oder gibt es noch andere Fallstricke?

EDIT: OK, ich habe ein paar Stunden eingeplant und einige Tests durchgeführt. Hier sind die Ergebnisse:

• Seltsamerweise liefern Kapazität, Kapazität + 1, Kapazität + 2, Kapazität 1 und sogar Kapazität 10 genau die gleichen Ergebnisse. Ich würde erwarten, dass mindestens Kapazität 1 und Kapazität 10 schlechtere Ergebnisse liefern.
• Die Verwendung der Anfangskapazität (im Gegensatz zur Verwendung des Standardwerts von 16) führt zu einer spürbaren Verbesserung von put () - bis zu 30% schneller.
• Die Verwendung des Lastfaktors 1 bietet die gleiche Leistung für eine kleine Anzahl von Objekten und eine bessere Leistung für eine größere Anzahl von Objekten (> 100000). Dies verbessert sich jedoch nicht proportional zur Anzahl der Objekte. Ich vermute, dass es einen zusätzlichen Faktor gibt, der die Ergebnisse beeinflusst.
• Die Leistung von get () ist für unterschiedliche Anzahlen von Objekten / Kapazitäten etwas unterschiedlich, kann jedoch von Fall zu Fall geringfügig variieren, wird jedoch im Allgemeinen nicht von der anfänglichen Kapazität oder dem Auslastungsfaktor beeinflusst.

EDIT2: Ich füge auch einige Diagramme hinzu. Hier ist der Unterschied zwischen dem Auslastungsfaktor 0,75 und 1, wenn ich HashMap initialisiere und bis zur vollen Kapazität fülle. Auf der y-Skala ist die Zeit in ms (niedriger ist besser) und auf der x-Skala ist die Größe (Anzahl der Objekte). Da sich die Größe linear ändert, wächst auch die erforderliche Zeit linear.

Also mal sehen, was ich habe. Die folgenden beiden Diagramme zeigen den Unterschied in den Lastfaktoren. Das erste Diagramm zeigt, was passiert, wenn HashMap voll ist. Der Lastfaktor 0,75 ist aufgrund der Größenänderung schlechter. Es ist jedoch nicht durchweg schlimmer und es gibt alle möglichen Unebenheiten und Sprünge - ich denke, dass GC dabei eine große Rolle spielt. Der Lastfaktor 1,25 entspricht 1, ist also nicht im Diagramm enthalten.

Diese Grafik zeigt, dass 0,75 aufgrund der Größenänderung schlechter war. Wenn wir die HashMap mit der halben Kapazität füllen, ist 0,75 nicht schlechter, nur ... anders (und es sollte weniger Speicher verbrauchen und eine merklich bessere Iterationsleistung haben).

Noch etwas möchte ich zeigen. Dies ist die Leistung für alle drei Lastfaktoren und verschiedene HashMap-Größen. Konsequent konstant mit einer kleinen Variation, bis auf eine Spitze für Lastfaktor 1. Ich möchte wirklich wissen, was das ist (wahrscheinlich GC, aber wer weiß).

Und hier ist der Code für Interessierte:

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

}

Okay, um dieses Problem zu lösen, habe ich eine Test-App erstellt, mit der einige Szenarien ausgeführt und einige Visualisierungen der Ergebnisse abgerufen werden können. So werden die Tests durchgeführt:

• Es wurden verschiedene Sammlungsgrößen ausprobiert: einhundert, eintausend und einhunderttausend Einträge.
• Die verwendeten Schlüssel sind Instanzen einer Klasse, die durch eine ID eindeutig identifiziert werden. Jeder Test verwendet eindeutige Schlüssel mit inkrementierenden Ganzzahlen als IDs. Die equalsMethode verwendet nur die ID, sodass keine Schlüsselzuordnung eine andere überschreibt.
• Die Schlüssel erhalten einen Hash-Code, der aus dem Modulrest ihrer ID gegen eine voreingestellte Nummer besteht. Wir nennen diese Nummer das Hash-Limit . Dadurch konnte ich die Anzahl der zu erwartenden Hash-Kollisionen steuern. Wenn unsere Sammlungsgröße beispielsweise 100 beträgt, haben wir Schlüssel mit IDs zwischen 0 und 99. Wenn das Hash-Limit 100 beträgt, hat jeder Schlüssel einen eindeutigen Hash-Code. Wenn das Hash-Limit 50 ist, hat Schlüssel 0 den gleichen Hash-Code wie Schlüssel 50, 1 hat den gleichen Hash-Code wie 51 usw. Mit anderen Worten, die erwartete Anzahl von Hash-Kollisionen pro Schlüssel ist die Sammlungsgröße geteilt durch den Hash Grenze.
• Für jede Kombination aus Sammlungsgröße und Hash-Limit habe ich den Test mit Hash-Maps ausgeführt, die mit unterschiedlichen Einstellungen initialisiert wurden. Diese Einstellungen sind der Auslastungsfaktor und eine Anfangskapazität, die als Faktor der Erfassungseinstellung ausgedrückt wird. Ein Test mit einer Sammlungsgröße von 100 und einem anfänglichen Kapazitätsfaktor von 1,25 initialisiert beispielsweise eine Hash-Karte mit einer anfänglichen Kapazität von 125.
• Der Wert für jeden Schlüssel ist einfach neu Object.
• Jedes Testergebnis ist in einer Instanz einer Ergebnisklasse gekapselt. Am Ende aller Tests werden die Ergebnisse von der schlechtesten zur besten Gesamtleistung geordnet.
• Die durchschnittliche Zeit für Puts und Gets wird pro 10 Puts / Gets berechnet.
• Alle Testkombinationen werden einmal ausgeführt, um den Einfluss der JIT-Kompilierung zu beseitigen. Danach werden die Tests für die tatsächlichen Ergebnisse ausgeführt.

Hier ist die Klasse:

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

        }

    }

}

Das Ausführen kann eine Weile dauern. Die Ergebnisse werden standardmäßig ausgedruckt. Sie werden vielleicht bemerken, dass ich eine Zeile auskommentiert habe. Diese Zeile ruft einen Visualizer auf, der visuelle Darstellungen der Ergebnisse in PNG-Dateien ausgibt. Die Klasse hierfür ist unten angegeben. Wenn Sie es ausführen möchten, kommentieren Sie die entsprechende Zeile im obigen Code aus. Seien Sie gewarnt: Die Visualizer-Klasse geht davon aus, dass Sie unter Windows ausgeführt werden, und erstellt Ordner und Dateien in C: \ temp. Passen Sie dies an, wenn Sie auf einer anderen Plattform ausgeführt werden.

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

    }

}

Die visualisierte Ausgabe lautet wie folgt:

• Die Tests werden zuerst nach Sammlungsgröße und dann nach Hash-Limit unterteilt.
• Für jeden Test gibt es ein Ausgabebild bezüglich der durchschnittlichen Put-Zeit (pro 10 Puts) und der durchschnittlichen Get-Zeit (pro 10 Gets). Die Bilder sind zweidimensionale "Wärmekarten", die eine Farbe pro Kombination aus Anfangskapazität und Lastfaktor zeigen.
• Die Farben in den Bildern basieren auf der durchschnittlichen Zeit auf einer normalisierten Skala vom besten bis zum schlechtesten Ergebnis, die von gesättigtem Grün bis zu gesättigtem Rot reicht. Mit anderen Worten, die beste Zeit ist vollständig grün, während die schlechteste Zeit vollständig rot ist. Zwei verschiedene Zeitmessungen sollten niemals dieselbe Farbe haben.
• Die Farbkarten werden für Puts und Get separat berechnet, umfassen jedoch alle Tests für ihre jeweiligen Kategorien.
• Die Visualisierungen zeigen die Anfangskapazität auf ihrer x-Achse und den Lastfaktor auf der y-Achse.

Schauen wir uns ohne weiteres die Ergebnisse an. Ich werde mit den Ergebnissen für Puts beginnen.

Ergebnisse setzen

Sammlungsgröße: 100. Hash-Limit: 50. Dies bedeutet, dass jeder Hash-Code zweimal vorkommen sollte und jeder andere Schlüssel in der Hash-Map kollidiert.

Nun, das fängt nicht sehr gut an. Wir sehen, dass es einen großen Hotspot für eine Anfangskapazität gibt, die 25% über der Sammlungsgröße liegt, mit einem Auslastungsfaktor von 1. Die untere linke Ecke funktioniert nicht besonders gut.

Sammlungsgröße: 100. Hash-Limit: 90. Jeder zehnte Schlüssel hat einen doppelten Hash-Code.

Dies ist ein etwas realistischeres Szenario, das keine perfekte Hash-Funktion hat, aber dennoch eine Überlastung von 10% aufweist. Der Hotspot ist weg, aber die Kombination einer geringen Anfangskapazität mit einem niedrigen Auslastungsfaktor funktioniert offensichtlich nicht.

Sammlungsgröße: 100. Hash-Limit: 100. Jeder Schlüssel als eigener eindeutiger Hash-Code. Keine Kollisionen zu erwarten, wenn genügend Eimer vorhanden sind.

Eine Anfangskapazität von 100 mit einem Lastfaktor von 1 scheint in Ordnung zu sein. Überraschenderweise ist eine höhere Anfangskapazität mit einem niedrigeren Auslastungsfaktor nicht unbedingt gut.

Sammlungsgröße: 1000. Hash-Limit: 500. Hier wird es mit 1000 Einträgen immer ernster. Genau wie im ersten Test gibt es eine Hash-Überladung von 2 zu 1.

Die untere linke Ecke läuft immer noch nicht gut. Es scheint jedoch eine Symmetrie zwischen der Kombination aus niedrigerer Anfangszahl / hohem Lastfaktor und höherer Anfangszahl / niedrigem Lastfaktor zu bestehen.

Sammlungsgröße: 1000. Hash-Limit: 900. Dies bedeutet, dass jeder zehnte Hash-Code zweimal vorkommt. Angemessenes Szenario in Bezug auf Kollisionen.

Es ist etwas sehr lustiges los mit der unwahrscheinlichen Kombination einer Anfangskapazität, die mit einem Auslastungsfaktor über 1 zu niedrig ist, was ziemlich kontraintuitiv ist. Ansonsten noch recht symmetrisch.

Sammlungsgröße: 1000. Hash-Limit: 990. Einige Kollisionen, aber nur wenige. In dieser Hinsicht ziemlich realistisch.

Wir haben hier eine schöne Symmetrie. Die untere linke Ecke ist immer noch nicht optimal, aber die Combos 1000 Init-Kapazität / 1,0 Lastfaktor gegenüber 1250 Init-Kapazität / 0,75 Lastfaktor sind auf dem gleichen Niveau.

Sammlungsgröße: 1000. Hash-Limit: 1000. Keine doppelten Hash-Codes, jetzt jedoch mit einer Stichprobengröße von 1000.

Hier gibt es nicht viel zu sagen. Die Kombination einer höheren Anfangskapazität mit einem Lastfaktor von 0,75 scheint die Kombination von 1000 Anfangskapazitäten mit einem Lastfaktor von 1 leicht zu übertreffen.

Sammlungsgröße: 100_000. Hash-Limit: 10_000. Okay, es wird jetzt ernst, mit einer Stichprobengröße von einhunderttausend und 100 Hash-Code-Duplikaten pro Schlüssel.

Huch! Ich denke, wir haben unser unteres Spektrum gefunden. Eine Init-Kapazität von genau der Sammlungsgröße mit einem Auslastungsfaktor von 1 ist hier wirklich gut, aber ansonsten ist es überall im Shop.

Sammlungsgröße: 100_000. Hash-Limit: 90_000. Etwas realistischer als der vorherige Test, hier haben wir eine 10% ige Überlastung der Hash-Codes.

Die untere linke Ecke ist immer noch unerwünscht. Höhere Anfangskapazitäten funktionieren am besten.

Sammlungsgröße: 100_000. Hash-Limit: 99_000. Gutes Szenario, das. Eine große Sammlung mit einer 1% igen Hash-Code-Überladung.

Hier gewinnt die exakte Sammlungsgröße als Init-Kapazität mit einem Auslastungsfaktor von 1! Etwas größere Init-Kapazitäten funktionieren jedoch recht gut.

Sammlungsgröße: 100_000. Hash-Limit: 100_000. Der Grosse. Größte Sammlung mit perfekter Hash-Funktion.

Einige überraschende Sachen hier. Eine anfängliche Kapazität mit 50% zusätzlichem Raum bei einem Auslastungsfaktor von 1 gewinnt.

Okay, das ist es für die Puts. Jetzt werden wir die bekommen überprüfen. Denken Sie daran, dass die folgenden Karten alle relativ zu den besten / schlechtesten Abrufzeiten sind. Die Put-Zeiten werden nicht mehr berücksichtigt.

Ergebnisse bekommen

Sammlungsgröße: 100. Hash-Limit: 50. Dies bedeutet, dass jeder Hash-Code zweimal vorkommen sollte und jeder andere Schlüssel in der Hash-Map kollidieren sollte.

Eh ... was?

Sammlungsgröße: 100. Hash-Limit: 90. Jeder zehnte Schlüssel hat einen doppelten Hash-Code.

Whoa Nelly! Dies ist das wahrscheinlichste Szenario, das mit der Frage des Fragestellers korreliert, und anscheinend ist eine Anfangskapazität von 100 mit einem Auslastungsfaktor von 1 eines der schlimmsten Dinge hier! Ich schwöre, ich habe das nicht vorgetäuscht.

Sammlungsgröße: 100. Hash-Limit: 100. Jeder Schlüssel als eigener eindeutiger Hash-Code. Keine Kollisionen zu erwarten.

Das sieht etwas friedlicher aus. Meist die gleichen Ergebnisse auf ganzer Linie.

Sammlungsgröße: 1000. Hash-Limit: 500. Genau wie im ersten Test gibt es eine Hash-Überladung von 2 zu 1, aber jetzt mit viel mehr Einträgen.

Es sieht so aus, als würde jede Einstellung hier ein anständiges Ergebnis liefern.

Sammlungsgröße: 1000. Hash-Limit: 900. Dies bedeutet, dass jeder zehnte Hash-Code zweimal vorkommt. Angemessenes Szenario in Bezug auf Kollisionen.

Und genau wie bei den Puts für dieses Setup erhalten wir eine Anomalie an einer seltsamen Stelle.

Sammlungsgröße: 1000. Hash-Limit: 990. Einige Kollisionen, aber nur wenige. In dieser Hinsicht ziemlich realistisch.

Überall gute Leistung, abgesehen von der Kombination einer hohen Anfangskapazität mit einem niedrigen Lastfaktor. Ich würde dies für die Puts erwarten, da zwei Größenänderungen der Hash-Map erwartet werden könnten. Aber warum auf die bekommen?

Sammlungsgröße: 1000. Hash-Limit: 1000. Keine doppelten Hash-Codes, jetzt jedoch mit einer Stichprobengröße von 1000.

Eine völlig unspektakuläre Visualisierung. Dies scheint zu funktionieren, egal was passiert.

Sammlungsgröße: 100_000. Hash-Limit: 10_000. Wieder in die 100K gehen, mit einer ganzen Menge Hash-Code-Überlappungen.

Es sieht nicht schön aus, obwohl die schlechten Stellen sehr lokalisiert sind. Die Leistung scheint hier weitgehend von einer gewissen Synergie zwischen den Einstellungen abzuhängen.

Sammlungsgröße: 100_000. Hash-Limit: 90_000. Etwas realistischer als der vorherige Test, hier haben wir eine 10% ige Überlastung der Hash-Codes.

Viel Varianz, obwohl Sie beim Schielen einen Pfeil sehen können, der in die obere rechte Ecke zeigt.

Sammlungsgröße: 100_000. Hash-Limit: 99_000. Gutes Szenario, das. Eine große Sammlung mit einer 1% igen Hash-Code-Überladung.

Sehr chaotisch. Es ist schwer, hier viel Struktur zu finden.

Sammlungsgröße: 100_000. Hash-Limit: 100_000. Der Grosse. Größte Sammlung mit perfekter Hash-Funktion.

Glaubt noch jemand, dass dies allmählich wie Atari-Grafiken aussieht? Dies scheint eine Anfangskapazität von genau der Sammlungsgröße von -25% oder + 50% zu begünstigen.

Okay, jetzt ist es Zeit für Schlussfolgerungen ...

• In Bezug auf Put-Zeiten: Sie möchten anfängliche Kapazitäten vermeiden, die niedriger sind als die erwartete Anzahl von Karteneinträgen. Wenn eine genaue Zahl vorher bekannt ist, scheint diese Zahl oder etwas etwas darüber am besten zu funktionieren. Hohe Lastfaktoren können niedrigere Anfangskapazitäten aufgrund früherer Größenänderungen der Hash-Map ausgleichen. Für höhere Anfangskapazitäten scheinen sie nicht so wichtig zu sein.
• In Bezug auf Get-Zeiten: Die Ergebnisse sind hier etwas chaotisch. Es gibt nicht viel zu schließen. Es scheint sehr stark von subtilen Verhältnissen zwischen Hash-Code-Überlappung, Anfangskapazität und Ladefaktor abhängig zu sein, wobei einige vermeintlich schlechte Setups gut und gute Setups furchtbar funktionieren.
• Ich bin anscheinend voller Mist, wenn es um Annahmen über die Java-Leistung geht. Die Wahrheit ist, wenn Sie Ihre Einstellungen nicht perfekt auf die Implementierung von abstimmen HashMap, werden die Ergebnisse überall sein. Wenn Sie etwas davon wegnehmen möchten, ist die Standard-Anfangsgröße von 16 für alles andere als die kleinsten Karten etwas dumm. Verwenden Sie also einen Konstruktor, der die Anfangsgröße festlegt, wenn Sie eine Vorstellung von der Größenordnung haben Es wird.
• Wir messen hier in Nanosekunden. Die beste durchschnittliche Zeit pro 10 Puts betrug 1179 ns und die schlechteste 5105 ns auf meiner Maschine. Die beste durchschnittliche Zeit pro 10 bekommen war 547 ns und die schlechteste 3484 ns. Das mag ein Unterschied von Faktor 6 sein, aber wir sprechen weniger als eine Millisekunde. Auf Sammlungen, die weitaus größer sind als das, was das Originalplakat vorhatte.

Das war's. Ich hoffe, mein Code hat kein schreckliches Versehen, das alles ungültig macht, was ich hier gepostet habe. Das hat Spaß gemacht, und ich habe gelernt, dass Sie sich am Ende genauso gut auf Java verlassen können, um seinen Job zu erledigen, als von winzigen Optimierungen einen großen Unterschied zu erwarten. Das heißt nicht, dass einige Dinge nicht vermieden werden sollten, aber dann geht es hauptsächlich darum, lange Strings in for-Schleifen zu konstruieren, die falschen Datenstrukturen zu verwenden und O (n ^ 3) -Algorithmen zu erstellen.

Dies ist ein ziemlich guter Thread, außer dass es eine entscheidende Sache gibt, die Sie vermissen. Du sagtest:

Seltsamerweise liefern Kapazität, Kapazität + 1, Kapazität + 2, Kapazität 1 und sogar Kapazität 10 genau die gleichen Ergebnisse. Ich würde erwarten, dass mindestens Kapazität 1 und Kapazität 10 schlechtere Ergebnisse liefern.

Der Quellcode überspringt die Anfangskapazität intern um die nächsthöhere Zweierpotenz. Dies bedeutet, dass beispielsweise Anfangskapazitäten von 513, 600, 700, 800, 900, 1000 und 1024 alle dieselbe Anfangskapazität verwenden (1024). Dies macht die von @G_H durchgeführten Tests jedoch nicht ungültig. Man sollte sich darüber im Klaren sein, dass dies durchgeführt wird, bevor man seine Ergebnisse analysiert. Und es erklärt das merkwürdige Verhalten einiger Tests.

Dies ist das Konstruktorrecht für die JDK-Quelle:

/**
 * 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();
}

Geh einfach mit 101. Ich bin mir nicht sicher, ob es gebraucht wird, aber es könnte unmöglich die Mühe wert sein, es jemals sicher herauszufinden.

... einfach hinzufügen 1.

EDIT: Eine Begründung für meine Antwort.

Erstens gehe ich davon aus, dass Ihr HashMapWille nicht darüber hinaus wächst 100. Wenn dies der Fall ist, sollten Sie den Lastfaktor unverändert lassen. Wenn es um Leistung geht, lassen Sie den Lastfaktor unverändert . Wenn es um Speicher geht, können Sie einige speichern, indem Sie die statische Größe festlegen. Dies könnte sich vielleicht lohnen, wenn Sie eine Menge Dinge in Erinnerung behalten. Das heißt, Sie speichern viele Karten oder erstellen Karten in Heap-Space-Stressing-Größe.

Zweitens wähle ich den Wert, 101weil er eine bessere Lesbarkeit bietet. Wenn ich Ihren Code anschließend betrachte und feststelle, dass Sie die anfängliche Kapazität auf eingestellt haben 100und ihn mit 100Elementen laden , muss ich dies tun Lesen Sie das Javadoc durch, um sicherzustellen, dass die Größe nicht geändert wird, wenn es genau erreicht wird 100. Natürlich werde ich dort keine Antwort finden, also muss ich mir die Quelle ansehen. Das ist es nicht wert ... lass es einfach 101und jeder ist glücklich und niemand schaut durch den Quellcode von java.util.HashMap. Hoorah.

Drittens die Behauptung, dass die Einstellung der HashMap exakten Kapazität, die Sie erwarten, mit einem Lastfaktor von 1 " Ihre Such- und Einfügungsleistung beeinträchtigt ", einfach nicht wahr, selbst wenn sie fett gedruckt ist.

... wenn Sie nEimer haben und nGegenstände zufällig in nEimern zuweisen , ja, werden Sie am Ende Gegenstände im selben Eimer haben, sicher ... aber das ist nicht das Ende der Welt ... in der Praxis, Es sind nur noch ein paar Vergleiche. In der Tat gibt es esp. wenig Unterschied, wenn man bedenkt, dass die Alternative darin besteht, nElemente in n/0.75Eimern zuzuweisen.

Keine Notwendigkeit, mein Wort dafür zu nehmen ...

Schnelltestcode:

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

Testergebnisse:

=======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: ↑ - da ist was dran → || ← viel Unterschied zwischen den verschiedenen Einstellungen .

In Bezug auf meine ursprüngliche Antwort (die etwas oberhalb der ersten horizontalen Linie) wurde absichtlich glib , weil in den meisten Fällen , diese Art von Mikro-Optimierung ist nicht gut .

In Bezug auf die Implementierung verfügt Google Guava über eine praktische Factory-Methode

Maps.newHashMapWithExpectedSize(expectedSize)

Welches berechnet die Kapazität mit der Formel

capacity = expectedSize / 0.75F + 1.0F

Aus dem HashMapJavaDoc:

In der Regel bietet der Standardlastfaktor (.75) einen guten Kompromiss zwischen Zeit- und Raumkosten. Höhere Werte verringern den Speicherplatzaufwand, erhöhen jedoch die Suchkosten (was sich in den meisten Operationen der HashMap-Klasse widerspiegelt, einschließlich get und put). Die erwartete Anzahl von Einträgen in der Karte und ihr Auslastungsfaktor sollten bei der Einstellung der Anfangskapazität berücksichtigt werden, um die Anzahl der Wiederaufbereitungsvorgänge zu minimieren. Wenn die Anfangskapazität größer ist als die maximale Anzahl von Einträgen geteilt durch den Lastfaktor, werden niemals Wiederaufbereitungsvorgänge durchgeführt.

Wenn Sie also 100 Einträge erwarten, ist möglicherweise ein Auslastungsfaktor von 0,75 und eine anfängliche Höchstkapazität (100 / 0,75) am besten. Das sind 134.

Ich muss zugeben, ich bin mir nicht sicher, warum die Suchkosten für einen höheren Auslastungsfaktor höher wären. Nur weil die HashMap "überfüllt" ist, heißt das nicht, dass mehr Objekte im selben Bucket platziert werden, oder? Das hängt nur von ihrem Hash-Code ab, wenn ich mich nicht irre. Sollten die meisten Fälle nicht immer noch O (1) sein, unabhängig vom Auslastungsfaktor?

EDIT: Ich sollte vor dem Posten mehr lesen ... Natürlich kann der Hash-Code nicht direkt einem internen Index zugeordnet werden. Es muss auf einen Wert reduziert werden, der der aktuellen Kapazität entspricht. Das heißt, je größer Ihre anfängliche Kapazität ist, desto geringer ist die Anzahl der Hash-Kollisionen. Wenn Sie eine Anfangskapazität wählen, die genau der Größe (oder +1) Ihres Objektsatzes mit einem Lastfaktor von 1 entspricht, wird in der Tat sichergestellt, dass die Größe Ihrer Karte niemals geändert wird. Jedoch, beeinträchtigt jedoch Ihre Such- und Einfügeleistung. Eine Größenänderung ist immer noch relativ schnell und würde möglicherweise nur einmal auftreten, während bei so ziemlich jeder relevanten Arbeit mit der Karte nachgeschlagen wird. Daher ist die Optimierung für schnelle Suchvorgänge genau das, was Sie hier wirklich wollen. Sie können dies damit kombinieren, dass Sie niemals die Größe ändern müssen, indem Sie das tun, was JavaDoc sagt: Nehmen Sie Ihre erforderliche Kapazität, dividieren Sie durch einen optimalen Auslastungsfaktor (z. B. 0,75) und verwenden Sie diese als anfängliche Kapazität mit diesem Auslastungsfaktor. Fügen Sie 1 hinzu, um sicherzustellen, dass Sie nicht gerundet werden.