java - how - ¿Cuál es la capacidad y el factor de carga óptimos para un HashMap de tamaño fijo?

how to use hashmap java

Question

Estoy tratando de descubrir la capacidad óptima y el factor de carga para un caso específico. Creo que entendí lo esencial, pero aún estaría agradecido por la confirmación de alguien más entendido que yo. :)

Si sé que mi HashMap se llenará para contener, digamos, 100 objetos y pasaré la mayor parte del tiempo teniendo 100 objetos, supongo que los valores óptimos son la capacidad inicial 100 y el factor de carga 1. ¿O necesito capacidad 101, o hay algún otro problema?

EDITAR: OK, reservé unas horas e hice algunas pruebas. Aquí están los resultados:

• Curiosamente, la capacidad, la capacidad + 1, la capacidad + 2, la capacidad-1 e incluso la capacidad-10 arrojan exactamente los mismos resultados. Yo esperaría que al menos la capacidad-1 y la capacidad-10 den peores resultados.
• El uso de la capacidad inicial (en contraposición al uso del valor predeterminado de 16) ofrece una mejora notoria de put (): hasta un 30% más rápido.
• El uso del factor de carga de 1 proporciona el mismo rendimiento para un número pequeño de objetos y un mejor rendimiento para una mayor cantidad de objetos (> 100000). Sin embargo, esto no mejora proporcionalmente a la cantidad de objetos; Sospecho que hay un factor adicional que afecta los resultados.
• El rendimiento de get () es un poco diferente para diferentes cantidades de objetos / capacidad, pero aunque puede variar ligeramente de un caso a otro, generalmente no se ve afectado por la capacidad inicial o el factor de carga.

EDIT2: También agregué algunos cuadros de mi parte. Aquí está la que ilustra la diferencia entre el factor de carga 0,75 y 1, en los casos en que inicializo HashMap y lo llevo hasta su capacidad máxima. En escala y es el tiempo en ms (menor es mejor), y x escala es el tamaño (número de objetos). Como el tamaño cambia linealmente, el tiempo requerido también crece linealmente.

Entonces, veamos lo que tengo. Los siguientes dos gráficos muestran la diferencia en los factores de carga. El primer gráfico muestra qué sucede cuando HashMap está lleno a su capacidad; el factor de carga 0,75 tiene un peor rendimiento debido al cambio de tamaño. Sin embargo, no es siempre peor, y hay todo tipo de baches y saltos, supongo que GC tiene una gran jugada en esto. El factor de carga 1.25 realiza lo mismo que 1, por lo que no está incluido en el gráfico.

Este cuadro demuestra que 0.75 fue peor debido al cambio de tamaño; si llenamos el HashMap a la mitad de la capacidad, 0.75 no es peor, solo ... es diferente (y debería usar menos memoria y tener un rendimiento de iteración indescriptiblemente mejor).

Una cosa más que quiero mostrar. Esto es obtener rendimiento para los tres factores de carga y diferentes tamaños de HashMap. Constantemente constante con una pequeña variación, excepto por un pico para el factor de carga 1. Realmente quisiera saber qué es eso (probablemente GC, pero quién sabe).

Y aquí está el código para los interesados:

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

}

Answer 1

Bien, para dejar esto de lado, he creado una aplicación de prueba para ejecutar un par de escenarios y obtener algunas visualizaciones de los resultados. Así es como se realizan las pruebas:

• Se han probado varios tamaños de colección diferentes: cien, mil cien cien entradas.
• Las claves utilizadas son instancias de una clase que están identificadas de forma única por una ID. Cada prueba usa claves únicas, con números enteros incrementales como ID. El método equals solo usa el ID, por lo que ninguna asignación de teclas sobrescribe a otra.
• Las teclas obtienen un código hash que consiste en el resto del módulo de su ID contra un número preestablecido. Llamaremos a ese número el límite de hash . Esto me permitió controlar la cantidad de colisiones hash que se esperarían. Por ejemplo, si nuestro tamaño de colección es 100, tendremos claves con ID que van de 0 a 99. Si el límite de hash es 100, cada clave tendrá un código de hash único. Si el límite de hash es 50, la clave 0 tendrá el mismo código hash que la clave 50, 1 tendrá el mismo código hash que 51, etc. En otras palabras, el número esperado de colisiones hash por clave es el tamaño de la colección dividido por el hash límite.
• Para cada combinación de tamaño de colección y límite de hash, ejecuté la prueba usando mapas hash inicializados con diferentes configuraciones. Estas configuraciones son el factor de carga y una capacidad inicial que se expresa como un factor de la configuración de recolección. Por ejemplo, una prueba con un tamaño de colección de 100 y un factor de capacidad inicial de 1.25 inicializará un mapa de hash con una capacidad inicial de 125.
• El valor para cada clave es simplemente un nuevo Object .
• Cada resultado de prueba se encapsula en una instancia de una clase Result. Al final de todas las pruebas, los resultados se ordenan del peor rendimiento general al mejor.
• El tiempo promedio para puts y gets se calcula por cada 10 puts / gets.
• Todas las combinaciones de prueba se ejecutan una vez para eliminar la influencia de compilación de JIT. Después de eso, las pruebas se ejecutan para obtener resultados reales.

