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

Question

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

Обновление:

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

3. Моя фигура и моя реализация требуют, чтобы ключ содержался внутри значения, иначе у меня возникла бы такая же проблема с накладными расходами на создание объекта, и это была бы просто еще одна реализация 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);
    }
}

Answer 2

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

Какая подоплека этого вопроса?

Answer 3

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

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

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

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

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

Answer 4

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

Runtime.getRuntime () FreeMemory ();.

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

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

РЕДАКТИРОВАТЬ: Исправлено, благодаря 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 ().

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

Answer 5

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

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

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

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

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

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

РЕДАКТИРОВАТЬ

После ответа Гранта Уэлча я решил измерить 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

Answer 6

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

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

Обновление:

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

Answer 7

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

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

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

HashMap :

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

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

ArrayList

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

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

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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