Ответ 1
Хорошо, чтобы положить эту вещь в состояние покоя, я создал тестовое приложение, чтобы запустить несколько сценариев и получить визуализацию результатов. Вот как выполняются тесты:
- Было опробовано несколько разных размеров сбора: сто, одна тысяча и сто тысяч записей.
- Используемые ключи - это экземпляры класса, которые однозначно идентифицируются идентификатором. Каждый тест использует уникальные ключи с добавлением целых чисел в виде идентификаторов. Метод
equalsиспользует только идентификатор, поэтому никакое сопоставление ключей не перезаписывает другой. - Ключи получают хеш-код, который состоит из остатка модуля от их идентификатора к некоторому предварительно установленному номеру. Мы будем называть это число хэш-предел. Это позволило мне контролировать количество столкновений хэшей, которые ожидались. Например, если наш размер коллекции равен 100, у нас будут ключи с идентификаторами от 0 до 99. Если предел хэша 100, каждый ключ будет иметь уникальный хэш-код. Если хэш-предел равен 50, ключ 0 будет иметь тот же хэш-код, что и ключ 50, 1 будет иметь тот же хеш-код, что и 51. Другими словами, ожидаемое количество столкновений хэша на ключ - это размер коллекции, деленный на хэш предел.
- Для каждой комбинации размера коллекции и хэш-лимита я запускаю тест с использованием хеш-карт, инициализированных различными настройками. Эти параметры являются коэффициентом загрузки и начальной мощностью, которая выражается в качестве коэффициента настройки коллекции. Например, тест с размером коллекции 100 и начальным коэффициентом емкости 1,25 инициализирует хэш-карту с начальной емкостью 125.
- Значение для каждого ключа - это просто новый
Object. - Каждый результат теста инкапсулируется в экземпляр класса Result. В конце всех тестов результаты упорядочены от худшей общей производительности до лучших.
- Среднее время для puts и gets рассчитывается на 10 puts/gets.
- Все тестовые комбинации запускаются один раз, чтобы исключить влияние компиляции 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 получает). Изображения представляют собой двумерные "карты тепла", которые показывают цвет за комбинацию начальной емкости и коэффициента загрузки.
- Цвета в изображениях основаны на среднем времени в нормализованном масштабе от наилучшего до наихудшего результата, от насыщенного зеленого до насыщенного красного. Другими словами, лучшее время будет полностью зеленым, а худшее время будет полностью красным. Два разных измерения времени никогда не должны иметь один и тот же цвет.
- Цветовые карты рассчитываются отдельно для puts и gets, но охватывают все тесты для соответствующих категорий.
- Визуализации показывают начальную емкость по оси x и коэффициент нагрузки по оси y.
Без дальнейших церемоний взгляните на результаты. Я начну с результатов для puts.
Положите результаты
Размер коллекции: 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%.
Используя точный размер коллекции как емкость init с коэффициентом загрузки 1 выигрывает здесь! Однако немного большие возможности инициализации работают довольно хорошо.
Размер коллекции: 100_000. Предел хэша: 100_000. Большая. Самая большая коллекция с идеальной хэш-функцией.
Некоторые удивительные вещи здесь. Начальная емкость с 50% дополнительной комнатой при коэффициенте нагрузки 1 побед.
Хорошо, что это для puts. Теперь мы проверим все. Помните, что приведенные ниже карты относятся к лучшим/худшим временам получения, время старта больше не учитывается.
Получить результаты
Размер коллекции: 100. Предел хэша: 50. Это означает, что каждый хеш-код должен появляться дважды, и каждый другой ключ должен был столкнуться на карте хэша.
<Т411 >
Эх... Что?
Размер коллекции: 100. Предел хэша: 90. Один из десяти ключей имеет повторяющийся хеш-код.
Эй, Нелли! Это наиболее вероятный сценарий, который коррелирует с вопросом опроса, и, по-видимому, первоначальная емкость 100 с коэффициентом загрузки 1 - это одна из худших вещей здесь! Клянусь, я не подделал это.
Размер коллекции: 100. Предел хэша: 100. Каждый ключ является его собственным уникальным хэш-кодом. Коллизий не ожидается.
Это выглядит немного спокойнее. В основном те же результаты по всем направлениям.
Размер коллекции: 1000. Предел хэша: 500. Как и в первом тесте, есть хеш-перегрузка от 2 до 1, но теперь с гораздо большим количеством записей.
Похоже, что любая настройка принесет достойный результат.
Размер коллекции: 1000. Предел хеширования: 900. Это означает, что один из десяти хэш-кодов будет повторяться дважды. Разумный сценарий, касающийся столкновений.
И так же, как с помощью puts для этой настройки, мы получаем аномалию в странном месте.
Размер коллекции: 1000. Предел хэша: 990. Некоторые столкновения, но только несколько. В этом отношении вполне реалистично.
Достойная производительность везде, за исключением сочетания высокой начальной емкости с низким коэффициентом нагрузки. Я ожидал бы этого для puts, так как можно было бы ожидать изменения размеров двух хэш-карт. Но почему на получение?
Размер коллекции: 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, чтобы выполнять свою работу, а не рассчитывать на большую разницу между крошечными оптимизациями. Это не означает, что некоторые вещи не следует избегать, но тогда мы в основном говорим о построении длинных строк для циклов, использовании неправильных структур данных и создании алгоритма O (n ^ 3).