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

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

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

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 producen exactamente los mismos resultados. Esperaría que al menos la capacidad 1 y la capacidad 10 den peores resultados.
• El uso de la capacidad inicial (en lugar de usar el valor predeterminado de 16) proporciona una mejora notable de put (), hasta un 30% más rápido.
• El uso de un factor de carga de 1 proporciona el mismo rendimiento para un número reducido de objetos y un mejor rendimiento para un mayor número de objetos (> 100000). Sin embargo, esto no mejora proporcionalmente al número de objetos; Sospecho que hay un factor adicional que afecta los resultados.
• El rendimiento de get () es un poco diferente para diferentes números 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: Añadiendo algunos gráficos de mi parte también. 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 lleno hasta su capacidad máxima. En la escala y es el tiempo en ms (cuanto más bajo, mejor) y la escala x es el tamaño (número de objetos). Dado que el tamaño cambia linealmente, el tiempo requerido también crece linealmente.

Entonces, veamos qué tengo. Los siguientes dos gráficos muestran la diferencia en los factores de carga. El primer gráfico muestra lo que sucede cuando HashMap se llena al máximo de su capacidad; el factor de carga 0,75 funciona peor debido al cambio de tamaño. Sin embargo, no es siempre peor, y hay todo tipo de baches y saltos; supongo que GC tiene un papel importante en esto. El factor de carga 1,25 funciona igual que 1, por lo que no se incluye en el gráfico.

Este gráfico demuestra que 0,75 fue peor debido al cambio de tamaño; Si llenamos el HashMap a la mitad de su capacidad, 0.75 no es peor, solo ... diferente (y debería usar menos memoria y tener un rendimiento de iteración notablemente mejor).

Una cosa más que quiero mostrar. Se trata de obtener rendimiento para los tres factores de carga y los diferentes tamaños de HashMap. Constantemente constante con una pequeña variación, excepto por un pico para el factor de carga 1. Realmente me gustaría 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);
  }

}

Muy bien, para dejar esto en reposo, he creado una aplicación de prueba para ejecutar un par de escenarios y obtener algunas visualizaciones de los resultados. Así es como se hacen las pruebas:

• Se han probado varios tamaños de colección diferentes: cien, mil y cien mil entradas.
• Las claves utilizadas son instancias de una clase que se identifican de forma exclusiva mediante un ID. Cada prueba utiliza claves únicas, con números enteros crecientes como ID. El equalsmétodo solo usa el ID, por lo que ninguna asignación de teclas sobrescribe a otra.
• Las claves obtienen un código hash que consiste en el resto del módulo de su ID contra algún 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 el tamaño de nuestra colección es 100, tendremos claves con ID de 0 a 99. Si el límite de hash es 100, cada clave tendrá un código 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 hash con una capacidad inicial de 125.
• El valor de cada clave es simplemente nuevo Object.
• Cada resultado de la 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 medio de las opciones de compra y venta se calcula por 10 opciones de compra.
• Todas las combinaciones de prueba se ejecutan una vez para eliminar la influencia de la compilación 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 llevar un tiempo. Los resultados se imprimen en formato estándar. Puede 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 de visualizador asume que está ejecutando Windows y creará carpetas y archivos en C: \ temp. Cuando corra 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 de colocación promedio (por cada 10 colocaciones) y el tiempo de obtención promedio (por cada 10 obtenciones). Las imágenes son "mapas de calor" bidimensionales que muestran un color por combinación de capacidad inicial y factor de carga.
• Los colores de las imágenes se basan en el tiempo promedio en una escala normalizada del mejor al peor resultado, que va desde el verde saturado al rojo saturado. En otras palabras, el mejor momento será completamente verde, mientras que el peor momento será completamente rojo. Dos medidas de tiempo diferentes nunca deben tener el mismo color.
• Los mapas de color se calculan por separado para las opciones de compra y venta, pero abarcan todas las pruebas para sus respectivas categorías.
• Las visualizaciones muestran la capacidad inicial en su eje x y el factor de carga en el eje y.

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

Poner resultados

Tamaño de la colección: 100. Límite de hash: 50. Esto significa que cada código hash debe aparecer dos veces y todas las demás claves chocan en el mapa hash.

Bueno, eso no empieza 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 muy bien.

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

Este es un escenario un poco más realista, que no tiene una función hash perfecta, pero sigue teniendo una sobrecarga del 10%. El punto de acceso se ha ido, pero la combinación de una capacidad inicial baja con un factor de carga bajo obviamente no funciona.

Tamaño de la colección: 100. Límite de hash: 100. Cada clave tiene 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 más bajo no es necesariamente buena.

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