Aquí está la clase:

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

        }

    }

}

Ejecutar esto puede tomar un tiempo. Los resultados se imprimen en salida estándar. Es posible que notes que he comentado una línea. Esa línea llama a un visualizador que genera representaciones visuales de los resultados en archivos png. La clase para esto se da a continuación. Si desea ejecutarlo, elimine el comentario de la línea correspondiente en el código anterior. Tenga cuidado: la clase del visualizador asume que se está ejecutando en Windows y creará carpetas y archivos en C: / temp. Cuando se ejecuta en otra plataforma, ajuste esto.

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

    }

}

La salida visualizada es la siguiente:

• Las pruebas se dividen primero por tamaño de colección y luego por límite de hash.
• Para cada prueba, hay una imagen de salida con respecto al tiempo promedio de publicación (por 10 puts) y el tiempo de obtención promedio (por cada 10 obtiene). Las imágenes son "mapas de calor" bidimensionales que muestran un color por combinación de capacidad inicial y factor de carga.
• Los colores en las imágenes se basan en el tiempo promedio en una escala normalizada de mejor a peor resultado, que van del verde saturado al rojo saturado. En otras palabras, el mejor momento será completamente verde, mientras que el peor momento será totalmente rojo. Dos medidas de tiempo diferentes nunca deben tener el mismo color.
• Los mapas de color se calculan por separado para puts y gets, pero abarcan todas las pruebas para sus respectivas categorías.
• Las visualizaciones muestran la capacidad inicial en su eje xy el factor de carga en el eje y.

Sin más preámbulos, echemos un vistazo a los resultados. Comenzaré con los resultados de puts.

Poner resultados

Tamaño de recopilación: 100. Límite hash: 50. Esto significa que cada código hash debe aparecer dos veces y cada otra clave colisiona en el mapa hash.

Bueno, eso no comienza muy bien. Vemos que hay un gran punto de acceso para una capacidad inicial del 25% por encima del tamaño de la colección, con un factor de carga de 1. La esquina inferior izquierda no funciona demasiado bien.

Tamaño de la colección: 100. Límite hash: 90. Una de cada diez teclas tiene un código hash duplicado.

Este es un escenario un poco más realista, ya que no tiene una función hash perfecta, pero aún tiene un 10% de sobrecarga. El punto de acceso desapareció, pero la combinación de una capacidad inicial baja con un factor de carga bajo obviamente no funciona.

Tamaño de colección: 100. Límite hash: 100. Cada clave como su propio código hash único. No se esperan colisiones si hay suficientes cubos.

Una capacidad inicial de 100 con un factor de carga de 1 parece estar bien. Sorprendentemente, una capacidad inicial más alta con un factor de carga menor no es necesariamente bueno.

Tamaño de la colección: 1000. Límite hash: 500. Se está volviendo más serio aquí, con 1000 entradas. Al igual que en la primera prueba, hay una sobrecarga hash de 2 a 1.

La esquina inferior izquierda todavía no está funcionando bien. Pero parece haber una simetría entre el combo de menor recuento inicial / factor de carga alto y mayor recuento inicial / factor de carga bajo.

Tamaño de la colección: 1000. Límite hash: 900. Esto significa que uno de cada diez códigos hash ocurrirá dos veces. Escenario razonable con respecto a las colisiones.

Hay algo muy divertido pasando con el improbable combo de una capacidad inicial que es demasiado bajo con un factor de carga superior a 1, lo que es bastante contrario a la intuición. De lo contrario, sigue siendo bastante simétrico.

Tamaño de la colección: 1000. Límite hash: 990. Algunas colisiones, pero solo algunas. Muy realista a este respecto.

Tenemos una buena simetría aquí. La esquina inferior izquierda aún no es óptima, pero la capacidad de inicio de los combos 1000 / factor de carga de 1.0 contra la capacidad de inicio de 1250 / factor de carga de 0.75 están en el mismo nivel.

Tamaño de la colección: 1000. Límite hash: 1000. No hay códigos hash duplicados, pero ahora con un tamaño de muestra de 1000.

