Какова оптимальная емкость и коэффициент загрузки для HashMap фиксированного размера?

Я пытаюсь вычислить оптимальную емкость и коэффициент загрузки для конкретного случая. Думаю, я понял суть, но все же был бы благодарен за подтверждение от кого-то более знающего, чем я. :)

Если я знаю, что моя HashMap заполнится, скажем, 100 объектами, и большую часть времени будет тратить на 100 объектов, я предполагаю, что оптимальными значениями являются начальная емкость 100 и коэффициент загрузки 1? Или мне нужна емкость 101, или есть еще какие-то подводные камни?

РЕДАКТИРОВАТЬ: Хорошо, я выделил несколько часов и провел некоторое тестирование. Вот результаты:

• Любопытно, что емкость, емкость + 1, емкость + 2, емкость-1 и даже емкость-10 дают точно такие же результаты. Я ожидал, что по крайней мере емкость-1 и емкость-10 дадут худшие результаты.
• Использование начальной емкости (в отличие от использования значения по умолчанию 16) дает заметное улучшение работы put () - до 30% быстрее.
• Использование коэффициента загрузки 1 дает одинаковую производительность для небольшого количества объектов и лучшую производительность для большего количества объектов (> 100000). Однако это не улучшается пропорционально количеству объектов; Я подозреваю, что на результаты влияет дополнительный фактор.
• Производительность get () немного отличается для разного количества объектов / емкости, но хотя она может незначительно отличаться от случая к случаю, обычно она не зависит от начальной емкости или коэффициента загрузки.

РЕДАКТИРОВАТЬ2: Добавление некоторых диаграмм с моей стороны. Вот тот, который иллюстрирует разницу между коэффициентом загрузки 0,75 и 1 в случаях, когда я инициализирую HashMap и заполняю его до полной емкости. По шкале y указано время в мс (чем меньше, тем лучше), а по шкале x - размер (количество объектов). Поскольку размер изменяется линейно, необходимое время также линейно растет.

Итак, посмотрим, что у меня получилось. На следующих двух диаграммах показана разница в коэффициентах нагрузки. Первая диаграмма показывает, что происходит, когда HashMap заполнен до отказа; коэффициент загрузки 0,75 хуже из-за изменения размера. Тем не менее, это не всегда хуже, и есть всевозможные неровности и прыжки - я думаю, что GC играет важную роль в этом. Коэффициент нагрузки 1,25 аналогичен 1, поэтому он не включен в таблицу.

Этот график доказывает, что 0,75 было хуже из-за изменения размера; если мы заполним HashMap наполовину, 0,75 не хуже, просто ... по-другому (и он должен использовать меньше памяти и иметь незаметно лучшую производительность итераций).

Еще одна вещь, которую я хочу показать. Это дает производительность для всех трех факторов нагрузки и разных размеров HashMap. Постоянно постоянный с небольшими вариациями, за исключением одного всплеска для коэффициента загрузки 1. Я действительно хотел бы знать, что это такое (возможно, GC, но кто знает).

А вот код для интересующихся:

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

}

Хорошо, чтобы положить этому конец, я создал тестовое приложение, чтобы запустить несколько сценариев и получить визуализацию результатов. Вот как проходят тесты:

• Было опробовано несколько различных размеров коллекций: сто, одна тысяча и сто тысяч записей.
• Используемые ключи - это экземпляры класса, которые однозначно идентифицируются идентификатором. Каждый тест использует уникальные ключи с увеличивающимися целыми числами в качестве идентификаторов. ВequalsМетод использует только идентификатор, поэтому ни одна клавиша отображения не перезаписывает другой.
• Ключи получают хэш-код, который состоит из остатка модуля от их идентификатора против некоторого предустановленного числа. Мы назовем этот номер пределом хеширования . Это позволило мне контролировать количество ожидаемых хеш-коллизий. Например, если размер нашей коллекции равен 100, у нас будут ключи с идентификаторами от 0 до 99. Если предел хеширования равен 100, каждый ключ будет иметь уникальный хеш-код. Если предел хеширования равен 50, ключ 0 будет иметь тот же хэш-код, что и ключ 50, 1 будет иметь тот же хэш-код, что и 51 и т. Д. Другими словами, ожидаемое количество хеш-коллизий на ключ - это размер коллекции, деленный на хэш предел.
• Для каждой комбинации размера коллекции и ограничения хеширования я провел тест с использованием хэш-карт, инициализированных с разными настройками. Эти настройки представляют собой коэффициент загрузки и начальную емкость, которая выражается как коэффициент настройки сбора. Например, тест с размером коллекции 100 и начальным коэффициентом емкости 1,25 инициализирует хэш-карту с начальной емкостью 125.
• Значение для каждого ключа просто новое Object.
• Каждый результат теста инкапсулируется в экземпляр класса Result. В конце всех тестов результаты отсортированы от худшей общей производительности к лучшей.
• Среднее время для пут-получения рассчитывается на каждые 10 пут-приемов.
• Все комбинации тестов запускаются один раз, чтобы исключить влияние JIT-компиляции. После этого запускаются тесты для получения реальных результатов.

