Qual é a capacidade ideal e o fator de carga para um HashMap de tamanho fixo?

Estou tentando descobrir a capacidade ideal e o fator de carga para um caso específico. Acho que entendi a essência, mas ainda assim ficaria grato por uma confirmação de alguém com mais conhecimento do que eu. :)

Se eu sei que meu HashMap será preenchido para conter, digamos, 100 objetos e passará a maior parte do tempo com 100 objetos, estou supondo que os valores ideais são capacidade inicial 100 e fator de carga 1? Ou eu preciso de capacidade 101, ou existem outras pegadinhas?

EDIT: OK, reservei algumas horas e fiz alguns testes. Aqui estão os resultados:

• Curiosamente, capacidade, capacidade + 1, capacidade + 2, capacidade-1 e até capacidade-10 produzem exatamente os mesmos resultados. Eu esperaria que pelo menos a capacidade-1 e a capacidade-10 apresentassem resultados piores.
• Usar a capacidade inicial (em vez de usar o valor padrão de 16) dá uma melhoria notável em put () - até 30% mais rápido.
• Usar o fator de carga de 1 fornece desempenho igual para um pequeno número de objetos e melhor desempenho para um número maior de objetos (> 100.000). No entanto, isso não melhora proporcionalmente ao número de objetos; Suspeito que haja um fator adicional que afeta os resultados.
• O desempenho de get () é um pouco diferente para diferentes números de objetos / capacidade, mas embora possa variar ligeiramente de caso para caso, geralmente não é afetado pela capacidade inicial ou fator de carga.

EDIT2: Adicionando alguns gráficos de minha parte também. Aqui está aquele que ilustra a diferença entre o fator de carga 0,75 e 1, nos casos em que inicializo o HashMap e o preencho até sua capacidade total. Na escala y é o tempo em ms (quanto menor, melhor) e a escala x é o tamanho (número de objetos). Como o tamanho muda linearmente, o tempo necessário também cresce linearmente.

Então, vamos ver o que eu tenho. Os dois gráficos a seguir mostram a diferença nos fatores de carga. O primeiro gráfico mostra o que acontece quando o HashMap é preenchido até a capacidade máxima; o fator de carga 0,75 tem pior desempenho devido ao redimensionamento. No entanto, não é sempre pior, e há todos os tipos de solavancos e saltos - acho que GC tem um papel importante nisso. O fator de carga 1,25 tem o mesmo desempenho que 1, portanto, não está incluído no gráfico.

Este gráfico prova que 0,75 foi pior devido ao redimensionamento; se preenchermos o HashMap até a metade da capacidade, 0,75 não é pior, apenas ... diferente (e deve usar menos memória e ter desempenho de iteração notavelmente melhor).

Mais uma coisa que quero mostrar. Isso é obter desempenho para todos os três fatores de carga e diferentes tamanhos de HashMap. Consistentemente constante com uma pequena variação, exceto por um pico para o fator de carga 1. Eu realmente gostaria de saber o que é (provavelmente GC, mas quem sabe).

E aqui está o código para os interessados:

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

}

Tudo bem, para colocar isso de lado, criei um aplicativo de teste para executar alguns cenários e obter algumas visualizações dos resultados. Veja como os testes são feitos:

• Vários tamanhos de coleção diferentes foram testados: cem, mil e cem mil entradas.
• As chaves usadas são instâncias de uma classe que são identificadas exclusivamente por um ID. Cada teste usa chaves exclusivas, com números inteiros incrementais como IDs. O equalsmétodo usa apenas o ID, portanto, nenhum mapeamento de tecla substitui o outro.
• As chaves obtêm um código hash que consiste no restante do módulo de sua ID em relação a algum número predefinido. Chamaremos esse número de limite de hash . Isso me permitiu controlar o número de colisões de hash que seriam esperadas. Por exemplo, se o tamanho de nossa coleção for 100, teremos chaves com IDs variando de 0 a 99. Se o limite de hash for 100, cada chave terá um código hash exclusivo. Se o limite de hash for 50, a chave 0 terá o mesmo código de hash da chave 50, 1 terá o mesmo código de hash de 51 etc. Em outras palavras, o número esperado de colisões de hash por chave é o tamanho da coleção dividido pelo hash limite.
• Para cada combinação de tamanho de coleção e limite de hash, executei o teste usando mapas de hash inicializados com configurações diferentes. Essas configurações são o fator de carga e uma capacidade inicial que é expressa como um fator da configuração de coleta. Por exemplo, um teste com um tamanho de coleção de 100 e um fator de capacidade inicial de 1,25 irá inicializar um mapa hash com uma capacidade inicial de 125.
• O valor de cada chave é simplesmente um novo Object.
• Cada resultado do teste é encapsulado em uma instância de uma classe Result. No final de todos os testes, os resultados são ordenados do pior desempenho geral para o melhor.
• O tempo médio para opções de compra e venda é calculado por 10 opções de venda / busca.
• Todas as combinações de teste são executadas uma vez para eliminar a influência da compilação JIT. Depois disso, os testes são executados para os resultados reais.

