Tabelas lineares, listas vinculadas e tabelas de hash são estruturas de dados comumente usadas. Ao desenvolver Java, o JDK nos forneceu uma série de classes correspondentes para implementar estruturas básicas de dados. Essas classes estão todas no pacote java.util. Este artigo tenta explicar aos leitores o papel de cada classe e como usá -los corretamente através de uma descrição simples.
Coleção ├list │✜linkedList │✜ArrayList │└Vector │└Stack └Set Mapa ├Hashtable ├Hashmap └Weakhashmap
Interface de coleção
A coleção é a interface de coleção mais básica. Uma coleção representa um conjunto de objetos, ou seja, os elementos da coleção (elementos). Algumas coleções permitem os mesmos elementos, enquanto outras não. Alguns podem classificar, mas outros não. O Java SDK não fornece classes diretamente herdadas da coleção. As classes fornecidas pelo Java SDK são todas "subinterfaces" herdadas da coleção como List e Set.
Todas as classes que implementam a interface de coleta devem fornecer dois construtores padrão: o construtor sem parâmetros é usado para criar uma coleção vazia, e um construtor de parâmetros de coleção é usado para criar uma nova coleção, que possui os mesmos elementos que a coleção que entra. O último construtor permite que o usuário copie uma coleção.
Como iterar através de todos os elementos de uma coleção? Independentemente do tipo real da coleção, ele suporta um método iterator (), que retorna um iterador e usa esse iterador para acessar cada elemento na coleção um por um.
Os usos típicos são os seguintes:
Iterator it = collection.iterator (); // obtenha um iterador enquanto (it.hasnext ()) {objeto obj = it.next (); // Obtenha o próximo elemento} As duas interfaces derivadas da interface de coleta são listas e definidas.
Interface da lista
A lista é uma coleção ordenada e, usando essa interface, permite controlar com precisão a posição de cada inserção de elemento. Os usuários podem usar índices (a posição dos elementos na lista, semelhante aos subscritos de matriz) para acessar elementos na lista, que é semelhante às matrizes de Java.
Ao contrário do conjunto mencionado abaixo, a lista permite os mesmos elementos.
Além do método iterator () que possui o método ITERator () necessário, a lista também fornece um método listiterator (), que retorna uma interface do listiterator. Comparado com a interface do iterador padrão, o Listiterator possui mais métodos como Add (), permitindo adicionar, excluir, definir elementos e atravessar para frente ou para trás.
As classes comuns que implementam interfaces de lista incluem LinkedList, ArrayList, Vector e Stack.
Classe LinkedList
O LinkedList implementa a interface da lista, permitindo elementos nulos. Além disso, o LinkedList fornece métodos adicionais, remover e inserir no cabeçalho ou na cauda do LinkedList. Essas operações permitem que o LinkedList seja usado como pilha, fila ou uma fila de duas vias.
Observe que o LinkedList não possui um método síncrono. Se vários threads acessarem uma lista ao mesmo tempo, você deverá implementar a sincronização de acesso por si mesmo. Uma solução é construir uma lista síncrona ao criá -la:
Lista de listas = coleções.synchronizedList (new LinkedList (...));
Classe Arraylist
Arraylist implementa matrizes de tamanho variável. Permite todos os elementos, incluindo NULL. Arraylist não é sincronizado.
O tempo de execução do tamanho, isetty, get, métodos definidos é constante. No entanto, a sobrecarga do método Add é uma constante amortizada e leva o tempo O (n) para adicionar n elementos. Os outros métodos têm tempo de execução linear.
Cada instância da Arraylist tem uma capacidade, que é o tamanho da matriz usada para armazenar elementos. Essa capacidade pode aumentar automaticamente à medida que novos elementos são adicionados constantemente, mas o algoritmo de crescimento não é definido. Quando um grande número de elementos precisa ser inserido, o método de segurança pode ser chamado antes de inserir para aumentar a capacidade da lista de array para melhorar a eficiência da inserção.
Como o LinkedList, o ArrayList também não é sincronizado.
Classe vetorial
O vetor é muito semelhante ao Arraylist, mas o vetor é síncrono. Embora o iterador criado pelo vetor seja a mesma interface que o iterador criado pelo ArrayList, porque o vetor é sincronizado, quando um iterador é criado e está sendo usado, outro encadeamento altera o status do vetor (por exemplo, adicionando ou removendo alguns elementos), a exceção é a que a exceção será atingida.
Classe de pilha
A pilha herda do Vector, implementando uma pilha de primeira saída. A pilha fornece 5 métodos adicionais para permitir que o vetor seja usado como uma pilha. Os métodos básicos de push e pop, e o método Peek colocam os elementos na parte superior da pilha, o método vazio testa se a pilha está vazia e o método de pesquisa detecta a posição de um elemento na pilha. A pilha é criada e é uma pilha vazia.
Definir interface
O Set é uma coleção que não contém elementos duplicados, ou seja, quaisquer dois elementos E1 e E2 têm E1.Equals (E2) = Falso, e o conjunto possui no máximo um elemento nulo.
Obviamente, o construtor do set tem uma restrição e o parâmetro de coleta aprovado não pode conter elementos duplicados.
Observação: objetos mutáveis devem ser operados com cuidado. Se um elemento mutável em um conjunto mudar seu próprio estado, ele causa objeto.equals (objeto) = verdadeiro para causar alguns problemas.
Interface do mapa
Observe que o MAP não herda a interface de coleta e o MAP fornece um mapeamento de chave para valor. Um mapa não pode conter a mesma chave e cada tecla pode mapear apenas um valor. A interface do mapa fornece três tipos de visualizações da coleção. O conteúdo do mapa pode ser considerado como um conjunto de coleções de chaves, um conjunto de coleções de valor ou um conjunto de mapeamentos de valor-chave.
Classe de hashtable
Hashtable implementa a interface do mapa para implementar uma tabela de hash com um mapeamento de valor-chave. Qualquer objeto não nulo pode ser usado como chave ou valor.
Use put (chave, valor) para adicionar dados, usar get (chave) para recuperar dados. A sobrecarga de tempo dessas duas operações básicas é constante.
A hashtable ajusta o desempenho através da capacidade inicial e dos parâmetros do fator de carga. Geralmente, o fator de carga padrão 0,75 pode alcançar melhor o equilíbrio de tempo e espaço. Aumentar o fator de carga pode economizar espaço, mas o tempo de pesquisa correspondente aumentará, o que afetará operações como GET e PUT.
Um exemplo simples de usar uma hashtable é o seguinte: Coloque 1, 2 e 3 em uma hashtable, e suas chaves são "um", "dois", "três", respectivamente:
Hashtable números = new hashtable ();
números.put ("One", novo número inteiro (1));
números.put ("dois", novo inteiro (2));
números.put ("três", novo inteiro (3));
Para retirar um número, como 2, use a tecla correspondente:
Número inteiro n = (número inteiro ).get ("dois");
System.out.println ("dois =" + n);
Como um objeto como chave determinará a posição do valor correspondente calculando sua função de hash, qualquer objeto como uma chave deve implementar os métodos HashCode e é igual a. Os métodos HashCode e Equals herdam do objeto da classe raiz. Se você usar uma classe personalizada como chave, tenha muito cuidado. De acordo com a definição da função de hash, se os dois objetos forem iguais, ou seja, obj1.equals (obj2) = true, seu código de hash deverá ser o mesmo, mas se os dois objetos forem diferentes, seus códigos de hash podem não ser diferentes. Se os códigos de hash de dois objetos diferentes forem iguais, esse fenômeno será chamado de conflito. O conflito aumentará a sobrecarga de tempo da operação da tabela de hash. Portanto, tente definir o método hashcode () para acelerar a operação da tabela de hash.
Se o mesmo objeto tiver códigos de hash diferentes, a operação na tabela de hash terá resultados inesperados (o método GET esperado retorna nulo). Para evitar esse problema, você só precisa se lembrar de uma coisa: você deve reescrever o método Equals Method and Hashcode ao mesmo tempo, em vez de apenas escrever um deles.
A hashtable é sincronizada.
Classe Hashmap
O hashmap é semelhante ao hashtable, a diferença é que o hashmap é assíncrono e permite nulo, ou seja, valor nulo e chave nula. , mas quando o hashmap é considerado uma coleção (o método valores () pode retornar uma coleção), seu tempo de suboperação iterativo é proporcional à capacidade do hashmap. Portanto, se o desempenho das operações de iteração for muito importante, não defina a capacidade de inicialização do hashmap para ser muito alta ou o fator de carga é muito baixo.
Classe de fracoshashmap
O fracoHashmap é um hashmap aprimorado que implementa "referência fraca" à chave. Se uma chave não for mais referenciada externamente, a chave poderá ser reciclada pelo GC.
Resumir
Se a pilha, a fila e outras operações estiverem envolvidas, considere usar a lista. Para elementos que precisam ser inseridos e excluídos rapidamente, você deve usar o LinkedList. Se os elementos precisarem ser acessados rapidamente, você deve usar o ArrayList.
Pacote de classe java.util.Collections
A classe Java.util.Collections contém muitos métodos úteis que podem facilitar o trabalho dos programadores, mas esses métodos geralmente não são totalmente utilizados. O Javadoc fornece a descrição mais completa da classe de coleções: "Esta classe contém uma classe estática dedicada que pode operar ou devolver uma coleção.
1.2 métodos incluídos
Iterador, Arraylist, Elements, Buffer, mapa, coleções
Liezi:
importar java.util.arraylist; importar java.util.Collection; importar java.util.Collections; importar java.util.comparator; importar java.util.list; public class collectionsSort {public collectionsSort () {} public static void main (string [] args) {Double Array [] = {111, 111, 23, 456, 231}; Lista da lista = new ArrayList (); Lista li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); //list.add(""+Arraybook]); } duplo arr [] = {111}; for (int j = 0; j <arr.length; j ++) {li.add (novo duplo (arr [j])); }}2. Operações específicas
1) classificar (classificar)
Use o método de classificação para classificar a lista especificada em ordem crescente de acordo com a ordem natural dos elementos. Todos os elementos da lista devem implementar a interface comparável. Todos os elementos desta lista devem ser comparados entre si usando o comparador especificado
matriz dupla [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções.sort (lista); for (int i = 0; i <Array.Length; i ++) {System.out.println (li.get (i)); } // Resultado: 112,111,23,456,2312) Shuffling
O algoritmo de arranjo híbrido faz exatamente do tipo oposto: interrompe quaisquer permutações que possam ser encontradas em uma lista. Ou seja, a lista é reorganizada com base na entrada da fonte aleatória, esse arranjo tem a mesma possibilidade (assumindo que a fonte aleatória seja justa). Esse algoritmo é muito útil na implementação de um jogo de sorte. Por exemplo, ele pode ser usado para misturar uma lista de objetos de cartão que representam um baralho de cartas. Além disso, também é muito útil ao gerar casos de teste.
Coleções. for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções.Shuffle (List); for (int i = 0; i <Array.Length; i ++) {System.out.println (li.get (i)); } // Resultado: 112,111,23,456,2313) reverso
Use o método reverso para classificar a lista especificada em ordem decrescente de acordo com a ordem natural dos elementos.
Coleções. for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções. reverso (lista); for (int i = 0; i <Array.Length; i ++) {System.out.println (li.get (i)); } // Resultado: 231.456,23,111,112 4) Substitua todos os elementos na lista especificada pelo elemento especificado. String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <str.Length; j ++) {li.add (new String (str [j])); } Coleções.fill (li, "aaa"); for (int i = 0; i <li.size (); i ++) {System.out.println ("List [" + i + "] =" + li.get (i)); } // Resultado: AAA, AAA, AAA, AAA5) Cópia (cópia)
Use dois parâmetros, uma lista de destino e uma lista de origem, para copiar o elemento de origem para o destino e substituir seu conteúdo. A lista de destino é pelo menos tanto quanto a fonte. Se for mais longo, os elementos restantes na lista de destino não serão afetados.
Coleções.
matriz dupla [] = {112, 111, 23, 456, 231}; Lista da lista = new ArrayList (); Lista li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } duplo arr [] = {1131,333}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (novo duplo (arr [j])); } Coleções.copy (list, li); for (int i = 0; i <list.size (); i ++) {System.out.println ("List [" + i + "] =" + list.get (i)); } // Resultado: 1131,333,23,456.2316) Retorna o menor elemento nas coleções (min)
Retorna o menor elemento da coleção fornecida de acordo com a ordem em que o comparador especificado é gerado. Todos os elementos da coleção devem ser comparados entre si através do comparador especificado
Coleções. Lista da lista = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções.Min (lista); for (int i = 0; i <list.size (); i ++) {System.out.println ("List [" + i + "] =" + list.get (i)); } // Resultado: 237) Retorna o menor elemento (max) nas coleções
Retorna o elemento máximo da coleção fornecida de acordo com a ordem em que o comparador especificado é gerado. Todos os elementos da coleção devem ser comparados entre si através do comparador especificado
Coleções.max (list) matriz dupla [] = {112, 111, 23, 456, 231}; Lista da lista = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções.max (lista); for (int i = 0; i <list.size (); i ++) {System.out.println ("List [" + i + "] =" + list.get (i)); } // Resultado: 4568) LastIndexofsublist
Retorna a posição inicial da lista de destino especificada que apareceu pela última vez na lista de origem especificada
int conting = collection.LastIndexOfSublist (List, LI); matriz dupla [] = {112, 111, 23, 456, 231}; Lista da lista = new ArrayList (); Lista li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } duplo arr [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (novo duplo (arr [j])); } Int location = coleções. LastIndexOfSublist (List, Li); System.out.println ("==="+ locais); // Resultado 39) Indexofsublist
Retorna a posição inicial da primeira vez que a lista de destino especificada aparece na lista de origem especificada
int conting = collection.IndexOfSublist (List, LI); matriz dupla [] = {112, 111, 23, 456, 231}; Lista da lista = new ArrayList (); Lista li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } duplo arr [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (novo duplo (arr [j])); } Int location = collection.IndexOfSublist (List, LI); System.out.println ("==="+ locais); // Resultado 110) Gire
Mova ciclicamente os elementos na lista especificada com base na distância especificada
Coleções.rotate (list, -1);
Se for um número negativo, se move positivamente e se se mover positivamente, se move positivamente.
matriz dupla [] = {112, 111, 23, 456, 231}; Lista da lista = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (novo duplo (matriz [i])); } Coleções.rotate (list, -1); for (int i = 0; i <list.size (); i ++) {System.out.println ("List [" + i + "] =" + list.get (i)); } // Resultado: 111,23,456.231.112O artigo acima discute brevemente a coleta de classes de implementação e o mapa das estruturas de dados comumente usadas em Java. Este é todo o conteúdo que compartilhei com você. Espero que você possa lhe dar uma referência e espero que você possa apoiar mais o wulin.com.