example - map ordenado java

La sobrecarga de memoria de Java HashMap en comparación con ArrayList

Question

Me pregunto cuál es la sobrecarga de memoria de java HashMap en comparación con ArrayList?

Actualizar:

Me gustaría mejorar la velocidad para buscar valores específicos de un paquete grande (6 millones +) de objetos idénticos.

Por lo tanto, estoy pensando en utilizar uno o varios HashMap en lugar de utilizar ArrayList. Pero me pregunto cuál es la sobrecarga de HashMap.

Por lo que yo entiendo, la clave no está almacenada, solo el hash de la clave, por lo que debería ser algo así como el tamaño del hash del objeto + un puntero .

Pero, ¿qué función hash se usa? ¿Es el ofrecido por Object u otro?

Answer 1

Básicamente, debe usar la "herramienta correcta para el trabajo". Dado que hay diferentes instancias en las que necesitará un par de clave / valor (donde puede usar un HashMap ) y diferentes instancias en las que solo necesitará una lista de valores (donde puede usar un ArrayList ), entonces la pregunta de "cuál uno usa más memoria ", en mi opinión, es discutible, ya que no es una consideración de elegir uno sobre el otro.

Pero para responder a la pregunta, dado que HashMap almacena pares clave / valor mientras ArrayList almacena solo valores, supongo que la adición de claves solo al HashMap significaría que requiere más memoria, suponiendo, por supuesto, que los comparemos por el mismo tipo de valor (por ejemplo, donde los valores en ambos son Cadenas).

Answer 2

Como señaló Jon Skeet, estas estructuras son completamente diferentes. Un mapa (como HashMap) es un mapeo de un valor a otro, es decir, tiene una clave que se correlaciona con un valor, en un tipo de relación Clave-> Valor. La clave es hash, y se coloca en una matriz para búsqueda rápida.

Una lista, por otro lado, es una colección de elementos con orden: ArrayList usa una matriz como mecanismo de almacenamiento de fondo, pero eso es irrelevante. Cada elemento indexado es un elemento único en la lista.

editar: basado en su comentario, he agregado la siguiente información:

La clave se almacena en un hashmap. Esto se debe a que no se garantiza que un hash sea único para dos elementos diferentes. Por lo tanto, la clave debe almacenarse en el caso de colisiones hash. Si simplemente desea ver si un elemento existe en un conjunto de elementos, use un conjunto (la implementación estándar de esto es HashSet). Si el pedido es importante, pero necesita una búsqueda rápida, use un LinkedHashSet, ya que mantiene el orden en que se insertaron los elementos. El tiempo de búsqueda es O (1) en ambos, pero el tiempo de inserción es un poco más largo en un LinkedHashSet. Use un Mapa solo si está mapeando de un valor a otro; si solo tiene un conjunto de objetos únicos, use un Conjunto; si tiene objetos ordenados, use una Lista.

Answer 3

Creo que se hace la pregunta incorrecta aquí.

Si desea mejorar la velocidad a la que puede buscar un objeto en una List contiene seis millones de entradas, entonces debe observar qué tan rápido se realizan las operaciones de recuperación de este tipo de datos.

Como de costumbre, los Javadocs para estas clases indican bastante claramente qué tipo de rendimiento ofrecen:

HashMap :

Esta implementación proporciona un rendimiento en tiempo constante para las operaciones básicas (get y put), suponiendo que la función hash dispersa los elementos correctamente entre los cubos.

Esto significa que HashMap.get (clave) es O(1) .

ArrayList :

Las operaciones size, isEmpty, get, set, iterator y listIterator se ejecutan en tiempo constante. La operación de adición se ejecuta en tiempo constante amortizado, es decir, agregar n elementos requiere O (n) tiempo. Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente hablando).

Esto significa que la mayoría de las operaciones de ArrayList son O(1) , pero probablemente no sean las que usaría para encontrar objetos que coincidan con un determinado valor.

Si está iterando sobre cada elemento en ArrayList y prueba la igualdad, o si usa contains() , esto significa que su operación se está ejecutando en el momento O(n) (o peor).

Si no está familiarizado con la notación O(1) u O(n) , esto se refiere a la duración de una operación. En este caso, si puede obtener un rendimiento en tiempo constante, quiere tomarlo. Si HashMap.get() es O(1) esto significa que las operaciones de recuperación tardan aproximadamente la misma cantidad de tiempo, independientemente de cuántas entradas haya en el mapa.

El hecho de que algo como ArrayList.contains() sea O(n) significa que la cantidad de tiempo que toma crece a medida que crece el tamaño de la lista; así que iterar a través de una ArrayList con seis millones de entradas no será muy efectiva en absoluto.

