SparseArray vs HashMap

177

Puedo pensar en varias razones por las cuales HashMaps con teclas enteras son mucho mejores que SparseArrays:

  1. La documentación de Android para un SparseArraydice "Generalmente es más lento que un tradicional HashMap".
  2. Si escribe código usando HashMaps en lugar de SparseArrays, su código funcionará con otras implementaciones de Map y podrá usar todas las API de Java diseñadas para Maps.
  3. Si escribe código usando HashMaps en lugar de SparseArrays, su código funcionará en proyectos que no sean de Android.
  4. El mapa anula equals()y hashCode()mientras SparseArrayque no.

Sin embargo, cada vez que intento usar un HashMapcon teclas enteras en un proyecto de Android, IntelliJ me dice que debería usar un SparseArrayen su lugar. Encuentro esto realmente difícil de entender. ¿Alguien sabe alguna razón convincente para usar SparseArrays?

Paul Boddington
fuente

Respuestas:

235

SparseArrayse puede usar para reemplazar HashMapcuando la clave es un tipo primitivo. Existen algunas variantes para diferentes tipos de clave / valor, aunque no todas están disponibles públicamente.

Los beneficios son:

  • Libre de asignación
  • No boxeo

Inconvenientes:

  • Generalmente más lento, no indicado para grandes colecciones
  • No funcionarán en un proyecto que no sea Android

HashMap puede ser reemplazado por lo siguiente:

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>   //this is not a public class                                 
                                    //but can be copied from  Android source code 

En términos de memoria, aquí hay un ejemplo de SparseIntArrayvs HashMap<Integer, Integer>para 1000 elementos:

SparseIntArray:

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

Clase = 12 + 3 * 4 = 24 bytes
Matriz = 20 + 1000 * 4 = 4024 bytes
Total = 8,072 bytes

HashMap:

class HashMap<K, V> {
    Entry<K, V>[] table;
    Entry<K, V> forNull;
    int size;
    int modCount;
    int threshold;
    Set<K> keys
    Set<Entry<K, V>> entries;
    Collection<V> values;
}

Clase = 12 + 8 * 4 = 48 bytes
Entrada = 32 + 16 + 16 = 64 bytes
Matriz = 20 + 1000 * 64 = 64024 bytes
Total = 64,136 bytes

Fuente: Android Memories por Romain Guy de la diapositiva 90.

Los números anteriores son la cantidad de memoria (en bytes) asignada en el montón por JVM. Pueden variar según la JVM específica utilizada.

El java.lang.instrumentpaquete contiene algunos métodos útiles para operaciones avanzadas como verificar el tamaño de un objeto con getObjectSize(Object objectToSize).

Hay información adicional disponible en la documentación oficial de Oracle .

Clase = 12 bytes + (n variables de instancia) * 4 bytes
Matriz = 20 bytes + (n elementos) * (tamaño del elemento)
Entrada = 32 bytes + (tamaño del primer elemento) + (tamaño del segundo elemento)

Sarpe
fuente
15
¿Alguien puede guiarme de dónde provienen esos "12 + 3 * 4" y "20 + 1000 * 4"?
Marian Paździoch
55
@ MarianPaździoch, mostró una presentación ( speakerdeck.com/romainguy/android-memories ) donde una clase ocupa 12 bytes + 3 variables de 4 bytes, una matriz (referencia) ocupa 20 bytes (dlmalloc - 4, sobrecarga del objeto - 8, ancho y relleno) - 8).
CoolMind
1
Para el registro, otra desventaja clave de SparseArray es que, como objeto de Android, debe ser objeto de burla para las pruebas unitarias. Siempre que sea posible, ahora uso los propios objetos de Java para simplificar las pruebas.
David G
@DavidG Simplemente puede usar el complemento de desmontaje para burlarse de las dependencias de Android.
tormenta de nieve
1
Incluso si no está utilizando Android, copiar la clase a su proyecto no es difícil, solo depende de otras 3 clases. La licencia APL significa que está bien hacerlo, independientemente de la licencia con la que esté trabajando.
Yann TM
35