Aqui está a aula:

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

        }

    }

}

Executando isso pode demorar um pouco. Os resultados são impressos na saída padrão. Você pode notar que comentei uma linha. Essa linha chama um visualizador que produz representações visuais dos resultados para arquivos PNG. A classe para isso é fornecida abaixo. Se você deseja executá-lo, descomente a linha apropriada no código acima. Esteja avisado: a classe visualizer presume que você está executando no Windows e criará pastas e arquivos em C: \ temp. Ao correr em outra plataforma, ajuste isso.

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

    }

}

A saída visualizada é a seguinte:

• Os testes são divididos primeiro pelo tamanho da coleção e, em seguida, pelo limite de hash.
• Para cada teste, há uma imagem de saída referente ao tempo médio de venda (por 10 opções) e o tempo médio de obtenção (por 10 tentativas). As imagens são "mapas de calor" bidimensionais que mostram uma cor por combinação de capacidade inicial e fator de carga.
• As cores nas imagens são baseadas no tempo médio em uma escala normalizada do melhor ao pior resultado, variando de verde saturado a vermelho saturado. Em outras palavras, o melhor horário será totalmente verde, enquanto o pior horário será totalmente vermelho. Duas medidas de tempo diferentes nunca devem ter a mesma cor.
• Os mapas de cores são calculados separadamente para opções de compra e venda, mas abrangem todos os testes de suas respectivas categorias.
• As visualizações mostram a capacidade inicial no eixo xe o fator de carga no eixo y.

Sem mais delongas, vamos dar uma olhada nos resultados. Vou começar com os resultados das opções de venda.

Coloque os resultados

Tamanho da coleção: 100. Limite de hash: 50. Isso significa que cada código hash deve ocorrer duas vezes e todas as outras chaves colidem no mapa hash.

Bem, isso não começa muito bem. Vemos que há um grande ponto de acesso para uma capacidade inicial 25% acima do tamanho da coleção, com um fator de carga de 1. O canto inferior esquerdo não tem um desempenho muito bom.

Tamanho da coleção: 100. Limite de hash: 90. Uma em cada dez chaves tem um código de hash duplicado.

Este é um cenário um pouco mais realista, sem uma função de hash perfeita, mas ainda com uma sobrecarga de 10%. O ponto de acesso acabou, mas a combinação de uma baixa capacidade inicial com um baixo fator de carga obviamente não funciona.

Tamanho da coleção: 100. Limite de hash: 100. Cada chave como seu próprio código hash exclusivo. Nenhuma colisão é esperada se houver baldes suficientes.

Uma capacidade inicial de 100 com um fator de carga de 1 parece adequada. Surpreendentemente, uma capacidade inicial maior com um fator de carga menor não é necessariamente bom.

Tamanho da coleção: 1000. Limite de hash: 500. Está ficando mais sério aqui, com 1000 entradas. Assim como no primeiro teste, há uma sobrecarga de hash de 2 para 1.

O canto esquerdo inferior ainda não está indo bem. Mas parece haver uma simetria entre a combinação de contagem inicial mais baixa / fator de carga alta e contagem inicial mais alta / fator de carga baixa.

Tamanho da coleção: 1000. Limite de hash: 900. Isso significa que um em cada dez códigos de hash ocorrerá duas vezes. Cenário razoável de colisões.

Há algo muito engraçado acontecendo com a combinação improvável de uma capacidade inicial muito baixa com um fator de carga acima de 1, o que é um tanto contra-intuitivo. Fora isso, ainda é bastante simétrico.

