Память наверху Java HashMap по сравнению с ArrayList

Как заметил Джон Скит, это совершенно разные структуры. Карта (например, HashMap) - это отображение одного значения в другое, т. Е. У вас есть ключ, который сопоставляется со значением в виде отношения Key-> Value. Ключ хешируется и помещается в массив для быстрого поиска.

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

edit: на основе вашего комментария я добавил следующую информацию:

Ключ хранится в хэш-карте. Это связано с тем, что не гарантируется, что хэш будет уникальным для любых двух разных элементов. Таким образом, ключ должен быть сохранен в случае коллизий хеширования. Если вы просто хотите увидеть, существует ли элемент в наборе элементов, используйте Set (стандартной реализацией этого является HashSet). Если порядок имеет значение, но вам нужен быстрый поиск, используйте LinkedHashSet, поскольку он сохраняет порядок, в котором были вставлены элементы. Время поиска составляет O (1) для обоих, но время вставки немного больше для LinkedHashSet. Используйте карту только в том случае, если вы фактически сопоставляете одно значение с другим - если у вас просто есть набор уникальных объектов, используйте Set, если у вас есть упорядоченные объекты, используйте List.

Если вы рассматриваете два списка ArrayList против одного Hashmap, это неопределенно; оба являются частично полными структурами данных. Если вы сравнивали Vector с Hashtable, Vector, вероятно, более эффективен с точки зрения памяти, потому что он выделяет только то пространство, которое он использует, тогда как Hashtables выделяет больше места.

Если вам нужна пара ключ-значение, и вы не делаете невероятно голодных по памяти работать, просто используйте Hashmap.

Используйте parseInt ("0x" + строка), чтобы преобразовать строковое значение в числовое

Это означает, что большинство операций ArrayList - это O (1) , но, скорее всего, не те, которые вы бы использовали для поиска объектов, соответствующих определенному значению.

Если вы перебираете каждый элемент в ArrayList и проверяете равенство, или используете contains () , то это означает, что ваша операция выполняется на O (n ) время (или хуже).

Если вы не знакомы с нотацией O (1) или O (n) , это относится к тому, как долго операция будет взять. В этом случае, если вы можете получить постоянную производительность, вы захотите ее взять. Если HashMap. get () is O (1) , это означает, что операции извлечения занимают примерно одинаковое количество времени независимо от количества записей на карте.

Тот факт, что что-то вроде ArrayList.contains () равно O (n) , означает, что количество времени, которое требуется, увеличивается по мере увеличения размера списка; так что итерация через ArrayList с шестью миллионами записей будет совсем неэффективной.

Я не знаю точного числа, но HashMaps намного тяжелее. Сравнивая эти два, внутреннее представление ArrayList самоочевидно, но HashMaps сохраняют объекты Entry (Entry), которые могут увеличивать потребление памяти.

Это не намного больше, но больше. Отличный способ визуализировать это - использовать динамический профилировщик, такой как YourKit , который позволяет вам видеть все распределения кучи. Это довольно мило.

Хэш-карты пытаются поддерживать коэффициент загрузки (обычно 75% заполнения), вы можете думать о хэш-карте как о редко заполненном списке массивов. Проблема при прямом сравнении размеров заключается в том, что коэффициент загрузки карты увеличивается в соответствии с размером данных. ArrayList, с другой стороны, увеличивается для удовлетворения своих потребностей, удваивая размер внутреннего массива. Для относительно небольших размеров они сопоставимы, однако по мере того, как вы упаковываете все больше и больше данных в карту, требуется много пустых ссылок, чтобы поддерживать производительность хеширования.

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

Обновление:

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

Экспериментировал с этим:

NSArray *paths = NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES); 
NSString *documentsDirectory = [paths objectAtIndex:0];

NSString *file = [documentsDirectory stringByAppendingPathComponent:@"binaryData"];

float b = 32.0f;

NSMutableData *data = [NSMutableData dataWithLength:sizeof(float)];
[data appendBytes:&b length:sizeof(float)];
[data writeToFile:file atomically:YES];

NSData *read = [NSData dataWithContentsOfFile:file];
float b2;
NSRange test = {0,4};
[read getBytes:&b2 range:test];

