1. Análise de código -fonte do Arraylist (JDK7)
Arraylist mantém uma matriz de objetos dinâmicos internamente. A adição e a exclusão dinâmica da Arraylist é a adição e a exclusão dinâmica desse par de grupos.
1. Construção e inicialização do Arraylist
ArrayList Instância variável // Capacidade padrão ArrayList private estático final int default_capacity = 10; // Matriz de objeto vazio padrão, usada para definir o ArrayList PrayListttate PRIVIDO ESTÁTICO ESTÁTICO DOBJETO [] vazio_ElementData = {}; // ArrayList armazena o objeto Array Private Object IntsatA;Construtor Arraylist:
Nenhum construtor de parâmetros: ou seja, construa um objeto vazio []
public ArrayList () {super (); this.ElementData = emaillementData;} Especifique a construção de tamanho de capacidade:
public ArrayList (int InitialCapacity) {super (); if (InitialCapacity <0) lançar novas ilegalargumentException ("Capacidade ilegal:"+ InitialCapacidade); this.ElementData = novo objeto [InitialCapacity];} Especifique uma estrutura de coleção que implementa a interface de coleta:
public ArrayList (coleção <? Extends e> c) {elementData = c.toarray (); size = elementData.length; // c.toArray pode (incorretamente) não retornar objeto [] (consulte 6260652) if (elementData.getClass ()! = object []. class) elementData = Arrays.copyof (elementData, tamanho, objeto []. classe);}Isso também explica o papel da coleção e a razão pela qual Java-Collection-Framwork projeta a interface de coleção em vez de usar diretamente a lista, o conjunto e outras interfaces.
2. Mecanismo de alocação de capacidade do Arraylist
Capacidade Captura para ArrayList: a capacidade do Arraylist é o limite superior e as teorias permitem a alocação de Integer.max_value - 8 Capacidade de tamanho. No entanto, quanto pode ser alocado depende das configurações da pilha, e os parâmetros da VM precisam ser definidos
private estático final int max_array_size = Integer.max_value - 8;
Estender o volume ao chamar o método Add
public boolean add (e e) {securecapacityInternal (tamanho + 1); // incrementos modCount !! ElementData [size ++] = e; retornar true; }O método EnsureCapacityInternal (int) determina realmente um tamanho mínimo de expansão.
Void privado EnsureCapacityInternal (int mincapacity) {if (elementData == emaillement_elementData) {mincapacity = Math.max (default_capacity, mincapacity); } garantirexplicitCapacity (Mincapacity); } void privado garantirexplicCapacity (int mincapacity) {modCount ++; // Código consciente de transbordamento if (Mincapacity - ElementData.Length> 0) Grow (MinCapacity); } SOBRE MODCOUNT: O MODCOUNT é definido na classe abstrata AbstractList. Os comentários do código -fonte explicam basicamente seu uso: ao usar o iterador para atravessar, é usado para verificar se os elementos da lista têm alterações estruturais (uma contagem do número de elementos da lista mudou). Ele é usado principalmente em um ambiente multithread para impedir que um thread iterar e outro thread modificando a estrutura desta lista.
O método de crescimento é um método de expansão real
Grow privado de vazio (int mincapacity) {// Código consciente de transbordamento int OldCapacity = ElementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newCapacity - MinCapacity <0) newCapacity = Mincapacity; if (newCapacity - max_array_size> 0) newCapacity = hugecapacity (mincapacidade); // MinCapacity geralmente é próximo do tamanho, então isso é uma vitória: elementData = Arrays.copyof (ElementData, NewCapacity); }Há também um método de HugeCapacity para quanta capacidade é expandida
private estático int hugecapacidade (int mincapacity) {if (mincapacity <0) // Overflow lançam um novo outOfMemoryError (); Return (Mincapacity> max_array_size)? Integer.max_value: max_array_size; } Resumir:
Cada expansão é acompanhada de uma cópia da matriz, portanto, fornecer a capacidade certa de cada vez melhorará um pouco o desempenho.
A figura a seguir é todo o processo de expansão que resumi:
3.ArrayList Iterator
Existem dois iteradores principais do ArrayList e Listitr, mas um ArrayListsPliterator também é adicionado no JDK1.8. Vamos aprender a análise do código -fonte do ITR e Listitr, respectivamente.
(1) ITR: só pode voltar para trás
classe privada ITR implementa o iterador <E> {int cursor; // índice do próximo elemento para retornar int lastret = -1; // Índice do último elemento retornado; -1 Se não tais // esperamModCount for uma cópia do modCount int esperamModCount = modCount; public boolean hasNext () {return cursor! = size; } @Suppresswarnings ("desmarcado") public e next () {checkForComodification (); // Registre a posição atual int i = cursor; if (i> = size) lança novos nosuchElementException (); Objeto [] ElementData = ArrayList.This.ElementData; if (i> = elementData.length) lança nova concurrentmodificationException (); // a posição do próximo elemento cursor = i + 1; return (e) elementData [lastret = i]; } // Use o método Remover do iterador public void remover () {if (lastret <0) lança new ilegalStateException (); checkForComodification (); tente {// observe como a classe interna chama a classe externa ArrayList.This.Remove (lastret); // Após a remoção, você precisa reajustar novamente a posição de cada ponteiro cursor = lastret; lastret = -1; esperadomodCount = modCount; } catch (indexOutOfBoundSexception ex) {tiro novo concurrentModificationException (); }} Final void checkForComodification () {if (modCount! = esperadoModCount) lança novo concurrentmodificationException (); }} A partir do código -fonte, pode -se observar que o iterador ITR é um iterador avançado, que fornece um próximo método para obter elementos no ArrayList.
O CheckForComodification é um mecanismo de detecção de erro de falha no Java-Collection-Framwork. A operação no mesmo conjunto em um ambiente multithread pode desencadear o mecanismo de falha e lançar uma exceção concorrente de exceção.
O iterador ITR define uma cópia do ModCount Record de ModCount esperado. Quando o ArrayList executa operações para alterar a estrutura, como Add, Remover e Limpar métodos, o valor do ModCount será alterado.
Através do código-fonte do ITR, pode-se observar que ligar para o próximo e remover métodos acionará a verificação de falha. No momento, se ocorrer uma exceção quando outros threads estão executando operações que alteram a estrutura do conjunto enquanto atravessam o conjunto.
(2) Listitr: suporta travessia para frente e para trás. Vamos dar uma olhada no código -fonte do Listitr:
classe privada listitr estende o ITR implementa o listiterator <E> {listitr (int index) {super (); cursor = index; } public boolean hasprevious () {return cursor! = 0; } public int nextIndex () {return cursor; } public int anteriorIndex () {return cursor - 1; } @Suppresswarnings ("desmarcado") public e anterior () {checkForComodification (); // a posição do elemento anterior do Arraylist int i = cursor - 1; if (i <0) lançar novos nosuchElementException (); Objeto [] ElementData = ArrayList.This.ElementData; if (i> = elementData.length) lança nova concurrentmodificationException (); cursor = i; return (e) elementData [lastret = i]; } // O método de SET é adicionado a este conjunto de void public iterator (e e) {if (lastret <0) lança new ilegalStateException (); checkForComodification (); tente {ArrayList.This.Set (lastret, e); } catch (indexOutOfBoundSexception ex) {tiro novo concurrentModificationException (); }} // Este iterador adiciona o método add public void add (e e) {checkForComodification (); tente {int i = cursor; ArrayList.This.add (i, e); // observa a posição do ponteiro cursor = i + 1; lastret = -1; esperadomodCount = modCount; } catch (indexOutOfBoundSexception ex) {tiro novo concurrentModificationException (); }}}A implementação do Listitr é basicamente a mesma que o ITR, adicionando métodos que podem ser percorridos anteriormente, além de métodos de adição e definição.
(3) Use CopyOnWritEarRayList em java.util.Concurrent para resolver o problema de falha rápida
CopyOnWriteArrayList é seguro para threads. Para detalhes, vamos dar uma olhada no código -fonte do método Add:
public boolean add (e e) {final reentrantlock bloqueio = this.lock; Lock.lock (); tente {object [] elements = getArray (); int len = elements.length; Objeto [] newElements = Arrays.copyof (elementos, len + 1); NewElements [len] = e; SetArray (NewElements); retornar true; } finalmente {Lock.unlock (); }} CopyOnWriteArrayList é um ArrayList copiado na gravação. Ao iniciar a operação de escrever dados, o Arrays.copyof é uma nova matriz, que não afetará a operação de leitura.
Esse custo é perder a memória e trazer problemas de desempenho. Quando o copyWriteArrayList é escrito, um objeto de cópia é gerado na memória e o objeto original ainda existe.
CopyOnWriteArrayList não pode garantir a consistência dos dados em tempo real, ele só pode garantir a consistência dos resultados. Adequado para cenários como cache ao ler mais e escrever mais e escrever menos em situações simultâneas.
(4) Outros métodos Código Fonte de Arraylist:
Um método privado BatchRemove (coleção <?> C, complemento booleano), ou seja, operação de remoção de lote
Private Boolean BatchRemove (coleção <?> C, complemento booleano) {// O motivo do uso do final é mencionado abaixo do objeto final [] elementData = this.ElementData; int r = 0, w = 0; booleano modificado = false; tente {// Tranquilidade através dos elementos da lista e verifique para (; r <size; r ++) if (c.contains (elementData [r]) == complement) elementData [w ++] = elementData [r]; } finalmente {// Se ocorrer uma exceção na tentativa, verifique a consistência dos dados e execute a seguinte operação de cópia se (r! = size) {System.arraycopy (ElementData, R, ElementData, W, Size - R); w += tamanho - r; } // Limpe os elementos não utilizados e notifique o GC para reciclar se (w! = Size) {// Limpe para deixar o GC fazer seu trabalho para (int i = w; i <tamanho; i ++) elementData [i] = null; modCount += tamanho - w; tamanho = w; modificado = true; }} retornar modificado; } A variável modificada por final refere -se à mesma referência para manter a consistência dos dados posteriormente.
Neste método, quando você deseja reter elementos na coleção C, o valor do complemento é verdadeiro; Quando você deseja remover elementos em C, o valor do complemento é falso. Isso se torna os métodos reter e removeados, respectivamente.
Troque: troque as duas posições no Arraylist
2. Análise de código -fonte do LinkedList (JDK7)
LinkedList é uma lista vinculada. Comparado com a tabela de pedidos, a lista vinculada não precisa usar unidades de memória contínua para armazenar dados. Reduz o problema dos elementos em movimento causados pela modificação da estrutura do contêiner, e o acesso sequencial é relativamente eficiente.
1. Definição de nó
O LinkedList no JDK é uma lista vinculada bidirecional, cada nó armazena informações sobre o nó anterior e o próximo nó, respectivamente. Sua definição é a seguinte:
classe estática privada nó <E> {e item; Nó <E> Em seguida; Nó <E> prev; Nó <E> (nó <E> prev, e elemento, nó <e> a seguir) {this.item = element; this.Next = Next; this.prev = prev; }}2. Construção e inicialização do LinkedList
Membro: 3 Variáveis de membro são mantidas no LinkedList para registrar o número de nós na lista vinculada, o antecessor e sucessor de nós
transitório int size = 0; nó transitório <e> primeiro; nó transitório <e> Último;
Construtor: o construtor padrão é construir uma lista de links vazio
public linkedList () {}Ou construção com base em outros contêineres e, posteriormente, escreveremos um construtor para formar uma lista de links ordenados.
public LinkedList (coleção <? Extends e> c) {this (); addall (c);}Aqui está um pouco extra. Para a diferença entre o modificador genérico? Super T e estende -se, veja este artigo sobre a diferença entre Super T e estende -se em genéricos.
3. Operação estrutural do LinkedList
Método de inserção do cabeçalho: isto é, insira um elemento no cabeçalho da lista vinculada
private void linkfirst (e e) {nó final <e> f = primeiro; Nó final <E> newNode = novo nó <> (null, e, f); primeiro = newNode; // julga se é uma lista vinculada vazia se (f == null) last = newNode; else f.prev = newNode; tamanho ++; modCount ++; } Método de inserção da cauda: isto é, insira um elemento no final da lista vinculada
void linkLast (e e) {nó final <E> l = last; Nó final <E> newNode = novo nó <> (l, e, null); last = newNode; if (l == null) primeiro = newNode; else L.Next = newNode; tamanho ++; modCount ++; } Antes de inserir no nó atual: encontre a tração dianteira do nó atual
link void antes (e, nó <e> succ) {// determinar se o nó não está vazio, é claro, nó final <E> pred = succ.prev; Nó final <E> newNode = novo nó <> (pred, e, succ); succ.prev = newNode; // determinar se o nó atual é o primeiro nó se (pred == null) primeiro = newNode; else pred.Next = newNode; tamanho ++; modCount ++; } Método de exclusão de cabeçalho: Exclua o primeiro nó da lista vinculada
privado e Unbinkfirst (nó <e> f) {// assert f == primeiro && f! = null; ELENTO E FINAL = F.Item; Nó final <E> próximo = f.next; f.item = null; f.next = null; // Ajude GC primeiro = a seguir; if (next == null) last = null; else next.prev = null; tamanho--; modCount ++; elemento de retorno; } Método de exclusão de cauda: Exclua o último nó da lista vinculada
privado e UnbinkLast (nó <e> l) {// verifique se L == last e L! = NULL ELEMENTO E FINAL E = L.Item; Nó final <E> prev = l.prev; L.Item = null; l.prev = null; // ajude gc last = prev; if (prev == null) primeiro = nulo; else prev.next = null; tamanho--; modCount ++; elemento de retorno; }4. Mantenha a consistência entre a interface da lista e o deque
A interface da lista permite que o uso de subscritos implemente o acesso aleatório a contêineres e é fácil implementar acesso aleatório a matrizes como essa. Para listas vinculadas, o JDK também usa logicamente a contagem de nós em listas vinculadas para dar a implementação do acesso aleatório
Nó <E> nó (int index) {// Garanta a correção do índice if (índice <(size >> 1)) {node <e> x = primeiro; for (int i = 0; i <index; i ++) x = x.next; retornar x; } else {node <e> x = last; for (int i = tamanho-1; i> índice; i--) x = x.prev; retornar x; }} O índice é a contagem do primeiro tempo, pesquise desde o início. O índice pertence à contagem do segundo tempo e pesquisa do final. Faça pleno uso das características das listas vinculadas de mão dupla.
Portanto, Add (Int Index, T T), GET (INT), Set (int) e outros métodos podem ser facilmente implementados.
O LinkedList implementa a interface DEQUE, ou seja, o LinkedList implementa o método de contêineres de fila de ponta dupla. Aqui estão algum resumo da API.
5. LinkedList Traversal
Como o LinkedList é uma lista vinculada de mão dupla, você pode atravessá-la naturalmente. Como o ArrayList, o LinkedList também tem problemas de falha quando se trata de operação de contêiner com vários threading.
A questão do Fail-Fast foi explicada no artigo anterior, então não vou falar sobre isso aqui.
Em relação aos iteradores, o LinkedList possui um iterador bidirecional de listiter e um iterador inverso descendente. Todos são muito simples. O código -fonte não é analisado
Se você atravessar elementos, o custo do acesso aleatório é relativamente alto.
3. LinkedList, Arraylist, Resumo do Vector
1. LinkedList e ArrayList
Arraylist implementa uma estrutura de dados com base em matrizes dinâmicas, e o LinkedList é baseado em uma estrutura de dados com base em uma lista vinculada.
Para acesso aleatório para obter e definir, o ArrayList se sente melhor do que o LinkedList porque o LinkedList move o ponteiro.
Para operações novas e de exclusão adicionar e remover, o LinedList tem uma vantagem melhor porque a ArrayList precisa mover os dados. Isso depende da situação real. Se apenas uma única peça de dados for inserida ou excluída, a velocidade do Arraylist é melhor que a do LinkedList. No entanto, se os dados forem inseridos aleatoriamente em lotes, a velocidade do LinkedList é muito melhor que a do Arraylist. Como toda vez que uma lista de Arraylist insere dados, é necessário mover o ponto de inserção e todos os dados posteriormente.
2. Arraylist e vetor
O vetor é síncrono de threads, por isso também é seguro para threads, enquanto o ArrayList é o Thread-Asyn, o que não é seguro. Se os fatores de segurança de threads não forem levados em consideração, o Arraylist geralmente será mais eficiente.
Se o número de elementos no conjunto for maior que o comprimento da matriz de conjunto atual, a taxa de crescimento do vetor será 100% do comprimento da matriz atual e a taxa de crescimento da Arraylist é de 50% do comprimento da matriz atual. Se estiver usando dados com quantidades relativamente grandes de dados no conjunto, o uso do vetor tem certas vantagens.
Se você procurar dados em um local especificado, o tempo usado pelo Vector e ArrayList são os mesmos, ambos 0 (1) e você pode usar o Vector e o Arraylist neste momento. Se o tempo gasto movendo os dados em um local especificado for 0 (ni) n, que é o comprimento total, considere usar o linklist, porque é preciso 0 (1) para mover os dados em um local especificado e o tempo gasto consulta os dados em um local especificado é 0 (i).
Arraylist e Vector usam matrizes para armazenar dados. O número de elementos nesta matriz é maior que os dados armazenados reais para adicionar e inserir elementos. Ambos permitem elementos de índice de número de série direto. No entanto, a inserção de dados deve ser projetada para mover elementos da matriz e outras operações de memória; portanto, os dados de índice são rápidos e lentos para inserir dados. O vetor usa o método sincronizado (segura do thread), portanto o desempenho é pior que o Arraylist. O LinkedList usa uma lista vinculada bidirecional para armazenar dados. A indexação de dados de acordo com o número de série requer travessia para frente ou para trás, mas ao inserir dados, apenas os itens frontal e traseiro deste item são gravados, portanto, a inserção de vários graus é mais rápida!