Вот класс:

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

        }

    }

}

Это может занять некоторое время. Результаты распечатываются на стандартном носителе. Вы могли заметить, что я закомментировал строку. Эта строка вызывает визуализатор, который выводит визуальные представления результатов в файлы png. Класс для этого приведен ниже. Если вы хотите запустить его, раскомментируйте соответствующую строку в приведенном выше коде. Имейте в виду: класс визуализатора предполагает, что вы работаете в Windows, и создаст папки и файлы в C: \ temp. При работе на другой платформе отрегулируйте это.

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

    }

}

Визуализированный результат выглядит следующим образом:

• Тесты делятся сначала по размеру коллекции, а затем по хеш-пределу.
• Для каждого теста есть выходное изображение, показывающее среднее время размещения (на 10 операций ввода) и среднее время получения (на 10 операций ввода). Изображения представляют собой двухмерные «тепловые карты», которые показывают цвет для каждой комбинации начальной емкости и коэффициента нагрузки.
• Цвета на изображениях основаны на среднем времени по нормализованной шкале от лучшего до худшего результата, в диапазоне от насыщенного зеленого до насыщенного красного. Другими словами, лучшее время будет полностью зеленым, а худшее - полностью красным. Два разных измерения времени никогда не должны иметь одинаковый цвет.
• Цветовые карты рассчитываются отдельно для положительных и отрицательных результатов, но охватывают все тесты для соответствующих категорий.
• Визуализации показывают начальную грузоподъемность по оси x и коэффициент нагрузки по оси y.

Без лишних слов, давайте посмотрим на результаты. Начну с результатов по путам.

Положите результаты

Размер коллекции: 100. Предел хеширования: 50. Это означает, что каждый хеш-код должен повторяться дважды, а все остальные ключи конфликтуют в хэш-карте.

Ну, это начинается не очень хорошо. Мы видим, что есть большая точка доступа для начальной емкости, на 25% превышающей размер коллекции, с коэффициентом загрузки 1. Левый нижний угол работает не очень хорошо.

Размер коллекции: 100. Предел хеширования: 90. Один из десяти ключей имеет повторяющийся хеш-код.

Это немного более реалистичный сценарий, не имеющий идеальной хеш-функции, но все же 10% перегрузки. Точка доступа исчезла, но сочетание низкой начальной емкости с низким коэффициентом загрузки явно не работает.

Размер коллекции: 100. Предел хеширования: 100. Каждый ключ как собственный уникальный хеш-код. Коллизий не ожидается, если ведра достаточно.

Начальная емкость 100 с коэффициентом загрузки 1 кажется прекрасной. Удивительно, но более высокая начальная емкость при более низком коэффициенте нагрузки не всегда хорошо.

Размер коллекции: 1000. Предел хеширования: 500. Здесь становится все серьезнее, с 1000 записей. Как и в первом тесте, есть перегрузка хеша от 2 до 1.

В нижнем левом углу все еще не все в порядке. Но, похоже, существует симметрия между комбинацией меньшего начального количества / высокого коэффициента загрузки и более высокого начального количества / низкого коэффициента загрузки.

Размер коллекции: 1000. Предел хеширования: 900. Это означает, что каждый десятый хэш-код встречается дважды. Разумный сценарий столкновений.

Что-то очень забавное происходит с маловероятной комбинацией начальной емкости, которая слишком мала, с коэффициентом загрузки выше 1, что довольно нелогично. В остальном все еще довольно симметрично.

