Сколько памяти Java HashSet <Long> следует принимать

Я хотел использовать HashSet<Long> для хранения большого списка уникальных номеров в памяти. Я вычислил предполагаемую потребляемую память (в размере 64-битного указателя):

Long займет 16 байт пространства. Поэтому изначально я умножил число записей с 16, чтобы получить память. Но на самом деле память составляла более 16 байт на запись. После этого я изучил реализацию HashSet. Короче говоря, в основной реализации он фактически хранит дополнительный фиктивный объект (12 байтов) с каждой записью hashset. И указатель (8 байт) на следующую запись. Таким образом, уступают дополнительные 12 + 8 байт на запись.

Таким образом, общая память на запись: 16 + 12 + 8 = 36 байт. Но все же, когда я запускал код и проверял память, он все равно составлял более 36 байт на запись.

Мой вопрос (вкратце): сколько памяти делает HashSet (например, на 64-битной машине)?

Ответ 1

Размер объектов - это деталь реализации. Нет никакой гарантии, что если он x байтов на одной платформе, другой - также x байтов.

Long помещается в коробку, как вы знаете, но 16 байт ошибочно. Примитив Long занимает 8 байтов, но размер блока вокруг Long зависит от реализации. Согласно этот связанный с Hotspot ответ верхние слова и добавление означает, что 4-байтовый int в штучной упаковке может доходить до 24 байтов!

Выравнивание и добавление байт, указанное в этом ответе (Hotspot specific), также будут относиться к объектам Entry, которые также будут подталкивать потребление вверх.

Ответ 2

Вы можете точно измерить этот размер с помощью этого теста:

    long m1 = Runtime.getRuntime().freeMemory();
    // create object (s) here
    long m2 = Runtime.getRuntime().freeMemory();
    System.out.println(m1 - m2);

для запуска с -XX: -UseTLAB опция

На моем 64-битном HotSpot пустой HashSet принимает 480 байтов.

Почему так много? Поскольку HashSet имеет сложную структуру (btw IDE в режиме отладки помогает видеть фактические поля). Он основан на HashMap (шаблон адаптера). Поэтому сам HashSet содержит ссылку на HashMap. HashMap содержит 8 полей. Фактические данные находятся в массиве узлов. A Node имеет: int hash; К ключ; Значение V; Node следующий. HashSet использует только ключи и помещает фиктивный объект в значения.

Ответ 3

Используемая память: 32 * SIZE + 4 * CAPACITY + (16 * SIZE) beign "SIZE" количество элементов.

Ответ 4

Размер по умолчанию HashMap - 16 записей HashMapEntry. Каждый HashMapEntry имеет четыре объекта (int keyHash, Object next, Object key, Object value). Таким образом, он вводит накладные расходы только для того, чтобы иметь пустые записи, обертывая элементы. Кроме того, hashmap имеет скорость расширения 2x, поэтому для 17 элементов у вас будет 32 записи, из которых 15 из них будут пустыми.

Более простой способ - проверить heapdump с помощью анализатора памяти.

Ответ 5

A HashSet - сложный зверь. В верхней части моей головы и после просмотра некоторых комментариев, вот некоторые элементы, которые вы потребляете, которые вы не учитывали:

Коллекции Java (настоящие коллекции, а не простые массивы) могут принимать только ссылки на объекты, а не примитивы. Поэтому ваш примитив long получает коробку в объект java.lang.Long, а ссылка, добавленная к объекту HashSet. Somebody mentioned that a Long`, будет 24 байта. Плюс ссылка, которая составляет 8 байтов.
Ведра хэш-таблицы - это коллекции. Я не помню, являются ли они массивами или ArrayList или LinkedList и т.д., Но поскольку алгоритмы хеширования могут приводить к коллизиям, элементы HashSet должны быть помещены в коллекции, которые организованы хеш-кодом. Лучшим случаем является ArrayList всего с одним элементом: ваш объект long. Размер массива поддержки по умолчанию для ArrayList равен 10, поэтому у вас есть 10 ссылок на объекты внутри объекта, поэтому по меньшей мере 80 байтов теперь за long. Так как long является целым числом, я подозреваю, что алгоритм хеширования делает хорошую работу по распространению вещей. Я не уверен, что произойдет с долгом, значение которого превысило Integer.MAX_VALUE. Это должно было столкнуться как-то из-за парадокса дня рождения.
Фактическая хэш-таблица - HashSet - это в основном HashMap, где значение не интересно. Под капотом создается HashMap, который содержит массив ведер, чтобы представлять хеш-таблицу. Размер массива основан на емкости, которая неясна в зависимости от количества добавленных элементов.
Размер хеш-таблицы обычно, умышленно, имеет больше ковшей, чем необходимо, чтобы облегчить будущий рост. Надеюсь, это не намного больше. Но не ожидайте, что 5 элементов берут ровно 5 ведер.

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