Затраты памяти на Java HashMap по сравнению с ArrayList

Question

Мне интересно, какова нагрузка на память в Java HashMap по сравнению с ArrayList?

Обновление:

Я бы хотел улучшить скорость поиска определенных значений большой пачки (6 миллионов +) идентичных объектов.

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

Насколько я понимаю, ключ не хранится, только хеш ключа, поэтому он должен быть примерно таким: размер хеша объекта + один указатель .

Но какая хеш-функция используется? Это тот, который предлагает Объект или другой?

Answer 1

Этот сайт отображает потребление памяти для нескольких часто используемых (и не очень) используемых структур данных. Отсюда видно, что HashMap занимает примерно в 5 раз больше, чем ArrayList. На карте также будет выделен один дополнительный объект для каждой записи.

Если вам нужен предсказуемый порядок итераций и вы используете LinkedHashMap, потребление памяти будет еще выше.

Вы можете выполнять свои собственные измерения памяти с помощью Memory Measurer .

Однако следует отметить два важных факта:

1. Множество структур данных (включая ArrayList и HashMap) действительно выделяют пространство больше места, чем им нужно в настоящее время, потому что в противном случае им пришлось бы часто выполнять дорогостоящую операцию изменения размера. Таким образом, потребление памяти на элемент зависит от количества элементов в коллекции. Например, ArrayList с настройками по умолчанию использует ту же память для 0-10 элементов.
2. Как уже говорили другие, ключи карты также хранятся. Так что, если они все равно не находятся в памяти, вам также придется добавить эту стоимость памяти. Дополнительный объект обычно занимает 8 байтов только служебной информации, плюс память для его полей и, возможно, некоторое заполнение. Так что это тоже будет много памяти.

Answer 2

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

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

Answer 3

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

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

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

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