Размер коллекции: 1000. Ограничение по хешу: 990. Некоторые коллизии, но только некоторые. Вполне реально в этом плане.

У нас здесь хорошая симметрия. Нижний левый угол по-прежнему неоптимален, но комбинация 1000 инициализаций / коэффициент загрузки 1.0 и 1250 инициализаций / коэффициент загрузки 0,75 находятся на том же уровне.

Размер коллекции: 1000. Предел хеширования: 1000. Нет повторяющихся хеш-кодов, но теперь размер выборки составляет 1000.

Здесь особо нечего сказать. Комбинация более высокой начальной емкости с коэффициентом нагрузки 0,75, кажется, немного превосходит комбинацию начальной емкости 1000 с коэффициентом нагрузки 1.

Размер коллекции: 100_000. Предел хеширования: 10_000. Хорошо, сейчас все становится серьезно, с размером выборки сто тысяч и 100 дубликатов хэш-кода на ключ.

Ой! Думаю, мы нашли наш нижний спектр. Емкость инициализации, равная точно размеру коллекции с коэффициентом загрузки 1, здесь очень хорошо работает, но в остальном это повсюду.

Размер коллекции: 100_000. Предел хеширования: 90_000. Немного более реалистично, чем предыдущий тест, здесь у нас 10% перегрузка хэш-кодов.

Левый нижний угол по-прежнему нежелателен. Лучше всего работают более высокие начальные мощности.

Размер коллекции: 100_000. Предел хеширования: 99_000. Хороший сценарий. Большая коллекция с перегрузкой хэш-кода 1%.

Здесь лучше использовать точный размер коллекции в качестве емкости инициализации с коэффициентом загрузки 1! Тем не менее, немного большие возможности инициализации работают достаточно хорошо.

Размер коллекции: 100_000. Предел хеширования: 100_000. Большая. Самая большая коллекция с идеальной хеш-функцией.

Здесь есть кое-что удивительное. Первоначальная мощность с 50% дополнительной комнаты при коэффициенте загрузки 1 побеждает.

Хорошо, это все, что касается пут. А теперь проверим. Помните, что все приведенные ниже карты относятся к лучшему / худшему времени получения, время размещения больше не учитывается.

Получите результат

Размер коллекции: 100. Предел хеширования: 50. Это означает, что каждый хеш-код должен встречаться дважды, и ожидалось, что все остальные ключи будут конфликтовать в хэш-карте.

Эх ... Что?

Размер коллекции: 100. Предел хеширования: 90. Один из десяти ключей имеет повторяющийся хеш-код.

Эй, Нелли! Это наиболее вероятный сценарий, который коррелирует с вопросом автора, и очевидно, что начальная емкость 100 с коэффициентом загрузки 1 - одна из худших вещей здесь! Клянусь, я не притворялся.

Размер коллекции: 100. Предел хеширования: 100. Каждый ключ как собственный уникальный хеш-код. Столкновения не ожидается.

Это выглядит немного более мирным. В основном одинаковые результаты по всем направлениям.

Размер коллекции: 1000. Предел хеширования: 500. Как и в первом тесте, имеется перегрузка хеш-функции от 2 до 1, но теперь с гораздо большим количеством записей.

Похоже, любая настройка здесь даст достойный результат.

Размер коллекции: 1000. Предел хеширования: 900. Это означает, что каждый десятый хэш-код встречается дважды. Разумный сценарий столкновений.

И точно так же, как с путами для этой установки, мы получаем аномалию в странном месте.

Размер коллекции: 1000. Ограничение по хешу: 990. Некоторые коллизии, но только некоторые. Вполне реально в этом плане.

Достойная производительность везде, за исключением комбинации высокой начальной емкости с низким коэффициентом загрузки. Я бы ожидал этого для put, поскольку можно было бы ожидать двух изменений размеров хэш-карты. Но почему на приеме?

Размер коллекции: 1000. Предел хеширования: 1000. Нет повторяющихся хеш-кодов, но теперь размер выборки составляет 1000.

Совершенно не впечатляющая визуализация. Кажется, это работает, несмотря ни на что.

Размер коллекции: 100_000. Предел хеширования: 10_000. Снова возвращаемся к 100К, с большим количеством перекрывающихся хэш-кодов.

