Muitas vezes encontrei essas perguntas durante as entrevistas no passado. Infelizmente, tenho vergonha, a fundação é muito pobre, não há como me sentir prejudicada
Agora, temos que falar sobre as diferenças e conexões entre esses três: esses três implementam a interface da lista, todos têm métodos definidos na interface da lista e também têm métodos da interface de coleta;
Arraylist: usa o método da matriz para armazenar dados, consulta e velocidade de modificação são rápidos, mas a velocidade de adição e exclusão é lenta;
LinkedList: usa o método da lista vinculada para armazenar dados, a velocidade de consulta e modificação é lenta, mas a velocidade de adição e exclusão é rápida.
Vetor: Ele também usa matrizes para armazenamento. iteradores, enumerações, get (int index) e indexOf (índice int), mas o ArrayList não possui enumerações
Arraylist e Vector Use matrizes para armazenar dados. Operações, portanto, os dados do índice são inseridos rapidamente. ou travessia para trás, mas apenas este item é necessário ao inserir dados.
Tabelas lineares, listas vinculadas e tabelas de hash são usadas estruturas de dados. Ao desenvolver Java, o JDK nos forneceu uma série de classes correspondentes para implementar estruturas de dados básicas. 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 └setMap ├Hashtable ├Hashmap └WeakHashmap
Interface de coleção
A coleção é a interface de coleta mais básica. 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.
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 há um construtor de parâmetros de coleção é usado para criar uma nova coleção, esta nova coleção e passagem. mesmo elemento. 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 ();
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 a interface de coleta necessária, a lista também fornece um método ListIterator (), que retorna uma interface do Listiterator. Exclua, defina elementos e também pode 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. O iterador criado pelo vetor, embora o iterador criado pelo ArrayList, seja a mesma interface que o iterador criado pelo ArrayList, porque o vetor é sincronizado, quando um iterador é criado e está sendo usado, outro segmento altera o status do vetor (por exemplo, adicionando ou remoção de alguns) neste momento, a concorrente de ModificationException será lançada quando o método do iterador for chamado, então a exceção deve ser capturada.
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, causando objeto.equals (objeto) = true 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.
Classe de hashtable
Hashtable herda a interface do mapa e implementa 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, use get (chave) para recuperar dados.
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 de classe raiz. ) = Verdadeiro, seu código de hash deve ser o mesmo, mas se os dois objetos são diferentes, seus códigos de hash podem não ser diferentes. de operar tabelas de hash para aumentar.
Se o mesmo objeto possui códigos de hash diferentes, a operação na tabela de hash terá resultados inesperados (o método GET esperado NULL). ao mesmo tempo.
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 FrawHashmap é um hash de hash aprimorado que implementa a "referência fraca" à chave.
Resumir
Se a pilha, a fila e outras operações estão envolvidas, considere usar a lista.
Se o programa estiver em um ambiente de thread único ou o acesso estiver apenas em um thread, considerando as classes assíncronas, é mais eficiente.
Preste atenção especial à operação das tabelas de hash.
Tente retornar a interface em vez do tipo real, como retornar uma lista em vez de uma lista de Array. Isto é para programação abstrata.
Sincronização
O vetor é síncrono. Alguns métodos nesta classe garantem que os objetos no vetor sejam seguros de threads. Arraylist é assíncrono, portanto, os objetos no ArrayList não são seguros de threads. Como os requisitos de sincronização afetarão a eficiência da execução, o uso do ArrayList é uma boa opção se você não precisar de coleções seguras de roscas, o que pode evitar uma sobrecarga desnecessária de desempenho devido à sincronização.
Crescimento de dados
A partir do mecanismo de implementação interna, o ArrayList e o vetor usam matrizes (matriz) para controlar objetos na coleção. Quando você adiciona elementos a esses dois tipos, se o número de elementos exceder o comprimento atual da matriz interna, eles precisam expandir o comprimento da matriz interna 50% originais disso, então, na última vez em que você receber, esta coleção sempre ocupa mais espaço do que você realmente precisa. Portanto, se você deseja salvar muitos dados em uma coleção, há algumas vantagens no uso do vetor, porque você pode evitar sobrecarga desnecessária de recursos, definindo o tamanho da inicialização da coleção.
Modo de uso
No Arraylist e Vector, leva o mesmo tempo para encontrar dados de um local especificado (através do índice) ou adicionar e remover um elemento no final do conjunto. No entanto, se os elementos forem adicionados ou removidos em outras partes do conjunto, o tempo gasto crescerá linearmente: o (ni), onde n representa o número de elementos no conjunto e eu representa a posição do índice em que os elementos aumentam ou removem os elementos. Por que isso está acontecendo? Pensa-se que, ao executar as operações acima, todos os elementos após os elementos i-és e i-és no conjunto devem executar operações de deslocamento. O que tudo isso significa?
Isso significa que você basta procurar elementos em uma posição específica ou apenas adicionar e remover elementos no final da coleção e, em seguida, usar o vetor ou o Arraylist está ok. Se for outra operação, é melhor escolher outra aula de operação de coleção. Por exemplo, o tempo que leva para a classe de coleta de links adicionar ou remover elementos em qualquer posição na coleção é a mesma? é a localização do índice. O Linklist também criará objetos para cada elemento inserido, e tudo o que você precisa entender também trará uma sobrecarga adicional.
Finalmente, no livro Java Practical, Peter Haggar sugere o uso de uma matriz simples (matriz) em vez de vetor ou Arraylist. Isso é especialmente verdadeiro para programas com alta eficiência de execução. Como o uso de matrizes (matriz) evita a sincronização, chamadas de método adicionais e realocação desnecessária de operações espaciais.