Análisis de matriz dispersa (SparseArray)

Nota: SparseArray proviene del código fuente de Android

Preguntas:

1. ¿Qué es SparseArray?

2. ¿Cuál es la descripción de la estructura de datos utilizada por SparseArray?

3. ¿Cuál es el tamaño predeterminado de SparseArray?

4.¿Cuál es la capacidad máxima de SparseArray? ¿Cuál es la capacidad máxima de un SparseArray?

5. ¿Cuál es el principio de adquisición de SparseArray?

6. ¿Cuál es el principio de SparseArrayput?

7. ¿Qué algoritmo se utiliza para la búsqueda SparseArray?

8. ¿Cuáles son las comparaciones y escenarios de aplicación entre SparseArray y HashMap?

Sparse se traduce como disperso, lo cual carece de significado. ¿Es SparseArray una matriz dispersa? ¿Es SparseArray una matriz dispersa? Hay tantos significados en él. El escenario de la aplicación es que los datos son relativamente escasos. En general, el rendimiento es mejor que HashMap en unos pocos cientos de datos y el rendimiento mejora entre 0 y 50. SparseArray usa Integer como objeto de mapeo de claves. Echemos un vistazo a sus consideraciones clave:

SparseArray no utiliza la estructura de lista enlazada individualmente de matriz unidimensional como HashMap, sino que usa dos matrices unidimensionales, una para almacenar claves (tipo int) y otra para almacenar claves. es el valor de existencia.

Los subíndices utilizados para leer y escribir mKeys y mValues ​​están en correspondencia uno a uno

La respuesta es 10. SparseArray no define una capacidad predeterminada, pero especifica su capacidad predeterminada en el constructor predeterminado.

SparseArray no define la capacidad máxima como HashMap. La capacidad máxima puede alcanzar el valor de Integer.MAX_VALUE, por lo que su tamaño de capacidad predeterminado se puede especificar en el constructor predeterminado.

SparseArray No existe una definición de capacidad máxima como HashMap, pero su capacidad predeterminada se especifica en el constructor predeterminado. Cuando la capacidad actual de cada expansión es menor que 5, la capacidad actual de la expansión es menor que 5. En este momento, la capacidad actual de la expansión es menor que 5. Si la capacidad actual es inferior a 5, se ampliará a 8; de lo contrario, será 2 veces la capacidad original. Sabrá por qué si observa el principio de entrega.

Primero veamos el código fuente de obtención:

Debido a que SparseArray usa dos matrices unidimensionales para almacenar claves y valores, si encuentra el subíndice basado en la clave, puede utilice el subíndice para obtener el valor correspondiente. El subíndice correspondiente a la clave se puede encontrar mediante el método de bisección.

Veamos primero el código fuente:

A través del código fuente anterior, podemos resumirlo de la siguiente manera:

1. Encuentre el subíndice de la clave mediante el método de dicotomía, determine si ya hay una clave para agregar y, si la encuentra, reemplace directamente el valor correspondiente

2. Si no hay ninguna clave para agregar y la capacidad de la clave es suficiente, agréguelo directamente

3. Si no hay claves para agregar y la capacidad es suficiente, agréguelas

3. Si no hay claves para agregar, expanda las dos matrices. almacenar claves y valores y agregar elementos

Se puede obtener información mediante la operación put:

1. SparseArray permite insertar una matriz con un valor nulo porque el tipo de clave es int. , no hay ningún caso en el que la clave sea nula.

En este caso

2. Para garantizar que las claves estén en orden cuando SparseArray agregue elementos, se ordenará según el tamaño de las claves, porque utiliza el método de segmentación para encontrar el subíndice correspondiente. a la clave correspondiente

3. De forma predeterminada, la capacidad de SparseArray se duplica cada vez que se expande (en casos especiales, si la capacidad actual es menor que 5, se expandirá a 8).

Vale, ya sabemos lo que queremos hacer. p>

Bien, vamos a comenzar a agregar elementos nuevamente. ¿Por qué necesitamos usar el método binario para negar el subíndice i? Echemos un vistazo a la implementación del código fuente:

Lo anterior es la implementación de la dicotomía. Si no comprende qué es la dicotomía, primero comprenda qué es la dicotomía.

A diferencia de otras implementaciones de métodos binarios, cuando no encuentra un elemento coincidente, no devuelve -1, sino el valor invertido después de agregar la posición del elemento. Este valor invertido se convierte en un número negativo. Entonces, cuando esta dicotomía devuelve un número negativo, significa que el valor correspondiente no existe en la matriz original, lo que significa que es necesario agregar un nuevo elemento, y luego el índice de posición del elemento que se agregará es añadido al revés.

El valor de retorno de dicotomía i inverso aquí tiene dos significados:

1. Un número negativo significa que no se puede encontrar ningún elemento, lo que significa que es necesario agregar un elemento

2, la posición del subíndice del elemento que se agregará

Si aún no lo entiende, piénselo de nuevo.

El análisis del código fuente de get y put ha sido muy claro. Utiliza el algoritmo de dicotomía.

1. SparseArray no usa el algoritmo hash, HashMap usa el algoritmo hash. p>

2. SparseArray utiliza dos matrices unidimensionales para almacenar claves y valores respectivamente. Las claves de HashMap SparseArray solo pueden ser de tipo int, mientras que HashMap puede ser de cualquier tipo

4. Las claves de SparseArray se almacenan en orden (orden ascendente), pero HashMap no.

5. La capacidad predeterminada de SparseArray es 10, mientras que la capacidad predeterminada de HashMap es 16. La capacidad predeterminada de HashMap es 16

6. La expansión predeterminada de SparseArray es 2 veces la capacidad original, mientras que la expansión predeterminada de HashMap es 0,75 veces la capacidad original

7 El uso de memoria de SparseArray es mejor que el de HashMap porque:

8. La búsqueda de elementos de SparseArray es generalmente peor que la de HashMap, porque la búsqueda de SparseArray requiere un proceso de dicotomía, mientras que HashMap no tiene conflictos y es. La tecnología está en HashMap. Se espera que el subíndice correspondiente pueda tomar el valor directamente.

Para la comparación anterior con HashMap, se recomienda utilizar SparseArray o HashMap según los siguientes requisitos:

<. p> 1. Si se comparan los requisitos de memoria Si la eficiencia de la consulta no es alta, puede usar SparseArray

2. SparseArray tiene una mejor ventaja que HashMap en cientos de cantidades

3 El requisito clave es el tipo int, porque HashMap personalizará int en tipo Integer

4. Las claves deben estar ordenadas y ascendentes

.