Выглядит не очень красиво, хотя плохие места очень локализованы. Производительность здесь, похоже, во многом зависит от определенного взаимодействия между настройками.

Размер коллекции: 100_000. Предел хеширования: 90_000. Немного более реалистично, чем предыдущий тест, здесь у нас 10% перегрузка хэш-кодов.

Большая разница, хотя, если прищуриться, можно увидеть стрелку, указывающую в правый верхний угол.

Размер коллекции: 100_000. Предел хеширования: 99_000. Хороший сценарий. Большая коллекция с перегрузкой хэш-кода 1%.

Очень хаотично. Здесь сложно найти много структуры.

Размер коллекции: 100_000. Предел хеширования: 100_000. Большая. Самая большая коллекция с идеальной хеш-функцией.

Кто-нибудь еще думает, что это начинает выглядеть как графика Atari? Похоже, что это в пользу начальной емкости точно такого же размера коллекции, -25% или + 50%.

Хорошо, теперь пора делать выводы ...

• Что касается времени размещения: вам нужно избегать начальной емкости, которая меньше ожидаемого количества записей на карте. Если заранее известно точное число, лучше всего подходит это число или что-то немного большее. Высокие коэффициенты загрузки могут компенсировать более низкие начальные емкости из-за более раннего изменения размеров хэш-карты. Для более высоких начальных мощностей они, похоже, не имеют большого значения.
• Что касается времени получения: здесь результаты немного хаотичны. Выводить особо нечего. Кажется, что он очень сильно зависит от тонких соотношений между перекрытием хэш-кода, начальной емкостью и коэффициентом загрузки, при этом некоторые предположительно плохие настройки работают хорошо, а хорошие настройки работают ужасно.
• Я, по-видимому, полон чуши, когда дело касается предположений о производительности Java. По правде говоря, если вы не настроите идеально свои настройки для реализации HashMap, результаты будут повсюду. Если есть что-то, что можно вынести из этого, так это то, что начальный размер по умолчанию, равный 16, немного глуп для чего-либо, кроме самых маленьких карт, поэтому используйте конструктор, который устанавливает начальный размер, если у вас есть какое-либо представление о том, какой порядок размера это будет.
• Здесь мы измеряем в наносекундах. Лучшее среднее время на 10 пут было 1179 нс, а худшее - 5105 нс на моей машине. Лучшее среднее время на 10 попыток составило 547 нс, а худшее - 3484 нс. Это может быть разница в шесть раз, но мы говорим меньше миллисекунды. О коллекциях, которые намного больше, чем предполагалось в оригинальном плакате.

Ну вот и все. Я надеюсь, что в моем коде нет какого-то ужасного упущения, которое сводит на нет все, что я здесь опубликовал. Это было весело, и я узнал, что в конце концов вы можете с таким же успехом полагаться на Java в выполнении своей работы, чем ожидать большой разницы от крошечных оптимизаций. Это не означает, что некоторых вещей нельзя избегать, но тогда мы в основном говорим о построении длинных строк в циклах for, использовании неправильных структур данных и создании алгоритма O (n ^ 3).

Это довольно хорошая тема, за исключением того, что вам не хватает одной важной вещи. Вы сказали:

Любопытно, что емкость, емкость + 1, емкость + 2, емкость-1 и даже емкость-10 дают точно такие же результаты. Я ожидал, что по крайней мере емкость-1 и емкость-10 дадут худшие результаты.

Исходный код внутренне перескакивает с начальной емкости на следующую по величине степень двойки. Это означает, что, например, начальные емкости 513, 600, 700, 800, 900, 1000 и 1024 будут использовать одну и ту же начальную емкость (1024). Это не отменяет тестирование, проведенное @G_H, однако следует понимать, что это делается, прежде чем анализировать его результаты. И это действительно объясняет странное поведение некоторых тестов.

Это конструктор исходного кода 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();
}

Просто продолжай 101. На самом деле я не уверен, что это необходимо, но вряд ли стоит потрудиться, чтобы узнать наверняка.

... просто добавьте 1.

РЕДАКТИРОВАТЬ: какое-то оправдание моего ответа.

