Я пытаюсь выяснить оптимальную емкость и коэффициент загрузки для конкретного случая. Я думаю, что я понял суть этого, но я все равно был бы благодарен за подтверждение от кого-то более известного, чем я.:)
Если я знаю, что мой HashMap заполнит, чтобы содержать, скажем, 100 объектов, и будет тратить большую часть времени на 100 объектов, я предполагаю, что оптимальными значениями являются начальная емкость 100 и коэффициент нагрузки 1? Или мне нужна емкость 101, или есть какие-то другие gotchas?
EDIT: Хорошо, я отложил несколько часов и провел некоторое тестирование. Вот результаты:
- Любопытно, что производительность, емкость + 1, емкость + 2, емкость-1 и даже мощность -10 все дают точно такие же результаты. Я ожидал бы, по меньшей мере, емкости-1 и мощности-10, чтобы дать худшие результаты.
- Использование начальной емкости (в отличие от использования значения по умолчанию 16) дает заметное улучшение put() - до 30% быстрее.
- Использование коэффициента загрузки 1 дает равную производительность для небольшого количества объектов и лучшую производительность для большего количества объектов ( > 100000). Однако это не улучшается пропорционально количеству объектов; Я подозреваю, что есть дополнительный фактор, влияющий на результаты. Производительность
- get() немного отличается для различного количества объектов/емкости, но, хотя она может немного меняться от случая к случаю, обычно она не зависит от начальной емкости или коэффициента загрузки.
EDIT2: добавление некоторых графиков с моей стороны. Здесь показан пример разницы между коэффициентом загрузки 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);
}
}