Análisis de matriz dispersa
Preguntas:
1. ¿Qué es SparseArray?
2. ¿SparseArray utiliza una estructura de datos de descripción?
3.¿Cuál es la capacidad predeterminada de SparseArray?
4.¿Cuál es la capacidad máxima de SparseArray? ¿Cuánto hay que ampliar cada vez?
5.¿Cuál es el principio de obtención de SparseArray?
6. ¿Cuál es el principio de SparseArray?
7. ¿Qué algoritmo se utiliza para la búsqueda de matrices dispersas?
8. En comparación con HashMap, ¿cuáles son los escenarios de aplicación?
Sparse se traduce en escasez y carencia. ¿SparseArray es una matriz dispersa? Hay algo interesante aquí. El escenario de la aplicación son datos relativamente escasos. Generalmente, el rendimiento de los datos dentro de unos pocos cientos es mejor que HashMap y el rendimiento mejorará entre 0 y 50. SparseArray es un objeto de mapeo con Integer como clave. Echemos un vistazo a su tono:
SparseArray no utiliza una 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.
MKeys y mValues tienen subíndices uno a uno al leer y escribir.
La respuesta es 10. SparseArray no define un tamaño de capacidad predeterminado, pero su tamaño de capacidad predeterminado se especifica en el constructor predeterminado.
SparseArray no define la capacidad máxima como HashMap. La capacidad máxima puede alcanzar un número entero. MAX_VALUE, se puede informar a oom. Si la capacidad actual es inferior a 5, la capacidad es 8; de lo contrario, la capacidad original es 2 veces. Puedes ver por qué cuando observas el principio bajista.
Primero mire el código fuente obtenido:
Debido a que SparseArray usa dos matrices unidimensionales para almacenar claves y valores respectivamente, podemos encontrar el subíndice según la clave. y luego use el subíndice Recuperar el valor correspondiente. Entre ellos, el método binario se utiliza para encontrar el subíndice correspondiente a la clave.
Mire primero el código fuente:
A través del código fuente anterior, podemos resumir lo siguiente:
1. subíndice de la clave y juzgue si la clave que se agregará ya existe. Si lo encuentra, reemplace el valor correspondiente directamente.
2. Si no hay llaves para agregar y la capacidad es suficiente, agréguelas directamente.
3. Si no hay claves para agregar, expanda las dos matrices que almacenan claves y valores y agregue elementos.
La información que se puede obtener mediante la operación put es la siguiente:
1 y SparseArray permiten la inserción de valores nulos. Como las claves son de tipo int, no hay claves nulas.
2. Cuando SparseArray agrega elementos, las claves se ordenan según el tamaño de las claves, porque el método de dicotomía que utiliza ahora es encontrar el subíndice correspondiente a la clave correspondiente.
3. La expansión de capacidad predeterminada de SpareseArray es 2 veces la capacidad original (en casos especiales, si la capacidad actual es 5, se ampliará a 8).
Bien, cuando volvamos a sumar elementos, ¿por qué tenemos el subíndice I como inverso de la bisección? Echemos un vistazo a su implementación del código fuente:
Lo anterior es la implementación de la dicotomía. Si no sabe qué es la dicotomía, primero comprenda qué es la dicotomía.
A diferencia de otros métodos binarios, cuando no encuentra un elemento coincidente, no devuelve -1, pero los valores después de invertir las posiciones de los elementos se suman y la inversión se convierte en un número negativo. . Entonces, cuando esta dicotomía devuelve un número negativo, significa que no hay un valor correspondiente en la matriz original, lo que significa que es necesario agregar un nuevo elemento. Al agregar, la inversión se convierte en la posición del subíndice del elemento que se agregará.
La dicotomía aquí tiene dos significados:
1. Un número negativo significa que el elemento no se encuentra y significa que se ha agregado un elemento.
2. La posición del subíndice del elemento que se agregará.
Si aún no lo entiendes, piénsalo de nuevo.
El análisis del código fuente de Get y Put ya es muy claro y en él se utiliza el algoritmo de dicotomía.
1. SparseArray no es un algoritmo hash, HashMap es un algoritmo hash.
2.SparseArray usa dos matrices unidimensionales para almacenar claves y valores respectivamente, y HashMap usa matrices unidimensionales y listas vinculadas unidireccionales.
3.Las claves SparseArray solo pueden ser de tipo int, mientras que HashMap puede ser de cualquier tipo.
4. Las claves SparseArray se almacenan en orden (orden ascendente), HashMap no.
5. La capacidad predeterminada de SparseArray es 10 y la capacidad predeterminada de HashMap es 16.
6.SparseArray tiene por defecto 2 veces la capacidad original y HashMap tiene por defecto *0,75 veces la capacidad original.
7. El uso de memoria de matrices dispersas es peor que HashMap porque:
8. Los elementos de búsqueda de SparseArray generalmente no son tan buenos como los de HashMap, porque la búsqueda de SparseArray es un proceso dicotómico y existe. No hay conflicto en HashMap. En este caso, el subíndice correspondiente a su hash técnico puede obtener directamente el valor.
En vista de la comparación anterior con HashMap, se recomienda elegir SparseArray o HashMap de acuerdo con los siguientes requisitos:
1. Si los requisitos de memoria son altos pero no hay grandes requisitos. Para mejorar la eficiencia de las consultas, se puede utilizar SparseArray.
2. SparseArray con una cantidad de 100 niveles tiene mejores ventajas que HashMap.
3. La clave debe ser de tipo int, porque HashMap personalizará el empaquetado de int y lo cambiará al tipo Integer.
4. Requerir que las claves se ordenen en orden ascendente.