Este artigo analisa o código -fonte do ArrayList. Deixe -me falar sobre matrizes antes de analisá -las. As matrizes podem ser uma das primeiras estruturas de dados com as quais entramos em contato. Eles dividem um espaço de endereço contínuo na memória para armazenar elementos. Como opera diretamente a memória, o desempenho das matrizes é melhor que o das classes de coleta, o que é uma grande vantagem do uso de matrizes. Mas sabemos que a matriz tem uma falha fatal, ou seja, o tamanho da matriz deve ser especificado durante a inicialização e o tamanho da matriz não pode ser alterado nas operações subsequentes. Em situações reais, encontramos mais coisas que não sabemos quantos elementos serem armazenados no início, mas esperamos que o contêiner possa expandir automaticamente sua própria capacidade para que possa armazenar mais elementos. A ArrayList pode atender muito bem tais necessidades e pode expandir automaticamente o tamanho para se adaptar ao aumento contínuo dos elementos de armazenamento. Sua camada subjacente é implementada com base em matrizes, por isso possui alguns recursos de matrizes, como encontrar modificações são rápidos e a inserção e a exclusão são lentas. Neste artigo, abordaremos o código -fonte para ver como ele encapsula as matrizes. Primeiro, olhe para suas variáveis de membros e os três principais construtores.
//Default initialization capacity private static final int DEFAULT_CAPACITY = 10;//Empty object array private static final Object[] EMPTY_ELEMENTDATA = {};//Object array private transient Object[] elementData;//Number of collection elements private int size;//Constructor method for passing in initial capacity public ArrayList(int initialCapacity) { super(); if (InitialCapacidade <0) {lança nova ilegalArgumentException ("Capacidade ilegal:"+ InitialCapacidade); } // Crie uma nova matriz de tipo de objeto da capacidade especificada this.ElementData = novo objeto [InitialCapacity];} // construtor sem parâmetros public ArrayList () {super (); // passa uma instância de matriz vazia para elementData this.ElementData = emaillement_elementData;} // Método construtor para passar para a coleção externa public ArrayList (coleção <? Extende e> c) {// segure o elemento de referência da matriz interna passada para a coleção ElementData = c.toarray (); // Atualize o número de elementos do tamanho da coleção = elementData.length; // julga o tipo de referência da matriz e converta a referência a uma referência de matriz de objetos se (elementData.getClass ()! = Object []. Classe) {elementData = Arrays.copyof (elementData, tamanho, objeto []. Classe); }}Você pode ver que a estrutura de armazenamento interna do Arraylist é uma matriz de tipo de objeto, para que possa armazenar elementos de qualquer tipo. Ao construir um ArrayList, se o tamanho inicial for passado, ele criará uma nova matriz de objetos de capacidade especificada. Se o tamanho inicial não estiver definido, ele não alocará o espaço de memória, mas usará uma matriz de objeto vazia e alocará memória quando o elemento realmente for colocado. Vamos dar uma olhada em seus métodos para adicionar, excluir, modificar e pesquisar.
// aumenta (add) public boolean add (e e) {// Verifique se a matriz precisa ser expandida antes de adicionar, o comprimento mínimo da matriz é tamanho + 1 egeCapacityInternal (tamanho + 1); // Adicione o elemento ao final do elemento da matriz [size ++] = e; return true;} // aumenta (insira) public void add (int index, e elemento) {// inserir o intervalo de posição Verifique Rangecheckforadd (index); // Verifique se a capacidade precisa ser expandida, EnsureCapacityInternal (tamanho + 1); // mova o elemento para trás do sistema de posição de inserção.arraycopy (ElementData, Index, ElementData, índice + 1, tamanho - índice); // atribui um novo elemento de valor Data [index] = elemento; size ++;} // excluir public e remover (int index) {// Índice não pode ser maior que o tamanho Rangecheck (índice); modCount ++; E OldValue = ElementData (índice); int numMoved = size - índice - 1; if (numMoved> 0) {// mova o elemento atrás do índice para a frente por um System.ArrayCopy (ElementData, Index+1, ElementData, Index, numMoved); } // referência vazia elementData [-size] = null; return OldValue;} // altere o conjunto público e (int índice, e elemento e) {// Índice não pode ser maior que o tamanho Rangecheck (índice); E OldValue = ElementData (índice); // substitua por um novo elemento elementoData [index] = elemento; return OldValue;} // Verifique public e get (int index) {// Índice não pode ser maior que o tamanho Rangecheck (índice); // retorna o elemento de posição especificado elemento elemento Data (index);} Cada vez que um elemento é adicionado à coleção, primeiro verificará se a capacidade é suficiente, caso contrário, a capacidade será expandida. Os detalhes da expansão da capacidade serão discutidos abaixo. Vamos primeiro olhar para os pontos específicos para prestar atenção ao adicionar, excluir, modificar e verificar.
Adicione (add): Basta adicionar este elemento ao final. Operação rápida.
Adicionar (inserir): a operação é mais lenta porque o elemento por trás da posição de inserção precisa ser movido e a cópia da matriz está envolvida.
Excluir: Como os elementos por trás da posição de exclusão precisam ser avançados, a cópia da matriz também será projetada, para que a operação seja lenta.
Alteração: modifique diretamente os elementos no local especificado, sem envolver o movimento do elemento ou a cópia da matriz, e a operação é rápida.
Verifique: retorne diretamente o elemento da matriz do subscrito especificado e a operação é rápida.
A partir do código -fonte, pode -se observar que, como a pesquisa e a modificação estão diretamente posicionadas no subscrito da matriz, ele não envolve o movimento do elemento e a cópia da matriz, por isso é mais rápido. No entanto, como os elementos precisam ser movidos, isso envolve a cópia da matriz, para que a operação seja mais lenta. Além disso, cada operação de adição também pode executar a expansão da matriz, o que também afetará o desempenho. Vamos dar uma olhada em como a Arraylist expande dinamicamente sua capacidade.
Void privado EnsureCapacityInternal (int mincapacity) {// Se a matriz ainda estiver vazia neste momento se (elementData == emaily_elementData) {// Compare com a capacidade padrão, pegue o valor maior de valor = math.max (default_capacity, minapacity); } // Se a matriz tiver sido inicializada, execute esta etapa, assegure explicitCapacity (MinCapacity);} vazio privado garantirexplicitCapacity (int mincapacity) {modCount ++; // Se a capacidade mínima for maior que o comprimento da matriz, amplie a matriz se (Mincapacity - ElementData.length> 0) {Grow (MinCapacity); }} // Capacidade máxima da coleção Final estática privada int max_array_size = INTEGER.MAX_VALUE - 8; // Aumente o comprimento da matriz Void Private Grow (int mincapacity) {// Obtenha a capacidade original da matriz int anticcapacity = elementData.LengA; // Capacidade da nova matriz, adicione metade na base original int newCapacity = OldCapacity + (OldCapacity >> 1); // Verifique se a nova capacidade é menor que a capacidade mínima se (NewCapacity - MinCapacity <0) {newCapacity = MinCapacity; } // Verifique se a nova capacidade excede a capacidade máxima da matriz se (newCapacity - max_array_size> 0) {newCapacity = hugecapacidade (mincapacidade); } // Copie a matriz original para o novo Array ElementData = Arrays.copyof (ElementData, NewCapacity);} Antes de adicionar elementos, o SurCapacityInternal será chamado para a verificação da capacidade de coleta. Dentro deste método, ele verificará se a matriz interna da coleção atual ainda é uma matriz vazia. Se for, crie uma nova matriz de objetos com o tamanho padrão de 10. Caso contrário, prova que a coleção atual foi inicializada. Em seguida, ligue para garantir o método do ExplicitCapacity para verificar se a capacidade da matriz atual atende à capacidade mínima necessária. Se não estiver satisfeito, chame o método Grow para expandir. No método Grow, você pode ver que cada expansão é aumentar metade do comprimento da matriz original. A expansão é realmente para criar uma nova matriz com maior capacidade, copiar todos os elementos da matriz original para a nova matriz e descartar a matriz original e usar a nova matriz. Até agora, analisamos os métodos mais usados no ArrayList, e alguns dos pontos -chave que vale a pena notar:
1. A implementação subjacente do Arraylist é baseada em matrizes, portanto a pesquisa e a modificação dos subscritos especificadas são mais rápidas, mas as operações de exclusão e inserção são mais lentas.
2. Ao construir uma lista de Array, tente especificar a capacidade o máximo possível de reduzir as operações de cópia da matriz causadas pela expansão. Se você não souber o tamanho, poderá atribuir a capacidade padrão a 10.
3. Antes de adicionar elementos, verifique se a expansão da capacidade é necessária. Cada expansão da capacidade é metade da capacidade original.
4. Toda vez que a operação do subscrito é operada, uma verificação de segurança será executada. Se a matriz estiver fora dos limites, uma exceção será imediatamente lançada.
5. Todos os métodos da Arraylist não são sincronizados, portanto, não é seguro.
6. A análise acima é baseada no JDK1.7, e outras versões terão algumas diferenças, portanto não podem ser generalizadas.
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.