Vine aquí solo queriendo un ejemplo de cómo usar SparseArray. Esta es una respuesta suplementaria para eso.

Crear una matriz dispersa

SparseArray<String> sparseArray = new SparseArray<>();

A SparseArrayasigna números enteros a algunos Object, por lo que podría reemplazarlos Stringen el ejemplo anterior con cualquier otro Object. Si está asignando enteros a enteros, use SparseIntArray.

Agregar o actualizar elementos

Use put(o append) para agregar elementos a la matriz.

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

Tenga en cuenta que las intclaves no necesitan estar en orden. Esto también se puede usar para cambiar el valor en una intclave particular .

Eliminar elementos

Use remove(o delete) para eliminar elementos de la matriz.

sparseArray.remove(17); // "pig" removed

El intparámetro es la clave entera.

Valores de búsqueda para una clave int

Use getpara obtener el valor de alguna clave entera.

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

Puede usarlo get(int key, E valueIfKeyNotFound)si desea evitar nulllas claves faltantes.

Iterar sobre los artículos

Puede usar keyAty valueAtalgún índice para recorrer la colección porque SparseArraymantiene un índice separado distinto de las intclaves.

int size = sparseArray.size();
for (int i = 0; i < size; i++) {

    int key = sparseArray.keyAt(i);
    String value = sparseArray.valueAt(i);

    Log.i("TAG", "key: " + key + " value: " + value);
}

// key: 1 value: camel
// key: 3 value: cow
// key: 10 value: horse
// key: 30 value: goat
// key: 99 value: sheep

Tenga en cuenta que las claves se ordenan en valor ascendente, no en el orden en que se agregaron.

Suragch
fuente
18

Sin embargo, cada vez que intento usar un HashMap con teclas enteras en un proyecto de Android, intelliJ me dice que debería usar un SparseArray en su lugar.

Es solo una advertencia de esta documentación de su matriz dispersa:

Se pretende que sea más eficiente en la memoria que usar un HashMap para asignar enteros a objetos

El SparseArrayestá hecho para ser eficiente de la memoria que el uso de la HashMap regular, que es no permitir que múltiples lagunas dentro de la matriz no como HashMap. No hay nada de qué preocuparse, puede usar el HashMap tradicional si no desea preocuparse por la asignación de memoria al dispositivo.

Rod_Algonquin
fuente
55
Los puntos sobre el ahorro de memoria son obviamente válidos, pero nunca he entendido por qué Android no podría haber hecho que SparseArray <T> implemente Map <Integer, T> para que obtenga una implementación de Map eficiente en memoria: lo mejor de ambos mundos.
Paul Boddington
3
@PaulBoddington también recuerda que SparseArrayevita que el entero clave sea Auto box, que es otra operación y rendimiento de costos. en lugar de Map, autoboxeará el entero primitivo paraInteger
Rod_Algonquin
También es cierto, pero si hubieran sobrecargado el método put al incluir uno con put de firma (int a, T t), aún podría poner pares clave-valor en el mapa sin que las claves se encuadren automáticamente. Simplemente creo que el Framework de Colecciones es tan poderoso (una de las mejores razones para usar Java) que es una locura no aprovecharlo.
Paul Boddington
66
@PaulBoddington Las colecciones se basan en objetos que no son primitivos, por lo que no funcionará dentro de la API de colecciones
Rod_Algonquin
10

Una matriz dispersa en Java es una estructura de datos que asigna claves a valores. La misma idea que un mapa, pero implementación diferente:

  1. Un mapa se representa internamente como una matriz de listas, donde cada elemento en estas listas es un par clave, valor. Tanto la clave como el valor son instancias de objeto.

  2. Una matriz dispersa se compone simplemente de dos matrices: una matriz de claves (primitivas) y una matriz de valores (objetos). Puede haber huecos en estos índices de matrices, de ahí el término matriz "dispersa".

