Накладные расходы памяти Java HashMap по сравнению с ArrayList

Ответ 1

Если вы сравниваете HashMap с ArrayList, я предполагаю, что вы делаете какой-то поиск/индексирование ArrayList, например бинарный поиск или пользовательскую хеш-таблицу...? Потому что .get(ключ) через 6 миллионов записей будет невозможно при использовании линейного поиска.

Используя это предположение, я провел некоторые эмпирические тесты и пришел к выводу, что "вы можете хранить в 2,5 раза больше мелких объектов в том же объеме ОЗУ, если вы используете ArrayList с бинарным поиском или пользовательской реализацией хэш-карты, против HashMap". Мой тест был основан на небольших объектах, содержащих только 3 поля, одним из которых является ключ, а ключ - целое. Я использовал 32-битный jdk 1.6. См. Ниже для предостережений на этом рисунке "2.5".

Ключевыми моментами, которые следует отметить, являются:

(a) это не пространство, требуемое для ссылок или "коэффициент загрузки", который убивает вас, а скорее накладные расходы, необходимые для создания объекта. Если ключ является примитивным типом или комбинацией из двух или более примитивных или ссылочных значений, то для каждой клавиши потребуется свой собственный объект, который несет служебные данные из 8 байтов.

(b) По моему опыту вам обычно нужен ключ как часть значения (например, для хранения записей клиентов, индексированных по идентификатору клиента, вы все равно хотите, чтобы идентификатор клиента был частью объекта Customer). Это означает, что IMO несколько расточительно, что HashMap отдельно хранит ссылки на ключи и значения.

Предостережения:

• Наиболее распространенным типом, используемым для ключей HashMap, является String. Накладные расходы на создание объектов здесь не применяются, поэтому разница будет меньше.

• Я получил цифру 2.8, будучи 8880502 записей, вставленных в ArrayList по сравнению с 3148004 в HashMap на -Xmx256M JVM, но мой коэффициент загрузки ArrayList составлял 80%, а мои объекты были довольно маленькими - 12 байтов плюс 8 байтовый объект.

• Моя фигура и моя реализация требуют, чтобы ключ содержался внутри значения, иначе у меня была бы такая же проблема с накладными расходами на объект, и это будет просто еще одна реализация HashMap.

Мой код:

public class Payload {
    int key,b,c;
    Payload(int _key) { key = _key; }
}


import org.junit.Test;

import java.util.HashMap;
import java.util.Map;


public class Overhead {
    @Test
    public void useHashMap()
    {
        int i=0;
        try {
            Map<Integer, Payload> map = new HashMap<Integer, Payload>();
            for (i=0; i < 4000000; i++) {
                int key = (int)(Math.random() * Integer.MAX_VALUE);
                map.put(key, new Payload(key));
            }
        }
        catch (OutOfMemoryError e) {
            System.out.println("Got up to: " + i);
        }
    }

    @Test
    public void useArrayList()
    {
        int i=0;
        try {
            ArrayListMap map = new ArrayListMap();
            for (i=0; i < 9000000; i++) {
                int key = (int)(Math.random() * Integer.MAX_VALUE);
                map.put(key, new Payload(key));
            }
        }
        catch (OutOfMemoryError e) {
            System.out.println("Got up to: " + i);
        }
    }
}


import java.util.ArrayList;


public class ArrayListMap {
    private ArrayList<Payload> map = new ArrayList<Payload>();
    private int[] primes = new int[128];

    static boolean isPrime(int n)
    {
        for (int i=(int)Math.sqrt(n); i >= 2; i--) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    ArrayListMap()
    {
        for (int i=0; i < 11000000; i++)    // this is clumsy, I admit
            map.add(null);
        int n=31;
        for (int i=0; i < 128; i++) {
            while (! isPrime(n))
                n+=2;
            primes[i] = n;
            n += 2;
        }
        System.out.println("Capacity = " + map.size());
    }

    public void put(int key, Payload value)
    {
        int hash = key % map.size();
        int hash2 = primes[key % primes.length];
        if (hash < 0)
            hash += map.size();
        do {
            if (map.get(hash) == null) {
                map.set(hash, value);
                return;
            }
            hash += hash2;
            if (hash >= map.size())
                hash -= map.size();
        } while (true);
    }

    public Payload get(int key)
    {
        int hash = key % map.size();
        int hash2 = primes[key % primes.length];
        if (hash < 0)
            hash += map.size();
        do {
            Payload payload = map.get(hash);
            if (payload == null)
                return null;
            if (payload.key == key)
                return payload;
            hash += hash2;
            if (hash >= map.size())
                hash -= map.size();
        } while (true);
    }
}

Ответ 2

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

Что заслоняет этот вопрос?

Ответ 3

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

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

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

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

О, также: Массивы могут соответствовать размеру вашей коллекции. HashMaps также может быть указан, если вы укажете размер, но если он "поднимется" выше этого размера, он перераспределит более крупный массив и не будет использовать некоторые из них, поэтому там может быть немного отходов.

Ответ 4

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

Runtime.getRuntime() FreeMemory();.

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

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

EDIT: Исправлено, благодаря amischiefr.

EDIT: Извините за редактирование сообщения, но это очень важно, если вы собираетесь использовать это (и это немного для комментария) , 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().

Снова, извините, что редактировал свой пост!

Ответ 5

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

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

Update:

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

Ответ 6

HashMap удерживайте ссылку на значение и ссылку на ключ.

ArrayList просто удерживайте ссылку на значение.

Итак, предполагая, что ключ использует одну и ту же память для значения, HashMap использует на 50% больше памяти (хотя, строго говоря, это не HashMap, который использует эту память, потому что просто сохраняет ссылку на нее)

С другой стороны, HashMap обеспечивает постоянную производительность для основных операций (get and put). Таким образом, хотя он может использовать больше памяти, получение элемента может быть намного быстрее с использованием HashMap, чем ArrayList.

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

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

EDIT

После ответа Grant Welch я решил измерить 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 [email protected] 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
[email protected] size: 2000000
$
$java -Xms128m -Xmx128m MemoryUsage H
Using [email protected] 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
[email protected] size: 2000000

Ответ 7

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

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

Ответ 8

Я думаю, что здесь задают неправильный вопрос.

Если вы хотите улучшить скорость, с которой вы можете искать объект в List, содержащий шесть миллионов записей, тогда вы должны изучить , насколько быстро выполняются эти операции поиска данных.

Как обычно, Javadocs для этих классов довольно четко заявляет, какой тип производительности они предлагают:

HashMap:

Эта реализация обеспечивает постоянную производительность для основных операций (get and put), предполагая, что хеш-функция правильно распределяет элементы среди ковшей.

Это означает, что HashMap.get(ключ) O(1).

ArrayList:

Операции size, isEmpty, get, set, iterator и listIterator выполняются в постоянное время. Операция add работает в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются в линейном времени (грубо говоря).

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

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

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

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

Ответ 9

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

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

Ответ 10

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

Ответ 11

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

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

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

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

Ответ 12

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

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

Ответ 13

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

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

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

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

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