Java: HashSet против HashMap

Question

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

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

Но я пришел, чтобы увидеть использование HashMap довольно расходная память, которая является одной из основных проблем, поэтому я думал, что переход на HashSet будет лучше, потому что он использует только <E>, а не <K,V> на элемент, но когда я посмотрел на реализация, которую я изучил, использует базовый HashMap! это означает, что он не спасет память!

Так что это мои вопросы:

• ли все мои предположения верно?
• Является ли память HashMap расточительной? более конкретно, каковы его накладные расходы для каждой записи?
• Является ли HashSet столь же расточительным, как HashMap?

• Есть ли другие контейнеры на основе хэша, которые будут значительно меньше расходных материалов для памяти?

  обновление

В соответствии с просьбой в комментариях я продлю немного по моей программе, HashMap предназначена для хранения пары других объектов, а также некоторое числовое значения - в float- вычисленный из их. по пути он извлекает некоторые из них и вводит новые пары. Для пары необходимо, чтобы она не удерживала эту пару или удаляла ее. Отображение может быть выполнено с использованием значения float или hashCode парного объекта.

Кроме того, когда я говорю «огромные наборы данных» Я говорю о ~ 4 * 10^9 объектов

Answer 1

ли все мои предположения верно?

Вы правы, что HashSet реализуются с помощью HashMap, так что вы не сбережете память с помощью HashSet вместо этого.

Если вы создаете карты с большим количеством элементов, вы должны построить свои HashMap s с помощью initialCapacity, насколько вам известно, во избежание повторного повторного перехвата (таким образом, перерыв памяти).

Является ли память HashMap расточительной? более конкретно, каковы его накладные расходы для каждой записи?

Нет, это не расточительно. Накладные расходы представляют собой базовый массив (размер изменен loadFactor) и объект Entry для каждой пары значений ключа. Помимо хранения ключа и значения, объект записи также сохраняет указатель на следующую запись в слоте (в случае, если две или более записи занимают один и тот же слот в базовом массиве). По умолчанию loadFactor 0.75 сохраняет размер базового массива на 133% от числа записей.

Очень конкретно, накладные расходы памяти для каждой записи является:

• ссылка на объект ввода для ключа,
• ссылку на объект ввода к значению,
• ссылка на объект ввода для следующего запись,
• и ссылка базового массива на запись (деленная на коэффициент нагрузки).

Очень сложно получить гораздо более аккуратный, чем у хэш-коллекции.

Является ли HashSet столь же расточительным, как HashMap?

Вы не получите никакой эффективности памяти, используя HashSet вместо HashMap.

Есть ли другие контейнеры на основе хэша, которые будут значительно ниже меньше расходных материалов для памяти?

Если ваши ключи примитивов (например int ы), есть пользовательские Map и Set реализации там (в third party libraries), которые используют больше памяти эффективных структур данных.

Answer 2

Есть очень полезные советы по this site о производительности коллекций в java.

HashSet построен на вершине HashMap< T, Object >, где значение является синглтон «присутствует» объект. Это означает, что the memory consumption of aHashSet is identical to HashMap: для хранения значений SIZE вам необходимо 32 * SIZE + 4 * ЕМКОСТЬ байт (плюс размер ваших значений). Это определенно не коллективная память.

THashSet может быть самой простой заменой для HashSet - она ​​реализует Set и Iterable, что означает, что вам нужно просто обновить одну букву при инициализации вашего набора.

THashSet использует один массив объектов для своих значений, поэтому он использует 4 * CAPACITY байт для хранения. Как вы можете видеть, по сравнению с JDK HashSet вы получите save32 * SIZE байт в случае идентичного коэффициента загрузки, что является огромным улучшением.

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

Answer 3

Это правда, что HashSet использует столько же памяти, как HashMap. Разница между ними заключается в том, что HasSet реализует Set, т. Е. Не заботится ни о каком значении, связанном с ключом, а только о наличии или отсутствии его определенного значения. HashMap занимается хранением/извлечением (put/get) значений на ключ.

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

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

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

Кроме того, TreeMap может использоваться по причинам программирования, когда вы либо не можете, либо не хотите создавать пользовательскую реализацию методов equals и hashCode вашего типа ключа. Вместо этого вы можете сделать компаратор для типа ключа. Например, чтобы сделать карту/установить на основе строки без учета регистра, используйте String.CASE_INSENSITIVE_ORDER в качестве компаратора TreeSet