HashSet.низкая производительность в большом сете

Question

Я столкнулся с проблемой, не могу найти решение. Я использую HashSet для хранения значений. Я сохраняю значения пользовательского типа Cycles, где я переопределил HashCode и равняюсь следующему, чтобы убедиться, что медленная производительность не ограничена hascode или аналогичными методами. Также я установил начальную емкость хэширования на 10.000.000

@Override
public int hashCode() {
 final int prime = 31;
 int result = 1;
 result = prime * result + (int) (cycleId ^ (cycleId >>> 32));
 return result;
}

@Override
public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 Cycle other = (Cycle) obj;
 if (cycleId != other.cycleId)
 return false;
 return true;
}

После первых 1.500.000 первых значений, когда я пытаюсь добавить новое значение (с помощью метода add класса HashSet), программа работает очень медленно. В конце концов я получу исключение Java из памяти (исключение в потоке "Thread-0" java.lang.OutOfMemoryError: пространство кучи Java), прежде чем сохраненные значения достигнут 1.600.000

IDE, которую я использую - Eclipse. Поэтому следующим шагом было увеличение размера кучи JVM со значения по умолчанию до 1 гига (с использованием комнадов Xmx1000M и Xms1000M) Теперь elipse запускается с 10-кратным увеличением доступной памяти (я вижу, что в правом нижнем углу, где показана память общего размера кучи и используемая память), но снова у меня та же «медленная» производительность и та же ошибка нехватки памяти ЖЕ ЗНАЧЕНИЯ, как и раньше (после 1.500.000 и до 1.600.000), что очень странно.

Кто-нибудь имеет представление, в чем может быть проблема?

Заранее спасибо

Answer 1

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

Перейдите к Выполнить> Выполнить конфигурации (или Отладочные конфигурации ) и установите Параметры VM там.

Answer 2

Недостаточно кучи памяти (увеличьте ее с помощью -Xmx, например, -Xmx512m). Когда свободной памяти становится очень мало, сборщик мусора тратит много-много времени, который яростно сканирует кучу на предмет недоступных объектов.

Ваш hashCode () в порядке, дополнительные очки за использование всех битов длиной cycleId.

Редактировать . Теперь я видел, как ты увеличил память и не помог. Прежде всего, вы уверены, что удалось увеличить объем памяти? Вы можете проверить это с помощью jconsole, подключиться к вашему приложению и увидеть его размер кучи.

Для проверки альтернативного объяснения, есть ли в вашем cycleId какой-либо конкретный шаблон, который может сделать эту реализацию hashCode () плохой? Мол, его 32 старших разряда в основном похожи на 32 младших разряда. (Да, верно).

Но нет. Даже если бы это было так, вы бы увидели постепенное снижение производительности, а не резкое падение в определенной точке (и вы получите операцию OutOfMemoryError и frenzy gc). Так что моя лучшая догадка - проблема с памятью. Вы либо не увеличили размер кучи, как вы думали , либо какой-то другой код захватывает память в какой-то момент. (Вы можете использовать такой инструмент, как VisualVM, чтобы профилировать это, получить дамп кучи на OOME и посмотреть, какие объекты он содержит).

Edit2 Я выделил жирным шрифтом правильную часть вышеупомянутого.

Answer 3

Тестировали ли вы реализацию hashCode метода?он всегда возвращает 31, для любого значения circleId.Не странно, что ваш HashMap работает медленно, он имеет линейную производительность.

Answer 4

Объем памяти, доступный для приложения, которое вы запускаете из Eclipse, должен быть настроен из меню «Выполнить». Попробуйте:

Выполнить -> Выполнить настройки -> Аргументы -> Аргументы VM -> -Xmx1000M

Причиной медленной работы вашей программы является сборщик мусора - он запускается каждый раз, когда объем памяти выходит за пределы.

Answer 5

JVM выбрасывает «из памяти» НЕ на основе доступной памяти. Это бросается, когда время, потраченное на сборку мусора, слишком много. отметьте это . Точные подробности реализации зависят от JVM и реализации сборщика мусора.

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

Answer 6

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

Answer 7

Я очень разочарован количеством ответов, указывающих ОП увеличить размер его кучи в его приложении. Это не решение - это быстрое и грязное исправление, которое не решит проблему, лежащую в основе.

Я нашел эту презентацию чрезвычайно информативной: http://www.cs.virginia.edu/kim/publicity/pldi09tutorials/memory-efficient-java-tutorial.pdf

В основном на странице указаны минимальные размеры каждого байта, когда он пуст -

ArrayList: 40 or 48
LinkedList: 48
HashMap: 56 or 120
HashSet: 72 or 136

Оказывается, что HashSet практически является HashMap и (нелогично) занимает больше памяти, несмотря на то, что он содержит только значения вместо пар ключ-значение.

Answer 8

Как вы инициализируете свой HashSet?Вы должны знать о его характере роста.При каждой операции add он проверяет, приближается ли он к емкости.Если он достигает определенной точки (определяемой его «коэффициентом нагрузки»), он выполняет операцию изменения размера, которая может быть дорогой.Из JavaDoc (из HashMap - коллекции, которая поддерживает HashSet):

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

Answer 9

Возможно, на вашем компьютере недостаточно памяти, поэтому он должен перейти на диск.