Во-первых, я предполагаю, что вы HashMapне вырастете дальше 100; если это так, вы должны оставить коэффициент загрузки как есть. Точно так же, если вас беспокоит производительность, оставьте коэффициент загрузки как есть . Если вас беспокоит память, вы можете сэкономить, установив статический размер. Это может возможно быть стоит делать , если вы зубрежки много материала в памяти; т. е. хранят много карт или создают карты размером с размер кучи.

Во-вторых, я выбираю значение, 101потому что оно обеспечивает лучшую читаемость ... если я потом посмотрю на ваш код и вижу, что вы установили начальную емкость 100и загружаете ее 100элементами, мне придется прочтите Javadoc, чтобы убедиться, что он не изменит размер при точном достижении 100. Конечно, я не найду там ответа, поэтому придется поискать в первоисточнике. Это того не стоит ... просто оставьте это, 101и все будут счастливы, и никто не смотрит исходный код java.util.HashMap. Ура.

В-третьих, утверждение о том, что установка HashMapточной емкости того, что вы ожидаете, с коэффициентом загрузки 1 « убьет вашу производительность поиска и вставки » , просто неверно, даже если оно выделено жирным шрифтом.

... если у вас есть nкорзины, и вы случайным образом распределяете nэлементы по nкорзинам, да, вы получите элементы в одном ведре, конечно ... но это еще не конец света ... на практике, это просто еще пара равных сравнений. Фактически, есть особенно. небольшая разница, если учесть, что альтернативой является распределение nэлементов по n/0.75сегментам.

Не надо верить мне на слово ...

Код быстрого тестирования:

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 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: ↑ - об этом → || ← большая разница между разными настройками .

Что касается моего первоначального ответа (бит выше первой горизонтальной линии), он намеренно GLIB , потому что в большинстве случаев , этот тип микро-оптимизации не хорошо .

С точки зрения реализации у Google Guava есть удобный заводской метод

Maps.newHashMapWithExpectedSize(expectedSize)

Что рассчитывает емкость по формуле

capacity = expectedSize / 0.75F + 1.0F

Из HashMapJavaDoc:

Как правило, коэффициент загрузки по умолчанию (0,75) предлагает хороший компромисс между затратами времени и места. Более высокие значения уменьшают накладные расходы на пространство, но увеличивают стоимость поиска (отражается в большинстве операций класса HashMap, включая получение и размещение). Ожидаемое количество записей на карте и ее коэффициент загрузки следует учитывать при настройке ее начальной емкости, чтобы минимизировать количество операций повторного хеширования. Если начальная емкость больше, чем максимальное количество записей, разделенное на коэффициент загрузки, никаких операций повторного хеширования не произойдет.

Так что, если вы ожидаете 100 записей, возможно, лучше всего подойдет коэффициент загрузки 0,75 и начальная емкость потолка (100 / 0,75). Получается 134.

Должен признать, я не уверен, почему стоимость поиска будет выше при более высоком коэффициенте загрузки. Тот факт, что HashMap более "переполнен", не означает, что в одну корзину будет помещено больше объектов, верно? Это зависит только от их хэш-кода, если я не ошибаюсь. Итак, предполагая приличный разброс хэш-кода, разве в большинстве случаев не должно быть O (1) независимо от коэффициента загрузки?

РЕДАКТИРОВАТЬ: я должен прочитать больше перед публикацией ... Конечно, хеш-код не может напрямую отображаться на некоторый внутренний индекс. Его необходимо уменьшить до значения, соответствующего текущей мощности. Это означает, что чем больше ваша начальная емкость, тем меньшее количество хэш-коллизий вы можете ожидать. Выбор начальной емкости точно такой же, как размер (или +1) вашего объекта, установленного с коэффициентом загрузки 1, действительно гарантирует, что размер вашей карты никогда не будет изменен. Однако это убьет вашу производительность поиска и вставки.. Изменение размера по-прежнему происходит относительно быстро и может произойти только один раз, в то время как поиск выполняется практически для любой соответствующей работы с картой. В результате оптимизация для быстрого поиска - вот что вам действительно нужно. Вы можете совместить это с отсутствием необходимости изменять размер, сделав так, как говорит JavaDoc: возьмите требуемую емкость, разделите ее на оптимальный коэффициент загрузки (например, 0,75) и используйте ее в качестве начальной емкости с этим коэффициентом загрузки. Добавьте 1, чтобы избежать округления.