Странно то, что записанный файл имеет размер 8 байтов, а не 4. Можно даже инициализировать nsdata длиной 0, добавить число с плавающей запятой и затем записать, и тогда размер файла будет 4 байта. Почему NSData по умолчанию добавляет 4 байта? NSData длиной 4 должен привести к файлу длиной 4, а не 8.

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

ИЗМЕНИТЬ

После ответа Гранта Уэлча я решил измерить 2 000 000 целых чисел.

Вот ] исходный код

Это результат

$
$javac MemoryUsage.java  
Note: MemoryUsage.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$java -Xms128m -Xmx128m MemoryUsage 
Using ArrayListMemoryUsage@8558d2 size: 0
Total memory: 133.234.688
Initial free: 132.718.608
  Final free: 77.965.488

Used: 54.753.120
Memory Used 41.364.824
ArrayListMemoryUsage@8558d2 size: 2000000
$
$java -Xms128m -Xmx128m MemoryUsage H
Using HashMapMemoryUsage@8558d2 size: 0
Total memory: 133.234.688
Initial free: 124.329.984
  Final free: 4.109.600

Used: 120.220.384
Memory Used 129.108.608
HashMapMemoryUsage@8558d2 size: 2000000

У меня тоже нет ответа, но быстрый поиск в Google обнаружил в Java функцию, которая может помочь.

Runtime.getRuntime (). FreeMemory ();

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

Вам, вероятно, следует сделать это с объемами данных. т.е. начните с 1000, затем с 10000, 100000, 1000000.

РЕДАКТИРОВАТЬ: Исправлено, спасибо amischiefr.

РЕДАКТИРОВАТЬ: Извините за редактирование вашего сообщения, но это очень важно, если вы собираетесь его использовать (и это многовато для комментария) . freeMemory не работает так, как вы думаете. Во-первых, его значение изменяется сборкой мусора. Во-вторых, это значение изменяется, когда java выделяет больше памяти. Использование одного лишь вызова freeMemory не дает полезных данных.

Попробуйте следующее:

public static void displayMemory() {
    Runtime r=Runtime.getRuntime();
    r.gc();
    r.gc(); // YES, you NEED 2!
    System.out.println("Memory Used="+(r.totalMemory()-r.freeMemory()));
}

Или вы можете вернуть использованную память и сохранить ее, а затем сравнить с более поздним значением. В любом случае, запомните 2 gcs и вычитание из totalMemory ().

Опять же, извините за редактирование вашего сообщения!

Все, что хранится в любом из них, - это указатели. В зависимости от вашей архитектуры указатель должен быть 32- или 64-битным (или более или менее)

Список массивов из 10 имеет тенденцию выделять как минимум 10 «указателей» (а также некоторые одноразовые накладные расходы).

Карта должна выделять вдвое больше (20 указателей), потому что одновременно хранит два значения. Кроме того, он должен хранить «хэш». который должен быть больше, чем карта, при загрузке 75% он ДОЛЖЕН иметь около 13 32-битных значений (хэшей).

поэтому, если вы хотите небрежный ответ, соотношение должно быть примерно 1: 3,25 или около того, но вы говорите только о хранилище указателей - очень мало, если вы не храните огромное количество объектов - и если да, то полезность возможности мгновенной ссылки (HashMap) против итерации (массив) должна быть НАМНОГО значительнее, чем размер памяти . Массивы могут соответствовать размеру вашей коллекции. HashMaps тоже может, если вы укажете размер, но если он «вырастет» за пределы этого размера, он перераспределит больший массив и не будет использовать его часть, так что там тоже могут быть небольшие потери.

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

Что стоит за этим вопросом?

По сути, вы должны использовать «правильный инструмент для работы». Поскольку есть разные случаи, когда вам понадобится пара ключ / значение (где вы можете использовать HashMap ), и разные экземпляры, где вам просто понадобится список значений (где вы можете использовать ] ArrayList ), то вопрос о том, «какой из них использует больше памяти», на мой взгляд, спорный, поскольку это не соображение выбора одного перед другим.

Но чтобы ответить на вопрос, поскольку ] HashMap хранит пары ключ / значение, а ArrayList хранит только значения,

Этот пост дает много информации о размерах объектов в Java.