1. Análisis del código fuente de ArrayList (JDK7)
ArrayList mantiene una matriz de objetos dinámico internamente. La adición y eliminación dinámica de ArrayList es la adición y eliminación dinámica de este par de grupos.
1. Construcción e inicialización de ArrayList
ArrayList Instance Variable // ArrayList Capacidad predeterminada PRIVADA ESTÁTICA FINAL INT Default_Capacity = 10; // Array de objeto vacío predeterminado, utilizado para definir vacío ArrayListPrivate Static Final Object [] vacía_ElementData = {}; // ArrayList almacena el objeto transiental privado de objetos [] elementData; // El número de elementos en el tamaño privado de ArrayList;ArrayList Constructor:
Sin constructor de parámetros: es decir, construir un objeto vacío []
public arrayList () {super (); this.ElementData = vacía_elementData;} Especifique la construcción del tamaño de la capacidad:
Public ArrayList (int InitialCapacity) {super (); if (InitialCapacity <0) tirar nueva IllegalArgumentException ("Capacidad ilegal:"+ InicialCapacity); this.ElementData = nuevo objeto [inicialcapacity];} Especificar una estructura de colección que implementa la interfaz de colección:
Public ArrayList (Collection <? Extends e> c) {elementData = c.toarray (); size = elementData.length; // C.ToArray podría (incorrectamente) no devolver objeto [] (ver 6260652) if (elementData.getClass ()! = Object []. Class) elementData = arrays.copyOf (elementData, size, object []. class);}Esto también explica el papel de la colección, y la razón por la cual Java-Collection-Framwork diseña la interfaz de recolección en lugar de usar directamente la lista, el conjunto y otras interfaces.
2. Mecanismo de asignación de capacidad de ArrayList
CAP de capacidad para ArrayList: la capacidad de ArrayList es el límite superior, y las teorías permiten la asignación de entero.max_value - 8 capacidad de tamaño. Sin embargo, cuánto se puede asignar depende de la configuración de la pila, y los parámetros de VM deben establecerse
Private static final int max_array_size = integer.max_value - 8;
Extender el volumen al llamar al método ADD
public boolean add (e e) {EnsurecapacityInternal (tamaño + 1); // incrementa modcount! elementData [size ++] = e; devolver verdadero; }El método EnsureCapacityInternal (int) en realidad determina un tamaño de expansión mínimo.
privado void asurecapacityInternal (int mincapacity) {if (elementData == vacía_elementData) {mincapacity = math.max (default_capacity, mincapacity); } asegurar EXUSEXPICITCAPACCID (minCapacity); } private void aseSexplicitCapacity (int mincapacity) {modCount ++; // Código consciente de desbordamiento if (mincapacity - elementData.length> 0) Grow (mincapacity); } Acerca de ModCount: ModCount se define en la clase abstracta de clase abstracta. Los comentarios del código fuente básicamente explican su uso: cuando se usa iterador para atravesar, se usa para verificar si los elementos en la lista tienen cambios estructurales (un recuento de la cantidad de elementos de la lista ha cambiado). Se usa principalmente en un entorno de múltiples subprocesos para evitar que un hilo se itere y otro hilo que modifique la estructura de esta lista.
El método de crecimiento es un método de expansión real
Private void Grow (int mincapacity) {// Overflow-Concscious Code int OldCapacity = elementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newCapacity - mincapacity <0) newCapacity = mincapacity; if (newCapacity - max_array_size> 0) newCapacity = HugeCapacity (mincapacity); // La mincapacidad generalmente está cerca del tamaño, por lo que esta es una victoria: elementData = arrays.copyOf (elementData, newCapacity); }También hay un método de HugeCapacity para la cantidad de capacidad ampliada
Private static int hugECapacity (int mincapacity) {if (mincapacity <0) // desbordamiento tirar nueva outOfMemoryError (); return (mincapacity> max_array_size)? Integer.max_value: max_array_size; } Resumir:
Cada expansión se acompaña de una copia de la matriz, por lo que dar la capacidad correcta a la vez mejorará un poco el rendimiento.
La siguiente figura es todo el proceso de expansión que resumí:
3. iterador de lista
Hay dos iteradores principales de ArrayList y Listitr, pero también se agrega un ArrayListsPliterator en JDK1.8. Aprendamos el análisis del código fuente de ITR y Listitr, respectivamente.
(1) ITR: solo puede ir hacia atrás
clase privada ITR implementa iterador <E> {int cursor; // índice del siguiente elemento para devolver int lastret = -1; // índice del último elemento devuelto; -1 Si no tal // esperadoModCount es una copia de ModCount int. public boolean Hasnext () {return cursor! = size; } @Suppleswarnings ("sin verificar") public e next () {checkforComOdification (); // Registre la posición actual int i = cursor; if (i> = size) tire nuevo nosuchelementException (); Objeto [] elementData = ArrayList.This.ElementData; if (i> = elementData.length) tire nuevo concurrentModificationException (); // La posición del siguiente elemento cursor = i + 1; return (e) elementData [lastret = i]; } // use el método de eliminación de Iterator public void remove () {if (LASTRET <0) Lanzar nueva IllegalStateException (); checkforcomodification (); Pruebe {// Tenga en cuenta cómo la clase interna llama a la clase externa ArrayList.THIS.Remove (LASTRET); // Después de eliminar, debe reajustar la posición de cada puntero cursor = latret; Lastret = -1; esperadoModCount = modCount; } Catch (indexOuTOfBoundsexception ex) {tirar nueva concurrenteModificationException (); }} final void checkForComOdification () {if (modCount! = EsperadoModCount) tire nuevo concurrentModificationException (); }} Del código fuente, se puede ver que el iterador ITR es un iterador directo, que proporciona un método siguiente para obtener elementos en la lista de matrices.
CheckForComodification es un mecanismo de detección de errores de falla en el trabajo de colección Java. La operación en el mismo conjunto en un entorno de múltiples subprocesos puede desencadenar el mecanismo de falla-rápida y organizar una excepción concurrente de Modificación Excepción.
El ITR Iterator define una copia del ModCount de registro esperado MODCOUNT. Cuando ArrayList realiza operaciones para cambiar la estructura, como agregar, eliminar y borrar métodos, el valor de ModCount cambiará.
A través del código fuente de ITR, se puede ver que llamar a los métodos siguientes y eliminar activará la verificación de Fail-Fast. En este momento, si se produce una excepción cuando otros hilos realizan operaciones que cambian la estructura del conjunto mientras atraviesa el conjunto.
(2) Listitr: admite el recorrido hacia adelante y hacia atrás. Echemos un vistazo al código fuente de Listitr:
Private Class Listitr extiende ITR implementos listIterator <E> {listitr (int index) {super (); cursor = índice; } public boolean Hasprevious () {return cursor! = 0; } public int NextIndex () {return cursor; } public int anteriorindex () {return cursor - 1; } @Suppleswarnings ("sin verificar") public e anterior () {checkforcomOdification (); // La posición del elemento anterior del arrayList int i = cursor - 1; if (i <0) tirar nueva nosuchelementException (); Objeto [] elementData = ArrayList.This.ElementData; if (i> = elementData.length) tire nuevo concurrentModificationException (); cursor = i; return (e) elementData [lastret = i]; } // El método establecido se agrega a este set de iterador público void (e e) {if (lastret <0) tirar nueva ilegalStateException (); checkforcomodification (); Pruebe {ArrayList.This.Set (LASTRET, E); } Catch (indexOuTOfBoundsexception ex) {tirar nueva concurrenteModificationException (); }} // Este iterador agrega el método add public void add (e e) {checkforComOdification (); intente {int i = cursor; ArrayList.THIS.Add (i, e); // Observar el cursor de posición del puntero = i + 1; Lastret = -1; esperadoModCount = modCount; } Catch (indexOuTOfBoundsexception ex) {tirar nueva concurrenteModificationException (); }}}La implementación de ListITR es básicamente la misma que la ITR, agregando métodos que se pueden atravesar previamente, así como agregar y establecer métodos.
(3) Use CopyOnWriteArrayList en java.util.concurrent para resolver el problema de falla rápida
CopyOnWriteArrayList es afronado. Para más detalles, echemos un vistazo a su código fuente de método ADD:
public boolean add (e e) {fin final reentrantlock bloqueo = this.lock; Lock.lock (); intente {objeto [] elements = getArray (); int len = Elements.length; Objeto [] newelements = arrays.copyOf (elementos, len + 1); Newelements [len] = E; SetArray (Newelements); devolver verdadero; } Finalmente {Lock.unlock (); }} CopyOnWriteArrayList es una lista de matrices copiada en Write. Al comenzar la operación de la escritura de datos, Arrays.CopyOf es una nueva matriz, que no afectará la operación de lectura.
Este costo es perder memoria y lograr problemas de rendimiento. Cuando se escribe CopyOnWriteArrayList, se genera un objeto de copia en la memoria y el objeto original todavía existe.
CopyOnWriteArrayList no puede garantizar la consistencia de los datos en tiempo real, solo puede garantizar la consistencia de los resultados. Adecuado para escenarios como el caché al leer más y escribir más y escribir menos en situaciones concurrentes.
(4) Otros métodos Código fuente de ArrayList:
Un método privado Batchremove (colección <?> C, complemento booleano), es decir, operación de eliminación de lotes
Private Boolean Batchremove (colección <?> C, complemento booleano) {// El motivo de usar final se menciona a continuación objeto final [] elementData = this.elementData; int r = 0, w = 0; booleano modificado = falso; Pruebe {// tranquilidad a través de los elementos en la lista y verifique para (; r <size; r ++) if (c.contains (elementData [r]) == complement) elementData [w ++] = elementData [r]; } Finalmente {// Si se produce una excepción en prueba, asegúrese de la consistencia de los datos y realice la siguiente operación de copia if (r! = size) {System.ArrayCopy (ElementData, R, ElementData, W, Size - R); w += tamaño - r; } // Limpiar elementos no utilizados y notificar a GC para reciclar if (w! = Size) {// claro para dejar que GC haga su trabajo para (int i = w; i <size; i ++) elementData [i] = null; ModCount += tamaño - W; tamaño = W; modificado = verdadero; }} return modificado; } La variable modificada por final se refiere a la misma referencia para mantener la consistencia de los datos más adelante.
En este método, cuando desea retener elementos en la Colección C, el valor del complemento es verdadero; Cuando desea eliminar elementos en C, el valor del complemento es falso. Esto se convierte en los métodos retener y eliminar respectivamente.
Intercambio: intercambie las dos posiciones en la ArrayList
2. Análisis del código fuente de LinkedList (JDK7)
LinkedList es una lista vinculada. En comparación con la tabla de pedidos, la lista vinculada no necesita usar unidades de memoria continua para almacenar datos. Reduce el problema de los elementos móviles causados por la modificación de la estructura del contenedor, y el acceso secuencial es relativamente eficiente.
1. Definición de nodo
LinkedList en JDK es una lista vinculada bidireccional, cada nodo almacena información sobre el nodo anterior y el siguiente nodo respectivamente. Su definición es la siguiente:
Nodo de clase estática privada <E> {E item; Nodo <E> siguiente; Nodo <E> anterior; Nodo <E> (nodo <E> anterior, e elemento, nodo <e> next) {this.item = elemento; this.next = siguiente; this.prev = prev; }}2. Construcción e inicialización de Linkedlist
Miembro: 3 variables de miembros se mantienen en LinkedList para registrar el número de nodos en la lista vinculada, el predecesor y el sucesor de los nodos
transitorio int size = 0; nodo transitorio <e> primero; nodo transitorio <e> last;
Constructor: el constructor predeterminado es construir una LinkedList vacía
public LinkedList () {}O construir según otros contenedores, y luego escribiremos un constructor para formar una lista de enlaces ordenada.
public LinkedList (colección <? extiende e> c) {this (); addall (c);}Aquí hay un poco más. ¿Para la diferencia entre el modificador genérico? Super T y extiende t, vea este artículo sobre la diferencia entre Super T y extiende T en genéricos.
3. Operación estructural de Linkedlist
Método de inserción del encabezado: es decir, inserte un elemento en el encabezado de la lista vinculada
Private void LinkFirst (e e) {nodo final <e> f = primero; nodo final <E> newnode = nuevo nodo <> (nulo, e, f); primero = newnode; // juzga si es una lista vinculada vacía si (f == null) last = newnode; else F.Prev = NewNode; tamaño ++; ModCount ++; } Método de inserción de la cola: es decir, inserte un elemento al final de la lista vinculada
Void LinkLast (E E) {nodo final <E> L = Last; nodo final <E> newnode = nuevo nodo <> (l, e, nulo); Último = Newnode; if (l == null) primero = newnode; else L.Next = Newnode; tamaño ++; ModCount ++; } Antes de insertar en el nodo actual: encuentre la unidad delantera del nodo actual
void linkbefore (e e, nodo <E> succ) {// Determinar si el nodo no está vacío de nodo final <E> pred = succ.prev; nodo final <E> newnode = nuevo nodo <> (pred, e, succ); succ.prev = newnode; // Determinar si el nodo actual es el primer nodo if (pred == null) primero = newnode; else Pred.Next = Newnode; tamaño ++; ModCount ++; } Método de deleción de encabezado: Elimine el primer nodo de la lista vinculada
privado e Unlinkfirst (nodo <e> f) {// afirmar f == primero && f! = null; Elemento E final = F.Item; nodo final <E> next = f.next; F.Item = nulo; F.next = nulo; // Ayuda GC primero = Next; if (next == null) last = null; el otro otro siguiente.prev = null; tamaño--; ModCount ++; elemento de retorno; } Método de deleción de la cola: elimine el último nodo de la lista vinculada
Private E Unlinklast (nodo <E> L) {// Asegúrese de L == Last y L! = NULL FINAL E Element = l.Item; nodo final <E> prev = l.prev; l.Item = nulo; l.prev = nulo; // Ayuda GC Last = Prev; if (prev == null) primero = null; else Prev.next = nulo; tamaño--; ModCount ++; elemento de retorno; }4. Mantenga la consistencia entre la interfaz de la lista y el deque
La interfaz de la lista permite el uso de subíndices implementar el acceso aleatorio a los contenedores, y es fácil implementar el acceso aleatorio a matrices como esta. Para listas vinculadas, JDK también usa lógicamente el recuento de nodos en listas vinculadas para dar la implementación de acceso aleatorio
Nodo <E> nodo (int index) {// Asegúrese de la corrección del índice if (índice <(tamaño >> 1)) {nodo <E> x = primero; para (int i = 0; i <index; i ++) x = x.next; regresar x; } else {nodo <E> x = último; para (int i = size-1; i> index; i--) x = x.prev; regresar x; }} El índice es el recuento de la primera mitad, busca desde el principio. El índice pertenece al recuento de la segunda mitad y busca desde el final. Haga un uso completo de las características de las listas vinculadas bidireccionales.
Por lo tanto, Agregar (INT index, t t), get (int), set (int) y otros métodos se pueden implementar fácilmente.
LinkedList implementa la interfaz Deque, es decir, LinkedList implementa el método de contenedores de cola de doble extremo. Aquí hay algún resumen de API.
5. Linkedlist Traversal
Dado que LinkedList es una lista vinculada de dos vías, puede atravesarla naturalmente de un lado a otro. Al igual que ArrayList, LinkedList también tiene problemas de fallas cuando se trata de operación de contenedores de múltiples subprocesos.
El tema de Fail-Fast se ha explicado en el artículo anterior, por lo que no hablaré de eso aquí.
Con respecto a los iteradores, LinkedList tiene un iterador bidireccional de ListIterator y un iterador inverso descendectante de periodista. Todos son muy simples. El código fuente no se analiza
Si atraviesa elementos, el costo del acceso aleatorio es relativamente alto.
3. LinkedList, ArrayList, Vector Resumen
1. Linkedlist y ArrayList
ArrayList implementa una estructura de datos basada en matrices dinámicas, y LinkedList se basa en una estructura de datos basada en una lista vinculada.
Para el acceso aleatorio a Get and Set, ArrayList se siente mejor que LinkedList porque LinkedList mueve el puntero.
Para las operaciones nuevas y de eliminación, agrega y elimina, LinedList tiene una mejor ventaja porque ArrayList necesita mover datos. Esto depende de la situación real. Si solo se inserta o elimina una sola pieza de datos, la velocidad de ArrayList es mejor que la de LinkedList. Sin embargo, si los datos se insertan aleatoriamente en lotes, la velocidad de LinkedList es mucho mejor que la de ArrayList. Porque cada vez que una lista de matrices inserta datos, es necesario mover el punto de inserción y todos los datos después.
2. ArrayList y Vector
El vector es sincronal de hilos, por lo que también es seguro de hilo, mientras que ArrayList es Thread-Asyn, lo que no es seguro. Si no se tienen en cuenta los factores de seguridad del hilo, ArrayList es generalmente más eficiente.
Si el número de elementos en el conjunto es mayor que la longitud de la matriz del conjunto actual, la tasa de crecimiento del vector es del 100% de la longitud de la matriz actual, y la tasa de crecimiento de la lista de matrices es del 50% de la longitud de la matriz actual. Si usa datos con cantidades relativamente grandes de datos en el conjunto, el uso de vector tiene ciertas ventajas.
Si busca datos en una ubicación especificada, el tiempo utilizado por Vector y ArrayList es el mismo, tanto 0 (1), y puede usar Vector y ArrayList en este momento. Si el tiempo dedicado a mover los datos en una ubicación especificada es 0 (Ni) N, que es la longitud total, debe considerar usar LinkList, porque se necesita 0 (1) para mover los datos en una ubicación especificada, y el tiempo dedicado a la consulta de los datos en una ubicación especificada es 0 (i).
ArrayList y Vector usan matrices para almacenar datos. El número de elementos en esta matriz es mayor que los datos almacenados reales para agregar e insertar elementos. Ambos permiten elementos de índice de número de serie directo. Sin embargo, la inserción de datos debe diseñarse para mover elementos de matriz y otras operaciones de memoria, por lo que los datos de índice son rápidos y lentos para insertar datos. Vector usa el método sincronizado (hilo seguro), por lo que el rendimiento es peor que ArrayList. LinkedList utiliza una lista vinculada bidireccional para almacenar datos. La indexación de los datos de acuerdo con el número de serie requiere un recorrido hacia adelante o hacia atrás, pero al insertar datos, solo se registran los elementos delanteros y posteriores de este elemento, por lo que insertar varios grados es más rápido.