No hay mucho que decir aquí. La combinación de una capacidad inicial más alta con un factor de carga de 0,75 parece superar ligeramente a la combinación de la capacidad inicial de 1000 con un factor de carga de 1.

Tamaño de la colección: 100_000. Límite de hash: 10_000. De acuerdo, se está poniendo serio ahora, con un tamaño de muestra de cien mil y 100 duplicados de código hash por clave.

¡Ay! Creo que encontramos nuestro espectro más bajo. Una capacidad de inicio de exactamente el tamaño de la colección con un factor de carga de 1 está yendo muy bien aquí, pero aparte de eso, está por toda la tienda.

Tamaño de la colección: 100_000. Límite hash: 90_000. Un poco más realista que la prueba anterior, aquí tenemos una sobrecarga del 10% en códigos hash.

La esquina inferior izquierda sigue siendo indeseable. Las capacidades iniciales más altas funcionan mejor.

Tamaño de la colección: 100_000. Límite de hash: 99_000. Buen escenario, esto. Una gran colección con una sobrecarga de código hash del 1%.

Usando el tamaño de colección exacto como capacidad de inicio con un factor de carga de 1, ¡gana aquí! Sin embargo, las capacidades de inicio ligeramente mayores funcionan bastante bien.

Tamaño de la colección: 100_000. Límite de hash: 100_000. El Grande. La colección más grande con una función hash perfecta.

Algunas cosas sorprendentes aquí. Una capacidad inicial con 50% de espacio adicional con un factor de carga de 1 gana.

Bien, eso es todo por las puts. Ahora, revisaremos los get. Recuerde, los mapas a continuación son todos relativos a los mejores / peores tiempos de obtención, los tiempos de entrega ya no se tienen en cuenta.

Tener resultados

Tamaño de recopilación: 100. Límite hash: 50. Esto significa que cada código hash debe aparecer dos veces y se espera que cada otra clave colisione en el mapa hash.

Eh ... ¿Qué?

Tamaño de la colección: 100. Límite hash: 90. Una de cada diez teclas tiene un código hash duplicado.

Whoa Nelly! Este es el escenario más probable para correlacionarse con la pregunta del consultante, y aparentemente una capacidad inicial de 100 con un factor de carga de 1 es una de las peores cosas aquí. Te juro que no fingí esto.

Tamaño de colección: 100. Límite hash: 100. Cada clave como su propio código hash único. No se esperan colisiones.

Esto se ve un poco más pacífico. En su mayoría, los mismos resultados en todos los ámbitos.

Tamaño de la colección: 1000. Límite hash: 500. Al igual que en la primera prueba, hay una sobrecarga hash de 2 a 1, pero ahora con muchas más entradas.

Parece que cualquier configuración arrojará un resultado decente aquí.

Tamaño de la colección: 1000. Límite hash: 900. Esto significa que uno de cada diez códigos hash ocurrirá dos veces. Escenario razonable con respecto a las colisiones.

Y al igual que con las estrategias para esta configuración, obtenemos una anomalía en un lugar extraño.

Tamaño de la colección: 1000. Límite hash: 990. Algunas colisiones, pero solo algunas. Muy realista a este respecto.

Un rendimiento decente en todas partes, excepto por la combinación de una alta capacidad inicial con un factor de carga bajo. Esperaría esto para las puts, ya que se podrían esperar dos cambios de tamaño en el hash. Pero ¿por qué en el consigue?

Tamaño de la colección: 1000. Límite hash: 1000. No hay códigos hash duplicados, pero ahora con un tamaño de muestra de 1000.

Una visualización completamente poco espectacular. Esto parece funcionar sin importar qué.

Tamaño de la colección: 100_000. Límite de hash: 10_000. Entrando en el 100K nuevamente, con una gran cantidad de superposición de código hash.

No se ve bonito, aunque los puntos malos están muy localizados. El rendimiento aquí parece depender en gran medida de una cierta sinergia entre las configuraciones.

Tamaño de la colección: 100_000. Límite hash: 90_000. Un poco más realista que la prueba anterior, aquí tenemos una sobrecarga del 10% en códigos hash.

Mucha variación, aunque si entrecierra los ojos puede ver una flecha que apunta a la esquina superior derecha.

Tamaño de la colección: 100_000. Límite de hash: 99_000. Buen escenario, esto. Una gran colección con una sobrecarga de código hash del 1%.

Muy caótico Es difícil encontrar mucha estructura aquí.

Tamaño de la colección: 100_000. Límite de hash: 100_000. El Grande. La colección más grande con una función hash perfecta.