Tamanho da coleção: 1000. Limite de hash: 990. Algumas colisões, mas apenas algumas. Bastante realista a esse respeito.

Temos uma boa simetria aqui. O canto esquerdo inferior ainda está abaixo do ideal, mas os combos capacidade de 1000 init / fator de carga de 1.0 versus capacidade de 1250 init / fator de carga de 0,75 estão no mesmo nível.

Tamanho da coleção: 1000. Limite de hash: 1000. Nenhum código de hash duplicado, mas agora com um tamanho de amostra de 1000.

Não há muito a ser dito aqui. A combinação de uma capacidade inicial mais alta com um fator de carga de 0,75 parece superar ligeiramente a combinação de 1000 capacidade inicial com um fator de carga de 1.

Tamanho da coleção: 100_000. Limite de hash: 10_000. Tudo bem, está ficando sério agora, com um tamanho de amostra de cem mil e 100 duplicatas de código hash por chave.

Caramba! Acho que encontramos nosso espectro inferior. Uma capacidade init exatamente do tamanho da coleção com um fator de carga de 1 está indo muito bem aqui, mas fora isso, está em toda a loja.

Tamanho da coleção: 100_000. Limite de hash: 90_000. Um pouco mais realista do que o teste anterior, aqui temos uma sobrecarga de 10% nos códigos hash.

O canto esquerdo inferior ainda é indesejável. Capacidades iniciais mais altas funcionam melhor.

Tamanho da coleção: 100_000. Limite de hash: 99_000. Bom cenário, isso. Uma grande coleção com uma sobrecarga de código hash de 1%.

Usar o tamanho exato da coleção como capacidade de inicialização com um fator de carga de 1 ganha aqui! Capacidades de inicialização um pouco maiores funcionam muito bem, no entanto.

Tamanho da coleção: 100_000. Limite de hash: 100_000. O grande. A maior coleção com uma função hash perfeita.

Algumas coisas surpreendentes aqui. Uma capacidade inicial com 50% de espaço adicional com uma taxa de ocupação de 1 ganha.

Tudo bem, é isso para os puts. Agora, vamos verificar os ganhos. Lembre-se de que os mapas abaixo são todos relativos aos melhores / piores tempos de obtenção, os tempos de colocação não são mais considerados.

Obter resultados

Tamanho da coleção: 100. Limite de hash: 50. Isso significa que cada código hash deve ocorrer duas vezes e todas as outras chaves devem colidir no mapa hash.

Eh ... O quê?

Tamanho da coleção: 100. Limite de hash: 90. Uma em cada dez chaves tem um código de hash duplicado.

Uau, Nelly! Este é o cenário mais provável de se correlacionar com a pergunta do autor da pergunta e, aparentemente, uma capacidade inicial de 100 com um fator de carga de 1 é uma das piores coisas aqui! Eu juro que não fingi.

Tamanho da coleção: 100. Limite de hash: 100. Cada chave como seu próprio código hash exclusivo. Nenhuma colisão esperada.

Isso parece um pouco mais pacífico. Quase sempre os mesmos resultados em todos os níveis.

Tamanho da coleção: 1000. Limite de hash: 500. Assim como no primeiro teste, há uma sobrecarga de hash de 2 para 1, mas agora com muito mais entradas.

Parece que qualquer configuração produzirá um resultado decente aqui.

Tamanho da coleção: 1000. Limite de hash: 900. Isso significa que um em cada dez códigos de hash ocorrerá duas vezes. Cenário razoável de colisões.

E assim como os puts para esta configuração, temos uma anomalia em um local estranho.

Tamanho da coleção: 1000. Limite de hash: 990. Algumas colisões, mas apenas algumas. Bastante realista a esse respeito.

Desempenho decente em qualquer lugar, exceto pela combinação de uma alta capacidade inicial com um baixo fator de carga. Eu esperaria isso para os puts, já que dois redimensionamentos de mapa de hash podem ser esperados. Mas por quê?

Tamanho da coleção: 1000. Limite de hash: 1000. Nenhum código de hash duplicado, mas agora com um tamanho de amostra de 1000.

Uma visualização totalmente nada espetacular. Isso parece funcionar, não importa o quê.

Tamanho da coleção: 100_000. Limite de hash: 10_000. Indo para 100K novamente, com uma grande quantidade de sobreposição de código hash.