Answer 4

Este site enumera el consumo de memoria para varias estructuras de datos comúnmente utilizadas (y no tan comúnmente). Desde allí se puede ver que el HashMap toma aproximadamente 5 veces el espacio de una ArrayList . El mapa también asignará un objeto adicional por entrada.

Si necesita un orden de iteración predecible y utiliza un LinkedHashMap , el consumo de memoria será aún mayor.

Puede hacer sus propias mediciones de memoria con code.google.com/p/memory-measurer .

Sin embargo, hay dos hechos importantes a tener en cuenta:

1. Muchas estructuras de datos (incluidos ArrayList y HashMap ) sí asignan más espacio del que necesitan actualmente, porque de lo contrario tendrían que ejecutar con frecuencia una costosa operación de cambio de tamaño. Por lo tanto, el consumo de memoria por elemento depende de cuántos elementos hay en la colección. Por ejemplo, una ArrayList con la configuración predeterminada usa la misma memoria para 0 a 10 elementos.
2. Como otros han dicho, las claves del mapa también se almacenan. Entonces, si no están en la memoria de todos modos, también tendrá que agregar el costo de la memoria. Un objeto adicional generalmente tomará solo 8 bytes de sobrecarga, más la memoria para sus campos y posiblemente algo de relleno. Entonces esto también será mucha memoria.

Answer 5

Lo más simple sería mirar la fuente y resolverlo de esa manera. Sin embargo, realmente está comparando manzanas y naranjas; las listas y los mapas son conceptualmente bastante distintos. Es raro que elija entre ellos sobre la base del uso de la memoria.

¿Cuál es el trasfondo detrás de esta pregunta?

Answer 6

Los Hashmaps intentan mantener un factor de carga (generalmente 75% lleno), puede pensar en un hashmap como una lista de matriz escasamente llena. El problema en una comparación directa en el tamaño es que este factor de carga del mapa crece para alcanzar el tamaño de los datos. ArrayList, por otro lado, crece para satisfacer su necesidad duplicando su tamaño de matriz interna. Para tamaños relativamente pequeños, son comparables, sin embargo, a medida que empaca más y más datos en el mapa, se requieren muchas referencias vacías para mantener el rendimiento del hash.

En cualquier caso, recomiendo cebar el tamaño esperado de los datos antes de comenzar a agregar. Esto dará a las implementaciones una configuración inicial mejor y probablemente consuma menos en todos los casos.

Actualizar:

en función de su problema actualizado, consulte listas transparentes . Esta es una pequeña y práctica herramienta escrita por algunos de los empleados de Google para realizar operaciones similares a la que usted describe. También es muy rápido. Permite agrupar, filtrar, buscar, etc.

Answer 7

No sé el número exacto, pero los HashMaps son mucho más pesados. Comparando los dos, la representación interna de ArrayList es evidente, pero los HashMaps retienen los objetos de entrada (Entrada) que pueden aumentar el consumo de memoria.

No es mucho más grande, pero es más grande. Una excelente forma de visualizar esto sería con un generador de perfiles dinámico como YourKit que le permite ver todas las asignaciones de montón. Es muy lindo.

Answer 8

No tengo una respuesta para usted tampoco, pero una búsqueda rápida en Google encontró una función en Java que podría ayudar.

Runtime.getRuntime (). FreeMemory ();

Por lo tanto, propongo que llene un HashMap y un ArrayList con los mismos datos. Registre la memoria libre, elimine el primer objeto, registre la memoria, elimine el segundo objeto, registre la memoria, calcule las diferencias ...

Probablemente deberías hacer esto con magnitudes de datos. es decir, comience con 1000, luego 10000, 100000, 1000000.

EDITAR: corregido, gracias a amischiefr.

EDIT: Perdón por editar tu publicación, pero esto es muy importante si vas a usar esto (y es un poco más para un comentario). freeMemory no funciona como crees que sería. Primero, su valor es cambiado por la recolección de basura. En segundo lugar, su valor se cambia cuando Java asigna más memoria. El solo uso de la llamada freeMemory solo no proporciona datos útiles.

Prueba esto:

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()));
}

O puede devolver la memoria utilizada y almacenarla, luego compararla con un valor posterior. De cualquier forma, recuerda las 2 gcs y resta de TotalMemory ().

Nuevamente, ¡lamento editar tu publicación!

Answer 9

Si está comparando HashMap con ArrayList, supongo que está realizando algún tipo de búsqueda / indexación de ArrayList, como búsqueda binaria o tabla hash personalizada ... Porque un .get (clave) a través de 6 millones de entradas sería inviable utilizando una búsqueda lineal.