¿Alguien más piensa que esto empieza a parecerse a los gráficos de Atari? Esto parece favorecer una capacidad inicial de exactamente el tamaño de la colección, -25% o + 50%.

Bien, es hora de sacar conclusiones ahora ...

• En cuanto a los tiempos de venta: deseará evitar las capacidades iniciales que son menores que el número esperado de entradas de mapas. Si se conoce un número exacto de antemano, ese número o algo ligeramente por encima parece funcionar mejor. Los factores de alta carga pueden compensar las capacidades iniciales más bajas debido al cambio de tamaño del mapa hash anterior. Para capacidades iniciales más altas, no parecen importar tanto.
• En cuanto a los tiempos de obtención: los resultados son ligeramente caóticos aquí. No hay mucho que concluir. Parece depender en gran medida de las sutiles proporciones entre la superposición del código hash, la capacidad inicial y el factor de carga, con algunas configuraciones supuestamente malas que funcionan bien y las configuraciones buenas se desempeñan terriblemente.
• Aparentemente estoy lleno de basura cuando se trata de suposiciones sobre el rendimiento de Java. La verdad es que, a menos que esté ajustando su configuración a la implementación de HashMap , los resultados van a estar por todos lados. Si hay algo que se puede sacar de esto, es que el tamaño inicial predeterminado de 16 es un poco tonto para cualquier cosa que no sean los mapas más pequeños, así que use un constructor que establezca el tamaño inicial si tiene alguna idea sobre el orden de tamaño Va a ser.
• Estamos midiendo en nanosegundos aquí. El mejor tiempo promedio por 10 puts fue 1179 ns y el peor 5105 ns en mi máquina. El mejor tiempo promedio por cada 10 intentos fue de 547 ns y el peor de 3484 ns. Esa puede ser una diferencia de factor 6, pero estamos hablando de menos de un milisegundo. En colecciones que son mucho más grandes de lo que el cartel original tenía en mente.

Bueno, eso es todo. Espero que mi código no tenga un descuido horrendo que invalide todo lo que he publicado aquí. Esto ha sido divertido, y he aprendido que al final puede confiar en Java para hacer su trabajo que esperar mucha diferencia de pequeñas optimizaciones. Eso no quiere decir que algunas cosas no deban evitarse, pero en general estamos hablando de construir cadenas largas en bucles for, usar las estructuras de datos incorrectas y hacer algoritmos O (n ^ 3).

Answer 2

Este es un hilo bastante bueno, excepto que hay una cosa crucial que te estás perdiendo. Tu dijiste:

Curiosamente, la capacidad, la capacidad + 1, la capacidad + 2, la capacidad-1 e incluso la capacidad-10 arrojan exactamente los mismos resultados. Yo esperaría que al menos la capacidad-1 y la capacidad-10 den peores resultados.

El código fuente salta la capacidad inicial la siguiente potencia más alta internamente. Eso significa que, por ejemplo, las capacidades iniciales de 513, 600, 700, 800, 900, 1000 y 1024 usarán la misma capacidad inicial (1024). Esto no invalida las pruebas hechas por @G_H, sin embargo, uno debe darse cuenta de que esto se está haciendo antes de analizar sus resultados. Y explica el comportamiento extraño de algunas de las pruebas.

Este es el derecho de constructor para la fuente 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();
}

Answer 3

Solo ve con 101 . Realmente no estoy seguro de que sea necesario, pero no podría valer la pena el esfuerzo de molestarme en descubrirlo con certeza.

... solo agrega el 1 .

EDITAR: Alguna justificación para mi respuesta.

Primero, supongo que su HashMap no crecerá más allá de 100 ; si lo hace, debe dejar el factor de carga tal como está. Del mismo modo, si su preocupación es el rendimiento, deje el factor de carga como está . Si su preocupación es la memoria, puede guardarla configurando el tamaño estático. Quizás valga la pena hacerlo si estás metiendo muchas cosas en la memoria; es decir, están almacenando muchos mapas o creando mapas del tamaño de un montón de estrés.

En segundo lugar, elijo el valor 101 porque ofrece una mejor legibilidad ... si luego miro tu código y veo que has establecido la capacidad inicial en 100 y la estás cargando con 100 elementos, voy a tener que leer el Javadoc para asegurarse de que no cambiará de tamaño cuando llegue exactamente a 100 . Por supuesto, no encontraré la respuesta allí, así que tendré que mirar la fuente. Esto no vale la pena ... simplemente déjalo en 101 y todos están contentos y nadie está mirando el código fuente de java.util.HashMap . Hoorah.

