Эффективность памяти: HashMap по сравнению с массивом

Question

Я думал о следующей ситуации: хочу подсчитать появление символов в строке (например, для проверки перестановки).

Одним из способов сделать это было бы выделение массива с 256 целыми числами (я предполагаю, что символы UTF-8), чтобы заполнить его нулями, а затем пройти через строку и прирастить целые числа на позициях массива соответствующий значению int символов.

Однако для этого подхода вам придется выделять 256 массивов каждый раз, даже если анализируемая строка очень короткая (и, следовательно, использует только малую часть массива).

Другим подходом было бы использование символа в Integer HashTable и сохранение номера для каждого встреченного символа. Таким образом, у вас будут только ключи для символов, которые на самом деле находятся в строке.

Поскольку мое понимание HashTable довольно теоретично, и я действительно не знаю, как оно реализовано в Java, мой вопрос: какой из двух подходов был бы более эффективным с точки зрения памяти?

Edit:

В ходе обсуждения этого вопроса (спасибо за ответы всем) Я понимаю, что у меня был очень нечеткое понимание природы UTF-8. После некоторого поиска я нашел this great video, что хочу поделиться, если у кого-то такая же проблема.

Answer 1

Ich wonder Почему вы выбираете 256 в качестве длины вашего массива, если предположите, что ваша строка UTF-8. В UTF-8 символ может состоять из 4 байтов, что означает довольно много символов, чем просто 256.

В любом случае: использование HashTable/HashMap требует огромных издержек памяти. Сначала все ваши символы и целое число необходимо обернуть в объект (Integer/Character). И Integer потребляет примерно в 3 раза больше памяти, чем int. Для массивов разница может быть даже больше из-за оптимизации java на массивах (например, стек java работает только в кратных 4 байтах, тогда как в массиве java позволяет меньшим типам, таким как char, потреблять всего 2 байта).

Затем сам HashTable создает накладные расходы памяти, так как он должен поддерживать массив (который обычно не используется полностью) и связанные списки для поддержки всех объектов, которые генерируют один и тот же хэш.

Дополнительно время доступа будет значительно быстрее для массивов. Вы сохраняете несколько вызовов методов (add, hashCode, iterator, ...), и в java-байт-коде существует ряд опкодов, чтобы сделать работу с массивами более эффективной.

В любом случае. Вы задали вопрос:

Какой из двух подходов был бы более эффективным с точки зрения памяти?

И можно с уверенностью сказать, что массивы будут более эффективными с точки зрения памяти.

Однако вы должны абсолютно точно знать, каковы ваши требования. Вам нужна дополнительная эффективность памяти? (Может быть верно, если вы обрабатываете большие объемы данных или находитесь на медленном устройстве (мобильные устройства?)) Насколько важна читаемость кода? Как насчет размера кода? Reuseability?

И ist 256 действительно правильный размер?

Answer 2

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

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

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

Answer 3

Инициализировать массив целых чисел, которые представляют Int значение полукокса, например, INT значение Р 102, который является его ASCII значение

http://www.asciitable.com/

char c = 'f'; 
int x = (int)c; 

Если вы знаете диапазон с тобой, с тобой, это легче.

Для каждого события char приращивание индекса этого символа в массиве на единицу. Этот подход был бы медленным, если вам придется перебирать и усложнять, если вы хотите сортировать, но не будете интенсивными в памяти.

Просто надо знать, когда вы как бы вы потеряете индексы

Answer 4

, не глядя в коде, я знаю, что HashMap требует, как минимум, базовый объект, массив, хеш и отдельные объекты для каждой записи хэш. Как правило, значение int должно храниться как объект Integer, так что это больше объектов.Предположим, у вас есть 30 уникальных персонажей:

• 32 байт для базового объекта
• 256 байт для минимального размера хэш-массива
• 32 байта для каждого из 30 элементов таблицы
• 16 байт (если высоко оптимизирован) для каждого из 30 целых чисел

32 + 256 + 960 + 480 = 1728 bytes. Это для минимальной, непривлекательной реализации.

Массив из 256 тс будет содержать около 1056 байт.

Answer 5

Ну вот факты.

• HashMap использует массив для своей таблицы за кулисами.

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

• HashMap является общим и поэтому использует объекты.

Объекты занимают дополнительное пространство. Насколько я помню, обычно это 8 или 16 байтов в зависимости от того, является ли это 32- или 64-разрядной системой. Это означает, что HashMap вполне может быть меньше, даже если количество символов в String невелико. HashMap потребует 3 дополнительных объекта для каждой записи: Entry, a Character и Integer. HashMap также должен хранить int для индекса локально, а массив - нет.

Это не значит, что с помощью HashMap будет проведено дополнительное вычисление.

Я бы также сказал, что оптимизация пространства не является чем-то, о чем вы должны беспокоиться. В любом случае, объем памяти на самом деле очень мал.