La esquina inferior izquierda todavía no funciona bien. Pero parece haber una simetría entre la combinación de conteo inicial más bajo / factor de carga alto y conteo inicial más alto / factor de carga bajo.

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

Algo muy divertido está sucediendo con la combinación poco probable de una capacidad inicial que es demasiado baja con un factor de carga superior a 1, lo cual es bastante contrario a la intuición. De lo contrario, sigue siendo bastante simétrico.

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

Tenemos una bonita simetría aquí. La esquina inferior izquierda todavía es subóptima, pero los combos 1000 init capacidad / 1.0 factor de carga versus 1250 init capacidad / 0.75 factor de carga están en el mismo nivel.

Tamaño de la colección: 1000. Límite de hash: 1000. Sin 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 la combinación de una 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. Muy bien, se está poniendo serio ahora, con un tamaño de muestra de cien mil 100 duplicados de código hash por clave.

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

Tamaño de la colección: 100_000. Límite de 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, este. Una colección grande con una sobrecarga de código hash del 1%.

¡Usar el tamaño exacto de la colección como capacidad de inicio con un factor de carga de 1 gana aquí! Sin embargo, las capacidades de inicio un poco más grandes 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 un 50% de espacio adicional con un factor de carga de 1 gana.

Muy bien, eso es todo para los put. Ahora, comprobaremos los get. Recuerde, los mapas a continuación son relativos a los mejores / peores tiempos de obtención, los tiempos de colocación ya no se tienen en cuenta.

Tener resultados

Tamaño de la colección: 100. Límite de hash: 50. Esto significa que cada código hash debería aparecer dos veces y se esperaba que todas las demás claves colisionen en el mapa hash.

Eh ... ¿Qué?

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

¡Vaya, Nelly! Este es el escenario más probable que se correlacione con la pregunta del autor de la pregunta, 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 la colección: 100. Límite de hash: 100. Cada clave tiene su propio código hash único. No se esperan colisiones.

Esto parece 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 de hash: 500. Al igual que en la primera prueba, hay una sobrecarga de hash de 2 a 1, pero ahora con muchas más entradas.

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

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

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

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

Rendimiento decente en todas partes, salvo por la combinación de una alta capacidad inicial con un factor de carga bajo. Esperaría esto para las put, ya que se pueden esperar dos cambios de tamaño de mapa hash. Pero, ¿por qué?

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

Una visualización totalmente espectacular. Esto parece funcionar pase lo que pase.

Tamaño de la colección: 100_000. Límite de hash: 10_000. Volviendo a los 100K nuevamente, con una gran cantidad de superposición de códigos 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 entornos.

Tamaño de la colección: 100_000. Límite de 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 entrecierras los ojos puedes ver una flecha apuntando a la esquina superior derecha.

Tamaño de la colección: 100_000. Límite de hash: 99_000. Buen escenario, este. Una colección grande 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 está empezando a parecerse a los gráficos de Atari? Esto parece favorecer una capacidad inicial exactamente del tamaño de la colección, -25% o + 50%.

Muy bien, es hora de sacar conclusiones ahora ...

• Con respecto a los tiempos de colocación: querrá evitar capacidades iniciales que sean más bajas que el número esperado de entradas de mapas. Si se conoce un número exacto de antemano, ese número o algo ligeramente superior parece funcionar mejor. Los factores de carga altos pueden compensar las capacidades iniciales más bajas debido a cambios de tamaño anteriores del mapa hash. Para capacidades iniciales más altas, no parecen importar mucho.
• Con respecto a los tiempos de obtención: los resultados son un poco caóticos aquí. No hay mucho que concluir. Parece depender mucho de las relaciones sutiles 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 unas buenas que funcionan mal.
• Aparentemente estoy lleno de tonterías cuando se trata de suposiciones sobre el rendimiento de Java. La verdad es que, a menos que esté ajustando perfectamente su configuración a la implementación de HashMap, los resultados van a estar por todas partes. 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 qué orden de tamaño Va a ser.
• Estamos midiendo en nanosegundos aquí. El mejor tiempo promedio por cada 10 put fue 1179 ns y el peor 5105 ns en mi máquina. El mejor tiempo promedio por cada 10 veces 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 tenía en mente el póster original.

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

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 producen exactamente los mismos resultados. Esperaría que al menos la capacidad 1 y la capacidad 10 den peores resultados.

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

Este es el constructor adecuado 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();
}

Solo ve con 101. En realidad, no estoy seguro de que sea necesario, pero no podría valer la pena el esfuerzo para molestarse en averiguarlo con seguridad.

... solo agrega el 1.

