java - SparseArray vs HashMap

android sparse-matrix

Question

Puedo pensar en varias razones por las que los HashMap con claves enteras son mucho mejores que SparseArray s:

1. La documentación de Android para un SparseArray dice "generalmente es más lento que un HashMap tradicional".
2. Si escribe código usando HashMap s en lugar de SparseArray , 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 HashMap s en lugar de SparseArray , su código funcionará en proyectos que no sean de Android.
4. El mapa anula equals() y hashCode() mientras que SparseArray no lo hace.

Sin embargo, cada vez que trato de usar un HashMap con claves enteras en un proyecto de Android, IntelliJ me dice que debería usar un SparseArray en SparseArray lugar. Encuentro esto realmente difícil de entender. ¿Alguien sabe alguna razón de peso para usar SparseArray s?

Answer 1

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

Creo que con SparseArray frecuencia solo usamos HashMap para buscar un valor asociado con una clave, mientras que SparseArray es 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 pagas muy poco moviéndolo a otras plataformas (a través de un simple COPY & Paste).

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

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

Otro aspecto importante de SparseArray es que solo utiliza una matriz para almacenar todos los elementos, mientras que HashMap usa la Entry , por lo que SparseArray cuesta una cantidad de memoria significativamente menor que la de un HashMap , vea documentation

Answer 2

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

Es solo una advertencia de esta documentation de su matriz dispersa:

Se pretende que sea más eficiente en cuanto a la memoria que utilizar un HashMap para asignar números enteros a objetos.

SparseArray está SparseArray para ser eficiente en cuanto a la memoria, en comparación con el HashMap normal, es decir, no permite múltiples espacios 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.

Answer 3

¡Mi punto de referencia dice que Sparse tiene la misma velocidad que Hash al agregar y 5! veces más rápido cuando se busca con get (int). Sin embargo, en un escritorio, la velocidad del procesador puede variar.

Answer 4

Después de buscar en Google, intento agregar algo de información a las torres ya publicadas:

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

Hashmap y SparseArray son muy similares para tamaños de estructura de datos por debajo de 1,000

y

cuando el tamaño se ha aumentado a la marca de 10,000, el Hashmap tiene un mayor rendimiento con la adición de objetos, mientras que el SparseArray tiene un mayor rendimiento cuando se recuperan 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 de la clave, el valor y la siguiente entrada. Además, también necesita 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, solo ignora la advertencia.

Answer 5

Es desafortunado que el compilador emita una advertencia. Supongo que HashMap ha sido demasiado utilizado para almacenar elementos.

SparseArrays tiene su lugar. Dado que utilizan un algoritmo de búsqueda binario para encontrar un valor en una matriz, debes tener en cuenta lo que estás haciendo. La búsqueda binaria es O (log n) mientras que la búsqueda hash es O (1). Esto no necesariamente significa que la búsqueda binaria es más lenta para un conjunto dado de datos. Sin embargo, a medida que el número de entradas crece, la potencia de la tabla hash toma el control. De ahí los comentarios donde el bajo número de entradas puede igualar y posiblemente ser 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, por lo que se puede optimizar mejor). También agregaron un hash secundario para asegurarse de que el hash es bueno. También la razón por la que SparseArray funciona realmente bien para relativamente pocas entradas (<100).

Sugeriría que si necesitas una tabla hash y deseas un mejor uso de la memoria para un entero primitivo (no auto boxeo), etc., prueba a trove. ( http://trove.starlight-systems.com - licencia LGPL). (No afiliación con trove, al igual que su biblioteca)

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

Answer 6

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

1. Un mapa se representa internamente como una matriz de listas, donde cada elemento de estas listas es una clave, par de valores. 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 lagunas en estos índices de matrices, de ahí el término matriz "dispersa".

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

Answer 7

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

Crear un SparseArray

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

Un SparseArray asigna enteros a algún Object , por lo que puede reemplazar String en el ejemplo anterior con cualquier otro Object . Si está mapeando enteros con números enteros, utilice 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 claves int no necesitan estar en orden. Esto también se puede usar para cambiar el valor en una tecla int particular.

Eliminar elementos

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

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

El parámetro int es la clave entera.

Valores de búsqueda para una clave int

Use get para obtener el valor de alguna clave entera.

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

Puede usar get(int key, E valueIfKeyNotFound) si quiere evitar obtener null para las teclas faltantes.

Iteramos sobre los artículos

Puede usar keyAt y valueAt index para recorrer la colección porque SparseArray mantiene un índice separado distinto de las claves int .

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.

Answer 8

SparseArray se puede usar para reemplazar HashMap cuando la clave es de tipo primitivo. Existen algunas variantes para diferentes tipos de clave / valor, aunque no todos están disponibles públicamente.

Los beneficios son:

• Libre de asignación
• Sin boxeo

Inconvenientes:

• Generalmente más lento, no indicado para grandes colecciones
• No funcionarán en proyectos que no sean de Android

HashMap puede ser reemplazado por los siguientes:

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 SparseIntArray vs HashMap para 1000 elementos

SparseIntArray:

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

Clase = 12 + 3 * 4 = 24 bytes
Array = 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
Array = 20 + 1000 * 64 = 64024 bytes
Total = 64,136 bytes

Fuente: Memorias de Android de 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 paquete java.lang.instrument contiene algunos métodos útiles para operaciones avanzadas, como comprobar el tamaño de un objeto con getObjectSize (Object objectToSize).

Información adicional está disponible a partir de la documentación oficial de Oracle

Clase = 12 bytes + (n variables de instancia) * 4 bytes
Array = 20 byte + (n elementos) * (tamaño del elemento)
Entrada = 32 bytes + (tamaño del primer elemento) + (tamaño de los elementos 2ns)