Хорошо, чтобы положить конец этому, я создал тестовое приложение для запуска нескольких сценариев и получения некоторых визуализаций результатов.Вот как выполняются тесты:
- Было опробовано несколько разных размеров коллекции: сто, одна тысяча и сто тысяч записей.
- Используемые ключи являются экземплярамикласс, который уникально идентифицируется идентификатором.Каждый тест использует уникальные ключи с инкрементными целыми числами в качестве идентификаторов.Метод
equals использует только идентификатор, поэтому никакое сопоставление клавиш не перезаписывает другое. - Ключи получают хеш-код, который состоит из остатка модуля от их идентификатора и некоторого предустановленного номера.Мы назовем этот номер пределом хеша .Это позволило мне контролировать количество ожидаемых коллизий хешей.Например, если размер нашей коллекции равен 100, у нас будут ключи с идентификаторами в диапазоне от 0 до 99. Если предел хеш-функции равен 100, у каждого ключа будет уникальный хэш-код.Если предел хеширования равен 50, ключ 0 будет иметь тот же хеш-код, что и ключ 50, 1 будет иметь тот же хеш-код, что и 51 и т. Д. Другими словами, ожидаемое количество коллизий хеш-функции на ключ - это размер коллекции, деленный на хешlimit.
- Для каждой комбинации размера коллекции и ограничения хеша я запустил тест, используя хеш-карты, инициализированные с различными настройками.Эти настройки представляют собой коэффициент загрузки и начальную емкость, которая выражается как коэффициент настройки сбора.Например, тест с размером коллекции 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 init / коэффициент загрузки 1.0 против 1250 init init / коэффициент нагрузки 0,75 находятся на том же уровне.
Размер сбора: 1000. Предел хеша:1000. Никаких дублирующих хеш-кодов, но теперь с размером выборки 1000.
Здесь особо нечего сказать.Комбинация более высокой начальной емкости с коэффициентом загрузки 0,75, кажется, немного превосходит комбинацию из 1000 начальной емкости с коэффициентом нагрузки 1.
Размер сбора: 100_000.Лимит хеша: 10_000.Хорошо, сейчас все серьезно, размер выборки составляет сто тысяч и 100 дубликатов хеш-кода на ключ.
Yikes!Я думаю, что мы нашли наш более низкий спектр.Емкость инициализации, точно равная размеру коллекции с коэффициентом загрузки 1, здесь очень хорошо работает, но кроме этого она повсюду в магазине.
Размер коллекции: 100_000.Предел хеша: 90_000.Немного более реалистично, чем в предыдущем тесте, здесь мы имеем 10% перегрузку в хэш-кодах.
Левый нижний угол все еще нежелателен.Более высокие начальные возможности работают лучше всего.
Размер коллекции: 100_000.Предел хеша: 99_000.Хороший сценарий, это.Большая коллекция с перегрузкой хеш-кода 1%.
Использование точного размера коллекции в качестве емкости инициализации с коэффициентом загрузки 1 выигрывает здесь!Немного большие возможности инициализации работают довольно хорошо.
Размер коллекции: 100_000.Лимит хеша: 100_000.Большая.Самая большая коллекция с идеальной хэш-функцией.
Некоторые удивительные вещи здесь.Начальная вместимость с дополнительным пространством 50% при коэффициенте нагрузки 1 побед.
Хорошо, вот и все для путов.Теперь мы проверим получение.Помните, что все приведенные ниже карты относятся к лучшим / худшим временам получения, время пут больше не учитывается.
Результаты получения
Размер коллекции: 100. Предел хеширования: 50. Это означает, что каждый хэш-код должен встречаться дважды, и каждый другой ключ должен был столкнуться в хэш-карте.
Eh... Что?
Размер коллекции: 100. Предел хеш-функции: 90. У каждого десятого ключа есть повторяющийся хэш-код.
ОооНелли!Это наиболее вероятный сценарий для корреляции с вопросом Аскера, и, по-видимому, начальная емкость 100 с коэффициентом загрузки 1 является одной из худших вещей здесь!Клянусь, я не притворялся.
Размер коллекции: 100. Предел хеш-функции: 100. Каждый ключ имеет свой уникальный хэш-код.Никаких столкновений не ожидается.
Это выглядит немного спокойнее.Практически одинаковые результаты по всем направлениям.
Размер коллекции: 1000. Предел хеш-функции: 500. Как и в первом тесте, есть перегрузка хэш-функции от 2 до 1, но теперь с гораздо большим количеством записей.
Похоже, что любой параметр даст здесь достойный результат.
Размер коллекции: 1000. Предел хеша: 900. Это означает, что один вдесять хеш-кодов появятся дважды.Разумный сценарий в отношении столкновений.
И так же, как и с путами для этой установки, мы получаем аномалию в странном месте.
Размер коллекции: 1000. Лимит хеширования: 990. Некоторые коллизии, но только несколько.Весьма реалистично в этом отношении.
Достойная производительность везде, за исключением комбинации высокой начальной емкости с низким коэффициентом нагрузки.Я ожидаю, что это будет для путов, поскольку можно ожидать изменения размеров двух хэш-карт.Но почему на получение?
Размер коллекции: 1000. Предел хеш-функции: 1000. Нет повторяющихся хеш-кодов, но теперь с размером выборки 1000.
Совершенно не впечатляющая визуализация.Кажется, это работает, несмотря ни на что.
Размер коллекции: 100_000.Лимит хеша: 10_000.Возвращаясь к 100K снова, с большим количеством совпадений хеш-кода.
Это не выглядит красиво, хотя плохие места очень локализованы.Производительность здесь, по-видимому, во многом зависит от определенной синергии между настройками.
Размер коллекции: 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 нс.Это может быть разница в 6 раз, но мы говорим меньше миллисекунды.О коллекциях, которые намного больше, чем предполагалось в оригинальном плакате.
Ну, вот и все.Я надеюсь, что мой код не имеет какой-то ужасной оплошности, которая лишает законной силы все, что я разместил здесь.Это было весело, и я узнал, что в конце концов вы можете положиться на Java, чтобы выполнять свою работу, чем ожидать большой разницы от крошечных оптимизаций.Это не означает, что некоторых вещей не следует избегать, но мы в основном говорим о построении длинных строк в циклах for, использовании неправильных структур данных и создании алгоритмов O (n ^ 3).