SparseArray vs HashMap
Puedo pensar en varias razones por las que HashMap
s con claves enteras son mucho mejores que SparseArray
:
- La documentación de Android para un
SparseArray
dice que "es generalmente más lento que unHashMap
tradicional". - Si escribe código usando
HashMap
s en lugar deSparseArray
s su código funcionará con otras implementaciones de Map y podrá usar todas las API de Java diseñadas para Maps. - Si escribe código usando
HashMap
s en lugar deSparseArray
s su código funcionará en proyectos no-android. - Mapa
hashCode()
equals()
yhashCode()
mientras queSparseArray
no.
Sin embargo, cada vez que intento utilizar un HashMap
con claves enteras en un proyecto de Android, IntelliJ me dice que debo usar un SparseArray
en SparseArray
lugar. Encuentro esto realmente difícil de entender. ¿Alguien sabe alguna razón de peso para usar SparseArray
?
Las matrices dispersas se pueden usar para reemplazar los mapas hash cuando la clave es un tipo primitivo. Hay algunas variantes para diferentes tipos de clave / valor, aunque no todos están disponibles públicamente.
Los beneficios son:
- Sin asignación
- Sin boxeo
Inconvenientes:
- Generalmente más lento, no indicado para grandes colecciones
- No funcionarán en proyectos no androides
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í es 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: Android Memories de Romain Guy de la diapositiva 90.
Los números anteriores son la cantidad de memoria (en bytes) asignada en montón por JVM. Pueden variar dependiendo de la JVM específica utilizada.
El paquete java.lang.instrument contiene algunos métodos útiles para operaciones avanzadas como verificar el tamaño de un objeto con getObjectSize (Object objectToSize).
Hay más información disponible en la documentación oficial de Oracle
Clase = 12 byte + (n variables de instancia) * 4 byte
Array = 20 byte + (n elementos) * (tamaño del elemento)
Entrada = 32 byte + (1 ° elemento) + (2ns tamaño de los elementos)
Sin embargo, cada vez que intento utilizar un HashMap con claves enteras en un proyecto de android, intelliJ me dice que debo usar un SparseArray en su lugar.
Es sólo una advertencia de esta documentación de su matriz dispersa:
Se pretende que sea más eficiente de memoria que usar un HashMap para asignar números enteros a objetos
El SparseArray
se hace para ser eficiente de la memoria que usar el HashMap regular, que es no permite las aberturas múltiples dentro del arsenal 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.
Una matriz dispersa en Java es una estructura de datos que asigna claves a valores. La misma idea que un mapa, pero la implementación diferente:
-
Un mapa se representa internamente como una matriz de listas, donde cada elemento de estas listas es un par clave, valor. Tanto la clave como el valor son instancias de objeto.
-
Una matriz dispersa se hace simplemente de dos arrays: una serie de claves (primitivas) y una matriz de valores (objetos). Puede haber vacíos en estos índices de arrays, de ahí el término "escasa" matriz.
El principal interés de la SparseArray es que guarda memoria mediante el uso de primitivas en lugar de objetos como la clave.
Después de algunos google intento agregar alguna información a las ya publicadas:
Isaac Taylor hizo una comparación de rendimiento para SparseArrays y Hashmaps. Afirma que
El Hashmap y el SparseArray son muy similares para tamaños de estructura de datos menores de 1.000
y
Cuando el tamaño ha aumentado a la marca […] 10.000, el Hashmap tiene un mayor rendimiento con la adición de objetos, mientras que el SparseArray tiene un mayor rendimiento al recuperar objetos. […] En un tamaño de 100.000 […] el Hashmap pierde rendimiento muy rápidamente
Una comparación en Edgblog muestra que un SparseArray necesita mucho menos memoria que un HashMap debido a la clave más pequeña (int frente a Integer) y el hecho de que
Una instancia de HashMap.Entry debe realizar un seguimiento de las referencias de la clave, el valor y la entrada siguiente. Además, también necesita almacenar el hash de la entrada como un 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.
La documentación de Android para un SparseArray dice que "es generalmente más lento que un HashMap tradicional".
Si, es correcto. Pero cuando usted tiene solamente 10 o 20 artículos, la diferencia del funcionamiento 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 la mayoría de las veces sólo usamos HashMap
para buscar un valor asociado con una clave mientras que SparseArray
es realmente bueno en esto.
Si escribe código utilizando 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, por lo que sólo pagas poco esfuerzo moviéndolo a otras plataformas (a través de un simple COPY & Paste).
El mapa sobresale igual a () y hashCode () mientras que SparseArray no
Todo lo que puedo decir es, (a la mayoría de los desarrolladores) que se preocupan?
Otro aspecto importante de SparseArray
es que sólo utiliza una matriz para almacenar todos los elementos mientras HashMap
utiliza Entry
, por lo que SparseArray
cuesta menos memoria significativa que un HashMap
, vea esto
Mi punto de referencia dice que Sparse tiene la misma velocidad que Hash al añadir y 5! Veces más rápido al buscar con get (int). Sin embargo, en una velocidad de procesador de escritorio pueden diferir.
Vine aquí sólo queriendo un ejemplo de cómo usar SparseArray
. Esta es una respuesta suplementaria para eso.
Creación de un SparseArray
SparseArray<String> sparseArray = new SparseArray<>();
Un SparseArray
asigna números enteros a algún Object
, por lo que podría reemplazar String
en el ejemplo anterior por cualquier otro Object
. Si está asignando números enteros a 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 clave int
particular.
Eliminar elementos
Utilice 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 una clave entera.
String someAnimal = sparseArray.get(99); // "sheep" String anotherAnimal = sparseArray.get(200); // null
Puede utilizar get(int key, E valueIfKeyNotFound)
si desea evitar obtener null
para las claves que faltan.
Iterar sobre los elementos
Puede utilizar keyAt
y valueAt
algún índice para realizar un bucle a través de la colección porque SparseArray
mantiene un índice independiente 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.
Es lamentable que el compilador emita una advertencia. Supongo que HashMap ha sido demasiado utilizado para almacenar elementos.
SparseArrays tienen su lugar. Dado que utilizan un algoritmo de búsqueda binaria para encontrar un valor en una matriz que tiene que considerar lo que está haciendo. La búsqueda binaria es O (log n) mientras que la búsqueda de hash es O (1). Esto no significa necesariamente 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 se hace cargo. De ahí los comentarios donde un número bajo de entradas puede igualar y posiblemente ser mejor que usar un HashMap.
Un HashMap sólo 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 puede ser mejor optimizado). También agregaron un hash secundario para asegurarse de que el hash es bueno. También la razón SparseArray funciona realmente bien para relativamente pocas entradas (<100).
Sugeriría que si usted necesita una tabla del hash y desea un uso mejor de la memoria para el entero primitivo (ningún boxeo auto), etc., pruebe el trove. ( http://trove.starlight-systems.com – licencia LGPL). (Sin afiliación con trove, al igual que su biblioteca)
Con el edificio multi-dex simplificado que tenemos, ni siquiera necesita reempaquetar para lo que necesita. (El trove tiene muchas clases)