EDITAR: Alguna justificación para mi respuesta.

Primero, asumo que tu HashMapno crecerás más allá 100; si es así, debe dejar el factor de carga como está. Del mismo modo, si lo que le preocupa es el rendimiento, deje el factor de carga como está . Si lo que le preocupa es la memoria, puede guardar algo configurando el tamaño estático. Esto podría quizás ser vale la pena si está metiendo un montón de cosas en la memoria; es decir, están almacenando muchos mapas o creando mapas con un tamaño de estrés de espacio de almacenamiento.

En segundo lugar, elijo el valor 101porque ofrece una mejor legibilidad ... si luego miro su código y veo que ha configurado la capacidad inicial 100y lo está cargando con 100elementos, tendré que hacerlo. lea el Javadoc para asegurarse de que no cambiará de tamaño cuando llegue con precisión 100. Por supuesto, no encontraré la respuesta allí, así que tendré que buscar la fuente. Esto no vale la pena ... simplemente déjelo 101y todos estarán contentos y nadie verá el código fuente de java.util.HashMap. ¡Hurra!

En tercer lugar, la afirmación de que establecer la HashMapcapacidad exacta de lo que espera con un factor de carga de 1 " matará su rendimiento de búsqueda e inserción " simplemente no es cierta, incluso si está en negrita.

... si tiene ncubos y asigna nelementos al azar en ncubos, sí, va a terminar con artículos en el mismo cubo, claro ... pero ese no es el fin del mundo ... en la práctica, son solo un par de comparaciones más iguales. De hecho, hay esp. poca diferencia cuando se considera que la alternativa es asignar nelementos en n/0.75contenedores.

No es necesario que confíe 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;
}

Resultados de la prueba:

=======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: ↑ - hay acerca de esto → || ← mucha diferencia entre las diferentes configuraciones .

Con respecto a mi respuesta original (el bit sobre la primera línea horizontal), fue deliberadamente simplista porque en la mayoría de los casos , este tipo de microoptimización no es bueno .

En cuanto a la implementación, Google Guava tiene un método de fábrica conveniente

Maps.newHashMapWithExpectedSize(expectedSize)

Que calcula la capacidad usando la fórmula

capacity = expectedSize / 0.75F + 1.0F

Desde HashMapJavaDoc:

Como regla general, el factor de carga predeterminado (.75) ofrece una buena compensación entre los costos de tiempo y espacio. Los valores más altos disminuyen la sobrecarga de espacio pero aumentan el costo de búsqueda (reflejado en la mayoría de las operaciones de la clase HashMap, incluidas obtener y poner). El número esperado de entradas en el mapa y su factor de carga deben tenerse en cuenta al establecer su capacidad inicial, a fin de minimizar el número de operaciones de refrito. Si la capacidad inicial es mayor que el número máximo de entradas dividido por el factor de carga, nunca se realizarán operaciones de refrito.

Entonces, si espera 100 entradas, quizás un factor de carga de 0,75 y una capacidad inicial de techo (100 / 0,75) sería lo mejor. Eso se reduce a 134.

Debo admitir que no estoy seguro de por qué el costo de búsqueda sería mayor para un factor de carga más alto. El hecho de que HashMap esté más "abarrotado" no significa que se colocarán más objetos en el mismo cubo, ¿verdad? Eso solo depende de su código hash, si no me equivoco. Entonces, asumiendo una distribución de código hash decente, ¿no deberían la mayoría de los casos seguir siendo O (1) independientemente del factor de carga?

EDITAR: Debería leer más antes de publicar ... Por supuesto, el código hash no se puede asignar directamente a algún índice interno. Debe reducirse a un valor que se ajuste a la capacidad actual. Lo que significa que cuanto mayor sea su capacidad inicial, menor puede esperar que sea el número de colisiones de hash. Si elige una capacidad inicial exactamente del tamaño (o +1) de su conjunto de objetos con un factor de carga de 1, se asegurará de que su mapa nunca cambie de tamaño. Sin embargo, matará su rendimiento de búsqueda e inserción. Un cambio de tamaño sigue siendo relativamente rápido y solo podría ocurrir una vez, mientras que las búsquedas se realizan en prácticamente cualquier trabajo relevante con el mapa. Como resultado, optimizar para búsquedas rápidas es lo que realmente desea aquí. Puede combinar eso sin tener que cambiar nunca el tamaño haciendo lo que dice JavaDoc: tome la capacidad requerida, divídala por un factor de carga óptimo (por ejemplo, 0,75) y utilícela como capacidad inicial, con ese factor de carga. Agregue 1 para asegurarse de que el redondeo no lo entienda.