El interés principal de SparseArray es que ahorra memoria al usar primitivas en lugar de objetos como clave.

Ganesh Katikar
fuente
10

Después de buscar en Google, trato de agregar información a las respuestas ya publicadas:

Isaac Taylor hizo una comparación de rendimiento para SparseArrays y Hashmaps. Él dice que

Hashmap y SparseArray son muy similares para estructuras de datos de menos de 1,000

y

cuando el tamaño se ha incrementado a la marca de 10,000, [...] el Hashmap tiene un mayor rendimiento al agregar objetos, mientras que el SparseArray tiene un mayor rendimiento al recuperar objetos. [...] Con un tamaño de 100,000 [...] el Hashmap pierde rendimiento muy rápidamente

Una comparación en Edgblog muestra que un SparseArray necesita mucha menos memoria que un HashMap debido a la clave más pequeña (int vs Integer) y al hecho de que

una instancia de HashMap.Entry debe realizar un seguimiento de las referencias para la clave, el valor y la siguiente entrada. Además, también debe almacenar el hash de la entrada como int.

Como conclusión, diría que la diferencia podría importar si va a almacenar una gran cantidad de datos en su Mapa. De lo contrario, simplemente ignore la advertencia.

Sebastian
fuente
4

La documentación de Android para un SparseArray dice "Generalmente es más lento que un HashMap tradicional".

Si, es correcto. Pero cuando solo tiene 10 o 20 elementos, la diferencia de rendimiento debe ser insignificante.

Si escribe código utilizando HashMaps en lugar de SparseArrays, su código funcionará con otras implementaciones de Map y podrá utilizar todas las API de Java diseñadas para Maps

Creo que la mayoría de las veces solo usamos HashMappara buscar un valor asociado con una clave, mientras que SparseArrayes realmente bueno en esto.

Si escribe código usando HashMaps en lugar de SparseArrays, su código funcionará en proyectos que no sean de Android.

El código fuente de SparseArray es bastante simple y fácil de entender, de modo que solo paga poco esfuerzo al moverlo a otras plataformas (a través de una simple COPIAR y pegar).

El mapa anula equals () y hashCode () mientras que SparseArray no

Todo lo que puedo decir es, (a la mayoría de los desarrolladores) a quién le importa?

Otro aspecto importante SparseArrayes que solo usa una matriz para almacenar todos los elementos mientras los HashMapusa Entry, por lo que SparseArraycuesta significativamente menos memoria que a HashMap, vea esto

Suitianshi
fuente
1

Es lamentable que el compilador emita una advertencia. Supongo que HashMap ha sido usado en exceso para almacenar elementos.

Los SparseArrays tienen su lugar. Dado que usan un algoritmo de búsqueda binario para encontrar un valor en una matriz, debe considerar lo que está haciendo. La búsqueda binaria es O (log n) mientras que la búsqueda hash es O (1). Esto no significa necesariamente que la búsqueda binaria sea más lenta para un conjunto de datos dado. Sin embargo, a medida que aumenta el número de entradas, el poder de la tabla hash se hace cargo. De ahí los comentarios en los que un número bajo de entradas puede ser igual y posiblemente mejor que usar un HashMap.

Un HashMap es tan bueno como el hash y también puede verse afectado por el factor de carga (creo que en versiones posteriores ignoran el factor de carga para que pueda optimizarse mejor). También agregaron un hash secundario para asegurarse de que el hash sea bueno. También la razón por la que SparseArray funciona realmente bien para relativamente pocas entradas (<100).

Sugeriría que si necesita una tabla hash y desea un mejor uso de la memoria para un entero primitivo (sin boxeo automático), etc., pruebe tesoro. ( http://trove.starlight-systems.com - licencia LGPL). (Sin afiliación a trove, al igual que su biblioteca)

Con el edificio simplificado multi-dex que tenemos, ni siquiera necesita reempacar el tesoro para lo que necesita. (el tesoro tiene muchas clases)

Bruce
fuente