Usando esa suposición, he hecho algunas pruebas empíricas y he llegado a la conclusión de que "puedes almacenar 2.5 veces más objetos pequeños en la misma cantidad de RAM si utilizas ArrayList con búsqueda binaria o implementación personalizada de mapas hash, versus HashMap" . Mi prueba se basó en objetos pequeños que contienen solo 3 campos, de los cuales uno es la clave, y la clave es un número entero. Usé un jdk de 32 bits 1.6. Consulte a continuación las advertencias sobre esta figura de "2.5".

Las cosas clave a tener en cuenta son:

(a) no es el espacio requerido para las referencias o el "factor de carga" lo que lo mata, sino la sobrecarga requerida para la creación del objeto. Si la clave es un tipo primitivo, o una combinación de 2 o más valores primitivos o de referencia, cada clave requerirá su propio objeto, que tiene una sobrecarga de 8 bytes.

(b) Según mi experiencia, generalmente necesita la clave como parte del valor (por ejemplo, para almacenar registros de clientes, indexados por ID de cliente, aún desea la ID de cliente como parte del objeto Cliente). Esto significa que es un desperdicio de la OMI que un HashMap almacene por separado referencias a claves y valores.

Advertencias:

1. El tipo más común utilizado para las teclas HashMap es String. La sobrecarga de creación de objeto no se aplica aquí, por lo que la diferencia sería menor.

2. Obtuve una cifra de 2.8, siendo 8880502 entradas insertadas en ArrayList en comparación con 3148004 en HashMap en -Xmx256M JVM, pero mi factor de carga ArrayList era 80% y mis objetos eran bastante pequeños: 12 bytes más 8 bytes de objetos por encima.

3. Mi figura y mi implementación requieren que la clave esté dentro del valor; de lo contrario, tendría el mismo problema con la sobrecarga de creación de objetos y sería solo otra implementación de HashMap.

Mi código:

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 10

Si está considerando dos ArrayLists frente a un Hashmap, es indeterminado; ambas son estructuras de datos parcialmente completas. Si estaba comparando Vector vs Hashtable, Vector probablemente sea más eficiente en cuanto a la memoria, ya que solo asigna el espacio que utiliza, mientras que las Hashtables asignan más espacio.

Si necesita un par clave-valor y no está haciendo un trabajo increíblemente hambriento de memoria, solo use el Hashmap.

Answer 11

Todo lo que está almacenado en cualquiera de ellos es punteros. Dependiendo de su arquitectura, un puntero debe ser de 32 o 64 bits (o más o menos)

Una lista de arreglos de 10 tiende a asignar 10 "Punteros" como mínimo (y también algunos elementos generales de una sola vez).

Un mapa tiene que asignar el doble (20 punteros) porque almacena dos valores a la vez. Luego, además de eso, tiene que almacenar el "Hash". que debería ser más grande que el mapa, con una carga del 75% DEBERÍA estar alrededor de 13 valores de 32 bits (hashes).

así que si quieres una respuesta improvisada, la relación debería ser de aproximadamente 1: 3,25 o menos, pero solo hablas de almacenamiento de puntero, muy pequeño a menos que estés almacenando una gran cantidad de objetos, y si es así, la utilidad de poder hacer referencia instantáneamente (HashMap) vs iterar (matriz) debería ser MUCHO más significativo que el tamaño de la memoria.

Ah, también: las matrices pueden ajustarse al tamaño exacto de tu colección. HashMaps también puede hacerlo si especifica el tamaño, pero si "Crece" más allá de ese tamaño, volverá a asignar una matriz más grande y no usará parte de ella, por lo que puede haber un poco de desperdicio allí también.

Answer 12

Esta publicación proporciona mucha información sobre el tamaño de los objetos en Java.

Answer 13

HashMap contiene una referencia al valor y una referencia a la tecla.

ArrayList solo tiene una referencia al valor.

Entonces, asumiendo que la clave usa la misma memoria del valor, HashMap usa un 50% más de memoria (aunque estrictamente hablando, no es el HashMap quien usa esa memoria porque solo mantiene una referencia a ella)

Por otro lado, HashMap proporciona un rendimiento de tiempo constante para las operaciones básicas (get y put). Por lo tanto, aunque puede usar más memoria, obtener un elemento puede ser mucho más rápido usando un HashMap que un ArrayList.

Entonces, lo siguiente que debes hacer es no preocuparte por quién usa más memoria, pero para qué sirven.

El uso de la estructura de datos correcta para su programa ahorra más CPU / memoria que la forma en que se implementa la biblioteca debajo.

EDITAR

Después de la respuesta de Grant Welch, decidí medir 2,000,000 enteros.

Aquí está el código fuente

Esta es la salida

$
$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