Não parece bonito, embora os pontos ruins sejam muito localizados. O desempenho aqui parece depender muito de uma certa sinergia entre as configurações.

Tamanho da coleção: 100_000. Limite de hash: 90_000. Um pouco mais realista do que o teste anterior, aqui temos uma sobrecarga de 10% nos códigos hash.

Muita variação, embora se você apertar os olhos possa ver uma seta apontando para o canto superior direito.

Tamanho da coleção: 100_000. Limite de hash: 99_000. Bom cenário, isso. Uma grande coleção com uma sobrecarga de código hash de 1%.

Muito caótico. É difícil encontrar muita estrutura aqui.

Tamanho da coleção: 100_000. Limite de hash: 100_000. O grande. A maior coleção com uma função hash perfeita.

Alguém mais acha que isso está começando a se parecer com os gráficos do Atari? Isso parece favorecer uma capacidade inicial exatamente do tamanho da coleção, -25% ou + 50%.

Tudo bem, é hora de conclusões agora ...

• Com relação aos tempos de colocação: você deseja evitar capacidades iniciais que sejam menores do que o número esperado de entradas do mapa. Se um número exato for conhecido de antemão, esse número ou algo um pouco acima parece funcionar melhor. Altos fatores de carga podem compensar capacidades iniciais mais baixas devido a redimensionamentos de mapas de hash anteriores. Para capacidades iniciais mais altas, eles não parecem importar muito.
• Em relação aos tempos de obtenção: os resultados são um pouco caóticos aqui. Não há muito o que concluir. Parece depender muito de proporções sutis entre a sobreposição de código hash, capacidade inicial e fator de carga, com algumas configurações supostamente ruins com bom desempenho e boas configurações com péssimo desempenho.
• Aparentemente, estou cheio de merda quando se trata de suposições sobre o desempenho do Java. A verdade é que, a menos que você esteja ajustando perfeitamente suas configurações para a implementação do HashMap, os resultados estarão em todos os lugares. Se há algo a tirar disso, é que o tamanho inicial padrão de 16 é um pouco estúpido para qualquer coisa, exceto os mapas menores, então use um construtor que define o tamanho inicial se você tiver alguma ideia sobre a ordem de tamanho vai ser.
• Estamos medindo em nanossegundos aqui. O melhor tempo médio por 10 puts foi 1179 ns e o pior 5105 ns na minha máquina. O melhor tempo médio por 10 acertos foi 547 ns e o pior 3484 ns. Isso pode ser uma diferença de fator 6, mas estamos falando em menos de um milissegundo. Em coleções muito maiores do que o pôster original tinha em mente.

Bem, é isso. Espero que meu código não tenha uma supervisão horrível que invalide tudo o que postei aqui. Isso tem sido divertido e eu aprendi que no final você pode muito bem confiar no Java para fazer seu trabalho do que esperar muita diferença em pequenas otimizações. Isso não quer dizer que algumas coisas não devam ser evitadas, mas então estamos falando principalmente sobre a construção de Strings longos em loops for, usando as estruturas de dados erradas e fazendo algoritmos O (n ^ 3).

Este é um tópico muito bom, exceto que há uma coisa crucial que você está perdendo. Você disse:

Curiosamente, capacidade, capacidade + 1, capacidade + 2, capacidade-1 e até capacidade-10 produzem exatamente os mesmos resultados. Eu esperaria que pelo menos a capacidade-1 e a capacidade-10 apresentassem resultados piores.

O código-fonte salta a capacidade inicial para a próxima potência de dois mais alta internamente. Isso significa que, por exemplo, as capacidades iniciais de 513, 600, 700, 800, 900, 1000 e 1024 usarão a mesma capacidade inicial (1024). Isso não invalida o teste feito por @G_H, porém, deve-se perceber que isso está sendo feito antes de analisar seus resultados. E explica o comportamento estranho de alguns dos testes.

Este é o construtor certo para a fonte 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();
}

Apenas vá com 101. Na verdade, não tenho certeza de que seja necessário, mas não vale a pena o esforço para descobrir com certeza.

... basta adicionar o 1.

EDIT: Alguma justificativa para minha resposta.