En tercer lugar, la afirmación de que configurar el HashMap a la capacidad exacta de lo que espera con un factor de carga de 1 " matará su búsqueda y rendimiento de inserción " no es cierto, incluso si está hecho en negrita.

... si tienes n cubos, y asignas aleatoriamente n elementos en n cubos, sí, vas a terminar con elementos en el mismo cubo, seguro ... pero ese no es el fin del mundo ... en la práctica, es solo un par más de comparaciones iguales. De hecho, hay esp. poca diferencia cuando se considera que la alternativa es asignar n elementos en n/0.75 cubos.

No hay necesidad de creer en mi palabra ...

Código de prueba rápida:

static Random r = new Random();

public static void main(String[] args){
    int[] tests = {100, 1000, 10000};
    int runs = 5000;

    float lf_sta = 1f;
    float lf_dyn = 0.75f;

    for(int t:tests){
        System.err.println("=======Test Put "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        long norm_put = testInserts(map, t, runs);
        System.err.print("Norm put:"+norm_put+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        long sta_put = testInserts(map, t, runs);
        System.err.print("Static put:"+sta_put+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        long dyn_put = testInserts(map, t, runs);
        System.err.println("Dynamic put:"+dyn_put+" ms. ");
    }

    for(int t:tests){
        System.err.println("=======Test Get (hits) "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        fill(map, t);
        long norm_get_hits = testGetHits(map, t, runs);
        System.err.print("Norm get (hits):"+norm_get_hits+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        fill(map, t);
        long sta_get_hits = testGetHits(map, t, runs);
        System.err.print("Static get (hits):"+sta_get_hits+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        fill(map, t);
        long dyn_get_hits = testGetHits(map, t, runs);
        System.err.println("Dynamic get (hits):"+dyn_get_hits+" ms. ");
    }

    for(int t:tests){
        System.err.println("=======Test Get (Rand) "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        fill(map, t);
        long norm_get_rand = testGetRand(map, t, runs);
        System.err.print("Norm get (rand):"+norm_get_rand+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        fill(map, t);
        long sta_get_rand = testGetRand(map, t, runs);
        System.err.print("Static get (rand):"+sta_get_rand+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        fill(map, t);
        long dyn_get_rand = testGetRand(map, t, runs);
        System.err.println("Dynamic get (rand):"+dyn_get_rand+" ms. ");
    }
}

public static long testInserts(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    for(int i=0; i<runs; i++){
        fill(map, test);
        map.clear();
    }
    return System.currentTimeMillis()-b4;
}

public static void fill(HashMap<Integer,Integer> map, int test){
    for(int j=0; j<test; j++){
        if(map.put(r.nextInt(), j)!=null){
            j--;
        }
    }
}

public static long testGetHits(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    ArrayList<Integer> keys = new ArrayList<Integer>();
    keys.addAll(map.keySet());

    for(int i=0; i<runs; i++){
        for(int j=0; j<test; j++){
            keys.get(r.nextInt(keys.size()));
        }
    }
    return System.currentTimeMillis()-b4;
}

public static long testGetRand(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    for(int i=0; i<runs; i++){
        for(int j=0; j<test; j++){
            map.get(r.nextInt());
        }
    }
    return System.currentTimeMillis()-b4;
}

Test Results:

=======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: ↑ — there''s about this →||← much difference between the different settings .

With respect to my original answer (the bit above the first horizontal line), it was deliberately glib because in most cases , this type of micro-optimising is not good .

Answer 4

From the HashMap JavaDoc:

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

So if you''re expecting 100 entries, perhaps a load factor of 0.75 and an initial capacity of ceiling(100/0.75) would be best. That comes down to 134.

I have to admit, I''m not certain why lookup cost would be greater for a higher load factor. Just because the HashMap is more "crowded" doesn''t mean that more objects will be placed in the same bucket, right? That only depends on their hash code, if I''m not mistaken. So assuming a decent hash code spread, shouldn''t most cases still be O(1) regardless of load factor?

EDIT: I should read more before posting... Of course the hash code cannot directly map to some internal index. It must be reduced to a value that fits the current capacity. Meaning that the greater your initial capacity, the smaller you can expect the number of hash collisions to be. Choosing an initial capacity exactly the size (or +1) of your object set with a load factor of 1 will indeed make sure that your map is never resized. However, it will kill your lookup and insertion performance . A resize is still relatively quick and would only occur maybe once, while lookups are done on pretty much any relevant work with the map. As a result, optimizing for quick lookups is what you really want here. You can combine that with never having to resize by doing as the JavaDoc says: take your required capacity, divide by an optimal load factor (eg 0.75) and use that as the initial capacity, with that load factor. Add 1 to make sure rounding doesn''t get you.