Este artículo analiza el código fuente de ArrayList. Déjame hablar de matrices antes de analizarlos. Las matrices pueden ser una de las primeras estructuras de datos con las que entramos en contacto. Dividan un espacio de direcciones continuo en la memoria para almacenar elementos. Dado que opera directamente la memoria, el rendimiento de las matrices es mejor que el de las clases de recolección, lo cual es una gran ventaja de usar matrices. Pero sabemos que la matriz tiene una falla fatal, es decir, el tamaño de la matriz debe especificarse durante la inicialización, y el tamaño de la matriz no se puede cambiar en las operaciones posteriores. En situaciones reales, encontramos más cosas que no sabemos cuántos elementos se almacenarán al principio, pero esperamos que el contenedor pueda expandir automáticamente su propia capacidad para que pueda almacenar más elementos. ArrayList puede satisfacer muy bien tales necesidades, y puede expandir automáticamente el tamaño para adaptarse al aumento continuo de los elementos de almacenamiento. Su capa subyacente se implementa en función de las matrices, por lo que tiene algunas características de las matrices, como encontrar modificaciones son rápidas y la inserción y la eliminación son lentos. En este artículo, profundizaremos en el código fuente para ver cómo encapsula las matrices. Primero mira a sus variables miembros y a los tres constructores principales.
// Capacidad de inicialización predeterminada Estático privado Final int default_capacitity = 10; // Vaciento Matriz de objetos Private Static Final Object [] vacía_elementData = {}; // Array de objetos Private Transiant Object [] elementData; // número de elementos de colección private size; // método de constructor para transmitir la capacidad publicitaria inicial (int inicial inicial) {super (); if (inicialcapacity <0) {tirar nueva ilegalargumentException ("capacidad ilegal:"+ inicialcapacity); } // Cree una nueva matriz de tipo de objeto de la capacidad especificada this.ElementData = new Object [InitialCapacity];} // Constructor sin parámetros public arrayList () {super (); // Pase una instancia de matriz vacía a elementData this.ElementData = vacía_elementData;} // Método de constructor para pasar a colección externa pública ArrayList (Collection <? Extends e> c) {// Mantenga el elemento de referencia de la matriz interna pasada a la colección ElementData = C.ToArray (); // actualizar el número de elementos del tamaño de colección = elementData.length; // juzga el tipo de referencia de matriz y convierta la referencia a una referencia de matriz de objeto if (elementData.getClass ()! = Object []. Class) {elementData = arrays.copyOf (elementData, size, object []. Class); }}Puede ver que la estructura de almacenamiento interna de ArrayList es una matriz de tipo de objeto, por lo que puede almacenar elementos de cualquier tipo. Al construir una lista de matrices, si se pasa el tamaño inicial, creará una nueva matriz de objetos de capacidad especificada. Si no se establece el tamaño inicial, no asignará espacio de memoria, sino que usará una matriz de objetos vacío y luego asignará memoria cuando el elemento realmente se coloque. Echemos un vistazo a sus métodos para agregar, eliminar, modificar y buscar.
// aumentar (agregar) public boolean add (e e) {// verifique si la matriz debe expandirse antes de agregar, la longitud mínima de la matriz es tamaño + 1 assureCapacityInternal (tamaño + 1); // Agregar elemento al final de la matriz ElementData [size ++] = e; return true;} // aumentar (insertar) public void add (int index, e elemento) {// Insertar el rango de posición check rangecheckforadd (índice); // Verifique si la capacidad debe ampliarse EnsurecapacityInternal (tamaño + 1); // Mueve el elemento detrás del sistema de posición de inserción. // Asignar un nuevo valor ElementData [index] = elemento; size ++;} // eliminar public e remove (int index) {// El índice no puede ser mayor que el tamaño rangecheck (índice); ModCount ++; E OldValue = elementData (índice); int numMoved = tamaño - índice - 1; if (numMoved> 0) {// Mueve el elemento detrás del índice hacia adelante por un sistema.ArrayCopy (elementData, index+1, elementData, index, numMoved); } // ElementData de referencia vacío [-size] = null; return OldValue;} // Cambiar public e set (int index, e elemento) {// índice no puede ser mayor que el tamaño rangecheck (índice); E OldValue = elementData (índice); // reemplazar con un nuevo elemento elementData [index] = elemento; return OldValue;} // Verifique el public e get (int index) {// El índice no puede ser mayor que el tamaño de ranGeCheck (índice); // devuelve el elemento de posición especificado ElementData (índice);} Cada vez que se agrega un elemento a la colección, primero verificará si la capacidad es suficiente, de lo contrario, la capacidad se ampliará. Los detalles de la expansión de la capacidad se discutirán a continuación. Primero veamos los puntos específicos a los que prestar atención al agregar, eliminar, modificar y verificar.
Agregar (agregar): simplemente agregue este elemento al final. Operación rápida.
Agregar (insertar): la operación es más lenta porque el elemento detrás de la posición de inserción debe moverse y la copia de la matriz está involucrada.
Eliminar: dado que los elementos detrás de la posición de eliminación deben avanzar, la copia de la matriz también se diseñará, por lo que la operación es lenta.
Cambio: modifique directamente los elementos en la ubicación especificada, sin involucrar el movimiento del elemento o la copia de la matriz, y la operación es rápida.
Verifique: Devuelva directamente el elemento de matriz del subíndice especificado, y la operación es rápida.
Desde el código fuente, se puede ver que, dado que la búsqueda y la modificación se colocan directamente en el subíndice de matriz, no implica el movimiento de elementos y la copia de la matriz, por lo que es más rápido. Sin embargo, debido a que los elementos deben moverse, implica la copia de matriz, por lo que la operación es más lenta. Además, cada operación de adición también puede realizar una expansión de matriz, lo que también afectará el rendimiento. Echemos un vistazo a cómo ArrayList expande dinámicamente su capacidad.
privado void asurecapacityInternal (int mincapacitity) {// Si la matriz todavía está vacía en este momento if (elementData == vacía_elementData) {// Compare con la capacidad predeterminada, tome el valor más grande mincapacity = math.max (default_capacity, mincapacity); } // Si la matriz se ha inicializado, realice este paso ASCANSEXPLICITECAPACIDAD (minCapacity);} private void aseSexplicitCapacity (int mincapacity) {modCount ++; // Si la capacidad mínima es mayor que la longitud de la matriz, amplifique la matriz if (mincapacity - elementData.length> 0) {Grow (minCapacity); }} // Capacidad máxima de la colección Private static final int max_array_size = integer.max_value - 8; // Aumente la longitud de matriz privada void creco (int mincapacity) {// Obtener la capacidad original de la matriz int // Capacidad de la nueva matriz, agregue la mitad en la base original int NewCapacity = OldCapacity + (OldCapacity >> 1); // Compruebe si la nueva capacidad es menor que la capacidad mínima if (newCapacity - mincapacity <0) {newCapacity = minCapacity; } // Verifique si la nueva capacidad excede la capacidad de matriz máxima if (newCapacity - max_array_size> 0) {newCapacity = HugeCapacity (minCapacity); } // Copiar la matriz original a la nueva matriz elementData = arrays.copyOf (elementData, newCapacity);} Antes de agregar elementos, EnsureCapacityInternal se solicitará para la verificación de capacidad de recolección. Dentro de este método, verificará si la matriz interna de la colección actual sigue siendo una matriz vacía. Si es así, cree una nueva matriz de objetos con el tamaño predeterminado de 10. Si no, demuestra que la colección actual se ha inicializado. Luego, llame al método ASARSEXPLICITCAPATity para verificar si la capacidad de la matriz actual cumple con la capacidad mínima requerida. Si no está satisfecho, llame al método de crecimiento para expandirse. En el método de crecimiento, puede ver que cada expansión aumenta la mitad de la longitud de la matriz original. La expansión es en realidad crear una nueva matriz con mayor capacidad, copiar todos los elementos de la matriz original a la nueva matriz y luego descartar la matriz original y usar la nueva matriz. Hasta ahora, hemos analizado los métodos más utilizados en ArrayList, y algunos de los puntos clave que vale la pena señalar:
1. La implementación subyacente de ArrayList se basa en matrices, por lo que la búsqueda y modificación de los subíndices especificados es más rápido, pero las operaciones de eliminación e inserción son más lentas.
2. Al construir una lista de matrices, intente especificar la capacidad tanto como sea posible para reducir las operaciones de copia de la matriz causadas por la expansión. Si no sabe el tamaño, puede asignar la capacidad predeterminada a 10.
3. Antes de agregar elementos, verifique si se requiere la expansión de la capacidad. Cada expansión de capacidad es la mitad de la capacidad original.
4. Cada vez que se opera la operación del subíndice, se realizará una verificación de seguridad. Si la matriz está fuera de los límites, se lanzará inmediatamente una excepción.
5. Todos los métodos de ArrayList no están sincronizados, por lo que no es seguro.
6. El análisis anterior se basa en JDK1.7, y otras versiones tendrán algunas diferencias, por lo que no puede generalizarse.
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.