Por um longo tempo, a lista de dados que é usada com mais frequência no código é principalmente a lista e todos são Arraylist. Parece que isso é suficiente. Arraylist é uma classe de ferramentas de wrapper usada para implementar matrizes dinâmicas, para que, ao escrever código, você possa entrar e sair, iterar e atravessar, o que é bastante conveniente.
Não sei quando comecei a iniciar lentamente as classes de ferramentas, como hashmap e hashset, geralmente aparecem no código. Deve -se dizer que o Hashmap é mais comum e também é uma pergunta clássica da entrevista, por isso vou ler mais na vida cotidiana. Quando comecei a usá-lo, simplesmente o entendi como uma tabela correspondente de valor-chave e é mais conveniente usar teclas para encontrar dados. Após uma investigação mais aprofundada, descobri
Essa coisa tem alguns segredos, especialmente depois que a nova versão do JDK muda o hashmap para uma árvore, o código é um pouco complicado.
Comecei a usar o Set Menos, mas acidentalmente encontrei um árvore em um código. Descobri que essa classe pode vir com suavidade. Pareceu bastante interessante. Gradualmente, descobri que essa também é uma boa ferramenta.
Se você escrever muito código, sentirá a importância do básico, então aqui escrevo um pequeno artigo para organizar brevemente algum conhecimento sobre a coleção.
Ok, vamos resolver brevemente:
• Lista: isto é, uma lista, que suporta as funções de matrizes e listas vinculadas e geralmente é linear.
• Mapa: é uma tabela de mapeamento, que armazena a relação correspondente entre chaves e valores.
• Conjunto: significa definido, usado principalmente para classificar dados e classificar
Vamos dar uma olhada na lista primeiro
A lista é uma janela para armazenar dados lineares, como: Arraylist para matrizes e LinkedList para listas vinculadas.
Arraylist
Esta é uma lista de matrizes, mas fornece função de expansão automática para realizar a interface da lista. As operações externas são acessadas através do método de declaração de interface, que é seguro e conveniente.
A chave para o ArrayList é a expansão da capacidade automática. A capacidade inicial pode ser definida quando o objeto é inicializado ou a capacidade padrão pode ser medida. Se o tamanho da matriz não estiver particularmente claro, o tamanho inicial não poderá ser especificado. Se estiver claro, um tamanho pode ser especificado, o que reduz o atraso causado pela expansão dinâmica. Falando nisso, precisamos falar sobre como a expansão é implementada. Veja o seguinte código:
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); }Grow é um método que desencadeia a lista de Array ao adicionar elementos ou algumas verificações fáceis. Processo principal:
1. Obtenha a duração da matriz e mova -a para a direita, o que é equivalente a OldCapacity/2, e obtenha o novo comprimento
2. Se esse comprimento for menor que a capacidade mínima, é fácil usá -lo diretamente.
3. Se for maior que o máximo, pegue um valor máximo. Um método HugeCapacity será chamado aqui, principalmente para comparar a picada com max_array_size. Se a pinça for maior que o max_array_size, pegue o número inteiro.max_value; caso contrário, pegue max_array_size. Curiosamente, max_array_size leva o número inteiro.max_value - 8; Não sei qual é o significado de fazer isso
4. Finalmente, ligue para um método de cópia para copiar o número existente em uma nova matriz.
Devido a esse processo de cópia, se a matriz for relativamente grande, a expansão certamente causará atraso. Portanto, se você souber o valor máximo desde o início e é fácil crescer para esse valor, especifique o tamanho ao iniciar a inicialização terá um certo efeito.
LinkedList
Esta é uma classe de ferramentas para listas vinculadas. As vantagens das listas vinculadas são que elas adicionam e excluem as coisas mais rapidamente, mas elas as acharão mais lentamente.
Quanto ao código, parece que nada de especial é que ele está ligado por uma série de ponteiros. Obviamente, o Java usa objetos para criar um objeto de nó. O nó em si aponta para o nó anterior e o próximo nó. Esta é a estrutura da lista vinculada:
classe estática privada nó <E> {e item; Nó <E> Em seguida; Nó <E> prev; Nó (nó <E> prev, e elemento, nó <e> a seguir) {this.item = element; this.Next = Next; this.prev = prev; }}Em seguida, use dois nós para apontar para a cabeça e a cauda e ele está pronto. O seguinte código:
/*** Ponteiro para o primeiro nó. * Invariante: (primeiro == null && last == null) || * (primeiro.prev == null && primeiro.item! = null) */ nó transitório <E> primeiro; /*** Ponteiro para o último nó. * Invariante: (primeiro == null && last == null) || * (last.Next == null && last.item! = null) */ nó transitório <E> last;
Veja uma operação Adicionar:
/*** Links e como último elemento. */ 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 ++; }O passado é:
1. Obtenha o último nó e coloque -o em L
2. Crie um novo nó e busque os dados neste nó. O processo de criação apontará o precesso do novo nó para L, para que ele seja conectado à cadeia.
3. Então o ponto durou para este novo nó
4. Em seguida, determine se L é nulo. Se NULL for nulo, significa que é uma lista vinculada vazia. O novo nó é o primeiro elemento. Dessa forma, o primeiro também deve apontar para o newNode
5. Se não estiver vazio, aponte o próximo de L para o newNode
6. Contador de acumulação
A operação de exclusão também é o nó frontal e traseiro apontando para a operação de movimento deste nó.
Vamos dar uma olhada no mapa
O mapa é uma aplicação de uma tabela de mapeamento para chaves e valores. As principais classes de implementação: HashMap, Hashtable, Treemap
Hashmap e hashtable
Hashmap é o que usa o algoritmo de hash para mapeamento de valor-chave. Hashtable é uma classe segura para roscas com sincronização. Esta é a principal diferença entre eles. O princípio é semelhante e todos são alcançados através da combinação de balde + cadeia. O balde é usado para armazenar teclas e o valor precisa ser armazenado em uma lista vinculada devido à colisão de hash.
• O significado do balde está na eficiência e pode ser posicionado em uma etapa nos cálculos de hash.
• O significado das listas vinculadas é acessar os dados de hash repetido
O princípio específico que escrevi um "Estudo observa: hashtable e hashmap" antes
Mas acabei de ver que o hashmap do JDK1.8 mudou sua estrutura de armazenamento e adota uma estrutura de árvore vermelha e preta. Isso pode resolver a eficiência da pesquisa de lista vinculada? Nenhum estudo detalhado foi realizado.
Treemap
Depois de ler o código de Treemap, descobri que ainda uso a estrutura das árvores, árvores vermelhas e negras. Como as árvores vermelhas e pretas são ordenadas, elas naturalmente têm a função de classificação. Obviamente, você também pode especificar o método de comparação através do comparador para obter classificação específica.
Como a estrutura da árvore é usada para armazenar, será mais problemático adicionar e excluir dados. Vamos dar uma olhada no código Put:
public v put (K -Key, V Valor) {Entrada <K, V> T = ROOT; if (t == null) {compare (chave, chave); // tipo (e possível nulo) Verifique root = nova entrada <> (chave, valor, nulo); tamanho = 1; modCount ++; retornar nulo; } int cmp; Entrada <k, v> pai; // Comparador dividido e comparador de caminhos comparáveis <??? Super K> CPR = Comparador; if (CPR! = null) {do {parent = t; cmp = cpr.comPare (chave, t.key); if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; caso contrário, retorne t.setValue (valor); } while (t! = null); } else {if (key == null) lança novo nullPointerException (); @Suppresswarnings ("desmarcado") comparável <?? Super K> K = (Comparável <? Super K>) Tecla; do {parent = t; cmp = k.compareto (t.key); if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; caso contrário, retorne t.setValue (valor); } while (t! = null); } Entrada <k, v> e = nova entrada <> (chave, valor, pai); if (cmp <0) parent.left = e; else parent.right = e; FixAfterInserção (e); tamanho ++; modCount ++; retornar nulo; }1. Verifique primeiro se o nó raiz existe. Se não existir, significa que é a primeira peça de dados e é usada diretamente como a raiz da árvore.
2. Determine se existe um comparador. Se houver, use o comparador para encontrar o local de armazenamento dos dados. Se o resultado do retorno do comparador for menor que 0, pegue a esquerda e pegue a direita; caso contrário, substitua o valor do nó atual diretamente.
3. Se não houver comparador, a chave será comparada diretamente com a chave do nó. A comparação é a mesma do método anterior.
4. O próximo passo é criar um nó filho no pai encontrado e colocá -lo nos nós da criança esquerda ou direita.
5. FixAfterInserção é para colorir nós
6. Processamento do acumulador
Também será um pouco problemático ao remover os dados. Além de excluir os dados, você também precisa reequilibrar as árvores vermelhas e pretas.
Além disso, a Treemap implementa a interface NavigabableMap <k, v>, por isso também fornece algumas operações de retorno no conjunto de dados.
Finalmente, dê uma olhada no set
O conjunto possui principalmente dois tipos de aplicações: Hashset e TreeSet.
Hashset
O significado literal é muito claro, usando uma coleção de hash. A característica desta coleção é usar o algoritmo de hash para armazenar dados, para que os dados não sejam duplicados e o acesso seja relativamente rápido. Como isso foi feito?
public boolean add (e e) {return map.put (e, presente) == null; }Acontece que existe um objeto de mapa. Vamos ver o que é o mapa?
HashMap transitório privado <e, objeto> mapa;
É um hashmap. Aqueles que conhecem o Hashmap entenderão que esses dados não serão repetidos. Como o próprio objeto é armazenado como uma chave quando depositado, apenas uma cópia existirá no hashmap.
Depois de entender isso e outras coisas, você entenderá muito bem.
Treeset
Esse conjunto é usado para classificar o conjunto, o que significa que, além da capacidade de classificar pesado, também pode ter sua própria função de classificação. Mas depois de olhar para o Código de Treeset, descobri que ele foi implementado no básico do Treemap. Mais precisamente, deve ser uma classe derivada de mapa de navegação. O TreeSet é baseado no TREEMAP sem especificar o mapa por padrão.
public TreeSet () {this (novo Treemap <e, object> ()); }Então, o que podemos prestar mais atenção aqui é como o TreeSet está pesado? Vamos dar uma olhada no método de add:
public boolean add (e e) {return m.put (e, presente) == null; }É um pouco semelhante ao hashset, ambos baseados nos recursos do mapa para obter carga pesada. É realmente simples e eficaz.
O exposto acima é a explicação detalhada do conjunto, lista e mapa em Java que o editor traz para você. Espero que você possa apoiar mais wulin.com ~