Regra geral para escolher uma implementação de uma coleção Java?

Question

Alguém tem uma boa regra para escolher entre diferentes implementações de interfaces de coleção Java, como List, Map ou Set?

Por exemplo, geralmente por que ou em que casos eu preferiria usar um Vector ou um ArrayList, um Hashtable ou um HashMap?

Answer 1

Sempre tomei essas decisões caso a caso, dependendo do caso de uso, como:

• Preciso que o pedido permaneça?
• Terei chaves/valores nulos?Dúvidas?
• Será acessado por vários threads
• Preciso de um par chave/valor
• Vou precisar de acesso aleatório?

E então eu abro minha útil 5ª edição Java em poucas palavras e compare as cerca de 20 opções.Tem pequenas tabelas no Capítulo cinco para ajudar a descobrir o que é apropriado.

Ok, talvez se eu souber de cara que um simples ArrayList ou HashSet resolverá o problema, não vou pesquisar tudo.;) mas se houver algo remotamente complexo sobre meu uso pretendido, pode apostar que estou no livro.Aliás, achei que Vector deveria ser 'velho' - não o uso há anos.

Answer 2

Eu realmente gosto desta folha de dicas de Sergiy Kovalchuk entrada do blog:

Mais detalhado foi o fluxograma de Alexander Zagniotov, mas infelizmente está offline.

Answer 3

Presumo que você saiba a diferença entre Lista, Conjunto e Mapa pelas respostas acima.Por que você escolheria entre suas classes de implementação é outra coisa.Por exemplo:

Lista:

1. ListaArray é rápido na recuperação, mas lento na inserção.É bom para uma implementação que lê muito, mas não insere/remove muito.Ele mantém seus dados em um bloco contínuo de memória, portanto, sempre que precisar expandir, ele copia todo o array.
2. Lista vinculada é lento na recuperação, mas rápido na inserção.É bom para uma implementação que insere/remove muito, mas não lê muito.Ele não mantém o array inteiro em um bloco contínuo de memória.

Definir:

1. HashSet não garante a ordem da iteração e, portanto, é o mais rápido dos conjuntos.Ele tem alta sobrecarga e é mais lento que ArrayList, portanto você não deve usá-lo, exceto para uma grande quantidade de dados, quando sua velocidade de hashing se tornar um fator.
2. Conjunto de árvores mantém os dados ordenados, portanto é mais lento que HashSet.

Mapa: O desempenho e o comportamento de HashMap e TreeMap são paralelos às implementações de Set.

Vector e Hashtable não devem ser usados.São implementações sincronizadas, antes do lançamento da nova hierarquia de Coleção, portanto lentas.Se a sincronização for necessária, use Collections.synchronizedCollection().

Answer 4

Teoricamente existem Grande-Oh compensações, mas na prática estas quase nunca importam.

Em benchmarks do mundo real, ArrayList desempenho superior LinkedList Mesmo com grandes listas e com operações como "muitas inserções perto da frente". Os acadêmicos ignoram o fato de que os algoritmos reais têm fatores constantes que podem sobrecarregar a curva assintótica.Por exemplo, listas vinculadas exigem uma alocação adicional de objetos para cada nó, o que significa mais lentidão na criação de um nó e características de acesso à memória muito piores.

Minha regra é:

1. Sempre comece com ArrayList e HashSet e HashMap (ou seja,não LinkedList ou TreeMap).
2. As declarações de tipo devem sempre ser uma interface (ou seja,Listar, Definir, Mapear) portanto, se um criador de perfil ou revisão de código provar o contrário, você poderá alterar a implementação sem quebrar nada.

Answer 5

Sobre sua primeira pergunta...

Lista, Mapa e Conjunto têm propósitos diferentes.Sugiro ler sobre o Java Collections Framework em http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

Para ser um pouco mais concreto:

• use List se precisar de uma estrutura de dados semelhante a um array e precisar iterar sobre os elementos
• use Map se precisar de algo como um dicionário
• use um Set se você só precisa decidir se algo pertence ao conjunto ou não.

Sobre sua segunda pergunta...

A principal diferença entre Vector e ArrayList é que o primeiro está sincronizado, o segundo não está sincronizado.Você pode ler mais sobre sincronização em Simultaneidade Java na prática.

A diferença entre Hashtable (observe que T não é letra maiúscula) e HashMap é semelhante, o primeiro é sincronizado, o último não é sincronizado.

Eu diria que não existe uma regra para preferir uma implementação ou outra, isso realmente depende das suas necessidades.

