Расчет накладных расходов HashMap в Java

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

Как бы я мог выяснить (математически) возможные накладные расходы для этой структуры?

  1. Достаточно ли важно, что, например, если данные внутри будут около 256 МБ, это будет иметь значение для служебных данных?
  2. Есть ли надежный способ (кроме профилировщика, который, как я обнаружил, в некоторых случаях ненадежен) математически рассчитать, какими должны быть его издержки?

Меня не интересует общий размер хеш-карты - только накладные расходы, связанные с использованием хеш-карты. Например, если у меня есть 10 дюймов, это 4 байта за штуку, так что это 40 байтов. Если я вставлю их в массив, я получу постоянную служебную информацию в 12 байтов - 8 для заголовка объекта, 4 для длины. Если я помещу их в другую структуру (например, TreeSet), мои издержки не будут постоянными, потому что дереву нужны узлы - поэтому я мог бы получить накладные расходы, выраженные через n, где n - количество элементов в наборе.

Для меня очевидно несколько вещей, которые я приведу здесь в качестве отправной точки.

  1. Мне нужно будет хранить как минимум 1000 длин. Это обнуляемые типы, поэтому они на самом деле являются объектами. Поэтому я предполагаю, что используемое целое число длиной 8 байтов имеет заголовок объекта также размером 8 байтов. Я добавлю фактор 16n.
  2. Мне также понадобятся ссылки на каждый объект, который должен существовать независимо от того, был ли этот объект извлечен из карты и используется; так что это дополнительные 8 байтов на объект. Вместо этого мы могли бы учесть это в размере данных, но поскольку ссылки находятся в самой хэш-карте, я чувствую, что лучше сделать их частью накладных расходов. Моя логика заключается в следующем: если бы я взял все данные из хэш-карты и сохранил их в переменных, эти n ссылок все равно будут существовать в хеш-карте, если я не удаляю эти объекты данных, что я не буду делать, Набор объектов постоянен, хотя они могут быть переработаны с другим ключом.
  3. Сама хэш-карта содержит 8 байтов.
  4. Хэш-карта должна хранить количество элементов внутри (или я так думаю!), Так что это 4 байта.
  5. Я буду полагать, что по неосведомленности ключи хеша находятся в массиве, отсортированном по порядку ключей хеша. Это 12 байтов для массива.
  6. Я также буду неосознанно предполагать, что объекты находятся в соответствующем массиве, который он разыскивает, когда находит ключ. Я угадаю еще 12 байтов.

Это дает мне полиномиальное уравнение: 36 + 24n

Таким образом, у меня есть предположение о 24036 байтах для 1000 объектов данных с использованием длинных ключей. Это несколько незначительные накладные расходы, но мой вопрос к вам: каковы настоящие накладные расходы, просто сидеть там?

Второстепенный вопрос: насколько это варьируется от JVM до JVM? Есть ли какой-нибудь независимый способ выяснить это? Чтобы проиллюстрировать то, что я имею в виду, рассмотрим JVM, которая имеет только 32-битные заголовки объектов - при рассмотрении массивов вы можете сказать, даже если размер варьируется от JVM до JVM, вполне справедливо предположить, что издержки на массиве станут 8 байтами вместо 12 в этом случае.

Я предполагаю фиксированную реализацию HashMap в той же версии Java.

Я мог бы попытаться прочитать исходный код или запустить профилирование, однако это может привести к вводящим в заблуждение результатам, основанным на моей JVM. Я прошу вашей помощи - возможно, кто-то, кто знает - для некоторой части информации, которую мы оба еще не знаем о ситуации. Спасибо!

Смотрите ответ ниже, фактическая оценка может быть выражена следующим образом:

8 слов на запись, плюс 8 байтов для каждой длинной, плюс 8 байтов для заголовка объекта hashmap.

В моем нынешнем окружении (32-битная ОС) это составляет 1 слово = 4 байта.

  • 40n + 8 в 32-битной среде: ~ 40k на 1000 записей
  • 72n + 8 в 64-битной среде: ~ 72k для 1000 записей.

Так что, кажется, под 100 КБ.

Источник

3 ответа

Решение

Следующее сообщение в блоге дает немного свободной математики по этой теме.
Этот сайт Google Code дает представление о том, как это делается.

Цитирование ссылок в случае гниения ссылок:

This is the cheat-sheet I compiled.

To compute the cost of a single (key, value) entry:

    If you use HashMap or ConcurrentHashMap, the cost is 8 words (32 bytes)


 So, consider this example from the javadoc:

   LoadingCache graphs = CacheBuilder.newBuilder()
       .maximumSize(10000)
       .expireAfterWrite(10, TimeUnit.MINUTES)
       .removalListener(MY_LISTENER)
       .build(
           new CacheLoader() {
             public Graph load(Key key) throws AnyException {
               return createExpensiveGraph(key);
             }
           });


The cost of an Entry in this structure this is computed as follows:

    It's a Cache: +12 words
    It uses maximumSize(): +4 words
    It uses expiration: +4 words

Thus, each (key, value) entry would have a footprint of 20 words (thus 80 bytes in a 32bit VM, or 160 in a 64bit one). 

To estimate the overhead imposed in the garbage collector, one could count how many references (pointers) each entry introduces, which the garbage collector would have to traverse to compute object reachability. The same list again, this time only counting references:

    If you use HashMap or ConcurrentHashMap, the cost is 5 references
Источник

Создайте программу, в которой вы создадите все свои объекты и сохраните их в простом массиве. Измерьте используемую память (см. Runtime).

Затем сохраните их в HashMap. Измерьте использованную память.

Вычтите первую измеренную память во вторую используемую память, и у вас есть накладные расходы на HashMap.

Источник
  1. Достаточно ли важно, что, например, если данные внутри будут около 256 МБ, это будет иметь значение для служебных данных?

Точно нет. Затраты на 1000 объектов в HashMap даже не стоит беспокоиться ни в коем случае: если они составляют 256 МБ каждый, тем более. Если бы издержки были 256 КБ, а это не так, это было бы только 1%. Незначительный.

  1. Есть ли надежный способ (кроме профилировщика, который, как я обнаружил, в некоторых случаях ненадежен) математически рассчитать, какими должны быть его издержки?

Учитывая мой ответ на (1) вопрос спорный.

Источник
Другие вопросы по тегам