Em primeiro lugar, estou supondo que você HashMapnão irá além 100; em caso afirmativo, você deve deixar o fator de carga como está. Da mesma forma, se sua preocupação for o desempenho, deixe o fator de carga como está . Se a sua preocupação for a memória, você pode salvar alguns configurando o tamanho estático. Isso pode talvez ser vale a pena fazer se você está colocando um monte de coisas na memória; isto é, estão armazenando muitos mapas ou criando mapas de tamanho estressante do espaço de pilha.

Em segundo lugar, escolho o valor 101porque oferece melhor legibilidade ... se eu olhar seu código depois e ver que você configurou a capacidade inicial para 100e está carregando-o com 100elementos, terei que leia o Javadoc para ter certeza de que ele não será redimensionado quando atingir a precisão 100. Claro, não vou encontrar a resposta lá, então vou ter que olhar para a fonte. Isso não vale a pena ... basta deixá-lo 101e todos ficarão felizes e ninguém olhará o código-fonte do java.util.HashMap. Hoorah.

Terceiro, a afirmação de que definir o HashMappara a capacidade exata do que você espera com um fator de carga de 1 " matará seu desempenho de pesquisa e inserção " simplesmente não é verdadeira, mesmo que esteja em negrito.

... se você tem nbaldes e atribui nitens aleatoriamente a nbaldes, sim, você vai acabar com itens no mesmo balde, claro ... mas isso não é o fim do mundo ... na prática, são apenas mais algumas comparações iguais. Na verdade, há esp. pouca diferença quando você considera que a alternativa é atribuir nitens em n/0.75baldes.

Não há necessidade de acreditar na minha palavra ...

Código de teste rápido:

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

Resultado dos testes:

=======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: ↑ - há sobre isso → || ← muita diferença entre as diferentes configurações .

Com relação à minha resposta original (um pouco acima da primeira linha horizontal), foi deliberadamente superficial porque na maioria dos casos , esse tipo de micro-otimização não é bom .

Em termos de implementação, o Google Guava tem um método de fábrica conveniente

Maps.newHashMapWithExpectedSize(expectedSize)

Que calcula a capacidade usando a fórmula

capacity = expectedSize / 0.75F + 1.0F

Do HashMapJavaDoc:

Como regra geral, o fator de carga padrão (0,75) oferece uma boa compensação entre os custos de tempo e espaço. Valores mais altos diminuem a sobrecarga de espaço, mas aumentam o custo de pesquisa (refletido na maioria das operações da classe HashMap, incluindo get e put). O número esperado de entradas no mapa e seu fator de carga devem ser levados em consideração ao definir sua capacidade inicial, de modo a minimizar o número de operações de rehash. Se a capacidade inicial for maior que o número máximo de entradas dividido pelo fator de carga, nenhuma operação de rehash ocorrerá.

Portanto, se você está esperando 100 entradas, talvez um fator de carga de 0,75 e uma capacidade inicial de teto (100 / 0,75) seja o melhor. Isso se resume a 134.

Tenho que admitir, não sei por que o custo de pesquisa seria maior para uma taxa de ocupação mais alta. Só porque o HashMap está mais "lotado" não significa que mais objetos serão colocados no mesmo intervalo, certo? Isso depende apenas do código hash, se não me engano. Portanto, assumindo uma propagação de código hash decente, a maioria dos casos não deveria ainda ser O (1), independentemente do fator de carga?

EDIT: Eu deveria ler mais antes de postar ... É claro que o código hash não pode mapear diretamente para algum índice interno. Deve ser reduzido a um valor que se ajuste à capacidade atual. O que significa que quanto maior sua capacidade inicial, menor será o número de colisões de hash. Escolher uma capacidade inicial exatamente do tamanho (ou +1) de seu conjunto de objetos com um fator de carga de 1 certamente garantirá que seu mapa nunca seja redimensionado. No entanto, isso vai matar seu desempenho de pesquisa e inserção. Um redimensionamento ainda é relativamente rápido e poderia ocorrer apenas uma vez, enquanto as pesquisas são feitas em praticamente qualquer trabalho relevante com o mapa. Como resultado, otimizar para pesquisas rápidas é o que você realmente deseja aqui. Você pode combinar isso com nunca ter que redimensionar, fazendo como o JavaDoc diz: pegue sua capacidade necessária, divida por um fator de carga ideal (por exemplo, 0,75) e use-o como a capacidade inicial, com esse fator de carga. Adicione 1 para ter certeza de que o arredondamento não vai te pegar