Answer 6

Para os não classificados, a melhor escolha, mais de nove em cada dez vezes, será:ArrayList, HashMap, HashSet.

Vector e Hashtable são sincronizados e, portanto, podem ser um pouco mais lentos.É raro que você queira implementações sincronizadas e, quando o faz, suas interfaces não são suficientemente ricas para que sua sincronização seja útil.No caso do Map, o ConcurrentMap adiciona operações extras para tornar a interface útil.ConcurrentHashMap é uma boa implementação do ConcurrentMap.

LinkedList quase nunca é uma boa ideia.Mesmo se você estiver fazendo muitas inserções e remoções, se estiver usando um índice para indicar a posição, isso exigirá uma iteração na lista para encontrar o nó correto.ArrayList é quase sempre mais rápido.

Para Map e Set, as variantes de hash serão mais rápidas que tree/sorted.Algoritmos hash tendem a ter desempenho O(1), enquanto árvores terão desempenho O(log n).

Answer 7

As listas permitem itens duplicados, enquanto os conjuntos permitem apenas uma instância.

Usarei um mapa sempre que precisar realizar uma pesquisa.

Para implementações específicas, existem variações de mapas e conjuntos que preservam a ordem, mas em grande parte tudo se resume à velocidade.Costumo usar ArrayList para listas razoavelmente pequenas e HashSet para conjuntos razoavelmente pequenos, mas há muitas implementações (incluindo qualquer uma que você mesmo escreva).HashMap é bastante comum para mapas.Qualquer coisa além de 'razoavelmente pequeno' e você terá que começar a se preocupar com a memória, para que isso seja muito mais específico em termos de algoritmos.

Esta página tem grande quantidade de imagens animadas junto com testes de código de exemplo LinkedList vs.ArrayList se você estiver interessado em números concretos.

EDITAR: Espero que os links a seguir demonstrem como essas coisas são apenas itens em uma caixa de ferramentas, você só precisa pensar em quais são suas necessidades:Veja as versões Commons-Collections de Mapa, Lista e Definir.

Answer 8

Conforme sugerido em outras respostas, existem diferentes cenários para usar a coleta correta, dependendo do caso de uso.Estou listando alguns pontos,

Lista de matrizes:

• Na maioria dos casos, você só precisa armazenar ou iterar um "monte de coisas" e depois iterá-las.A iteração é mais rápida porque é baseada em índice.
• Sempre que você cria um ArrayList, uma quantidade fixa de memória é alocada para ele e, uma vez excedida, ele copia todo o array

Lista vinculada:

• Ele usa uma lista duplamente vinculada para que a operação de inserção e exclusão seja rápida, pois apenas adicionará ou removerá um nó.
• A recuperação é lenta, pois terá que percorrer os nós.

HashSet:

• Tomar outras decisões sim ou não sobre um item, por ex."O item é uma palavra de inglês", "o item está no banco de dados?" , "O item está nesta categoria?" etc.

• Lembrar "quais itens você já processou", por ex.ao fazer um rastreamento da web;

HashMap:

• Usado nos casos em que você precisa dizer “para um determinado X, qual é o Y”?Muitas vezes é útil para implementar caches ou índices na memória, ou seja, pares de valores-chave. Por exemplo:Para um determinado ID de usuário, qual é o nome/objeto de usuário em cache?
• Sempre use o HashMap para realizar uma pesquisa.

Vector e Hashtable são sincronizados e, portanto, um pouco mais lentos. Se a sincronização for necessária, use Collections.synchronizedCollection().Verificar Esse para coleções classificadas.Espero que isso tenha ajudado.

Answer 9

Achei Thinking in Java de Bruce Eckel muito útil.Ele compara muito bem as diferentes coleções.Eu costumava manter um diagrama que ele publicou mostrando a herança hereditária na parede do meu cubo como referência rápida.Uma coisa que sugiro que você faça é ter em mente a segurança do thread.Desempenho geralmente significa não ser seguro para threads.

Answer 10

Bem, depende do que você precisa.As diretrizes gerais são:

Lista é uma coleção onde os dados são mantidos em ordem de inserção e cada elemento obtém índice.

Definir é um conjunto de elementos sem duplicação (se você reinserir o mesmo elemento, ele não será adicionado).Os dados não têm noção de ordem.

Mapa Você acessa e escreve seus elementos de dados por sua chave, que pode ser qualquer objeto possível.

Atribuição: https://stackoverflow.com/a/21974362/2811258

Para obter mais informações sobre coleções Java, confira este artigo.