Qual Java Collection devo usar?

127

Nesta pergunta Como posso selecionar com eficiência um contêiner da Biblioteca Padrão no C ++ 11? é um fluxograma útil para usar na escolha de coleções C ++.

Eu pensei que este era um recurso útil para pessoas que não têm certeza de qual coleção eles deveriam usar, então tentei encontrar um fluxograma semelhante para Java e não consegui fazê-lo.

Quais recursos e "folhas de dicas" estão disponíveis para ajudar as pessoas a escolher a coleção certa a ser usada ao programar em Java? Como as pessoas sabem quais implementações de Lista, Conjunto e Mapa devem usar?

Tim B
fonte
O livro Java Generics and Collections (Naftalin & Wadler) tem um capítulo sobre isso.
Christophe Roussy

Respostas:

292

Como não consegui encontrar um fluxograma semelhante, decidi fazer um eu mesmo.

Este fluxograma não trata de coisas como acesso sincronizado, segurança de encadeamentos etc. ou coleções herdadas, mas abrange os 3 conjuntos padrão s, os 3 mapas padrão e as 2 listas padrão .

insira a descrição da imagem aqui

Esta imagem foi criada para esta resposta e está licenciada sob uma Licença Internacional Creative Commons Attribution 4.0. A atribuição mais simples é vincular-se a esta pergunta ou a esta resposta.

Outros recursos

Provavelmente, a outra referência mais útil é a página a seguir na documentação da Oracle que descreve cada coleção .

HashSet vs TreeSet

Há uma discussão detalhada de quando usar HashSetou TreeSetaqui: Hashset vs Treeset

ArrayList vs LinkedList

Discussão detalhada: Quando usar o LinkedList sobre o ArrayList?

Tim B
fonte
Agradável! Mas devo discordar de suas decisões LinkedListvs. ArrayListPrimeiro, se a lista é de tamanho significativo, LinkedListé preferível. LinkedListpossui sobrecarga por elemento; portanto, é assintoticamente pior em termos de consumo de memória que um ArrayList. Além disso, se a maior parte do acesso estiver no final da lista, ArrayListé preferível, pois fornece acesso a elementos aleatórios em tempo constante. Acessar o nth elemento de a LinkedListé uma O(n)operação. ... De fato, a decisão de usar uma lista vinculada deve sempre ser "não".
Matt Ball
2
@ MattBall Eu concordo com você em sua maior parte. No entanto, Java LinkedListé uma lista dupla, portanto, o acesso no início e no final é rápido. Você observará que os ramos acima das três perguntas precisam responder sim antes de eu recomendar o uso LinkedList- portanto, em outras palavras, concordo com você que, na maioria dos casos, a resposta é não. Coisas como filas e desenfileiramentos nas quais você está constantemente adicionando e removendo itens das extremidades da área da lista é um bom caso de uso LinkedList.
Tim B
@MattBall O uso de memória é uma situação muito mais complicada, pois enquanto um LinkedListusa mais memória por elemento ... ArrayListnunca libera memória. Isso significa que, se você tiver uma lista que às vezes cresce para um tamanho enorme, mas geralmente é pequena, o ArrayListdesempenho da memória será pior. A sobrecarga de memória em Listsi é geralmente (embora nem sempre) pequena em comparação com a dos elementos que ela contém.
Tim B
Map<K,V>não faz parte dejava.util.collection
Mehraj Malik 02/04
@MehrajMalik Hmm, a rotulagem é ambígua, eu concordo. Eu quis dizer coleção dentro de java.util. ou seja java.util * nome de inserção de recolha aqui *.
Tim B
66

Resumo das principais coleções não simultâneas e não sincronizadas

Collection: Uma interface que representa uma "bolsa" não ordenada de itens, chamada "elementos". O elemento "próximo" é indefinido (aleatório).

  • Set: Uma interface representando a Collectionsem duplicatas.
    • HashSet: A Setapoiado por a Hashtable. Uso de memória mais rápido e menor, quando o pedido não é importante.
    • LinkedHashSet: A HashSetcom a adição de uma lista vinculada para associar elementos na ordem de inserção . O elemento "next" é o próximo elemento inserido mais recentemente.
    • TreeSet: A Setonde os elementos são ordenados por um Comparator(normalmente ordem natural ). Uso de memória maior e mais lento, mas necessário para pedidos baseados em comparador.
    • EnumSet: Um personalizado extremamente rápido e eficiente Setpara um único tipo de enum.
  • List: Uma interface representando a Collectioncujos elementos são ordenados e cada um tem um índice numérico representando sua posição, em que zero é o primeiro elemento e(length - 1) é o último.
    • ArrayList: ListSuportado por uma matriz, em que a matriz possui um comprimento (chamado "capacidade") que é pelo menos tão grande quanto o número de elementos (o "tamanho" da lista). Quando o tamanho excede a capacidade (quando o (capacity + 1)-thelemento é adicionado), a matriz é recriada com uma nova capacidade de (new length * 1.5)- essa recreação é rápida, pois é usada System.arrayCopy(). Excluir e inserir / adicionar elementos requer que todos os elementos vizinhos (à direita) sejam deslocados para dentro ou fora desse espaço. O acesso a qualquer elemento é rápido, pois requer apenas o cálculo (element-zero-address + desired-index * element-size)para encontrar sua localização. Na maioria das situações , um ArrayListé preferível a um LinkedList.
    • LinkedList: Um Listrespaldado por um conjunto de objetos, cada um vinculado a seus vizinhos "anterior" e "próximo". A LinkedListtambém é um Queuee Deque. O acesso aos elementos é feito iniciando no primeiro ou no último elemento e passando até o índice desejado. Inserção e exclusão, uma vez que o índice desejado seja alcançado via travessia, é uma questão trivial de re-mapear apenas os links de vizinhos imediatos para apontar para o novo elemento ou ignorar o elemento agora excluído.
  • Map: Uma interface que representa um Collectionlocal em que cada elemento possui uma "chave" de identificação - cada elemento é um par de valores-chave.
    • HashMap: A Maponde as chaves são desordenadas e apoiadas por a Hashtable.
    • LinkedhashMap: As chaves são ordenadas por ordem de inserção .
    • TreeMap: A Maponde as chaves são ordenadas por um Comparator(normalmente ordem natural).
  • Queue: Uma interface que representa um Collectiononde os elementos são, geralmente, adicionados a uma extremidade e removidos da outra (FIFO: primeiro a entrar, primeiro a sair).
  • Stack: Uma interface que representa um local Collectiononde os elementos são, geralmente, adicionados (enviados) e removidos (exibidos) da mesma extremidade (LIFO: último a entrar, primeiro a sair).
  • Deque: Abreviação de "fila dupla", geralmente pronunciada "deck". Uma lista vinculada que normalmente é adicionada e lida apenas em cada extremidade (não no meio).

Diagramas básicos de coleta:

diagrama

Comparando a inserção de um elemento com um ArrayListe LinkedList:

diagrama

aliteralmind
fonte
2
Melhor em breve verão que se pode obter em qualquer lugar :)
roottraveller
11

Imagem ainda mais simples está aqui. Intencionalmente simplificado!

  1. Coleção é qualquer coisa que contém dados chamados "elementos" (do mesmo tipo). Nada mais específico é assumido.

  2. List é umacoleção indexada de dados em que cada elemento tem um índice. Algo como a matriz, mas mais flexível.

    Os dados da lista mantêm a ordem de inserção.

    Operação típica: obtenha o n-ésimo elemento.

  3. Conjunto é um conjunto de elementos , cada elemento apenas uma vez (os elementos são diferenciados usando suaequals() método

    Os dados no conjunto são armazenados principalmente apenas para saber quais dados existem.

    Operação típica: diga se um elemento está presente na lista.

  4. O mapa é algo como a Lista, mas, em vez de acessar os elementos pelo índice inteiro, você os acessa pela chave , que é qualquer objeto. Como a matriz em PHP :)

    Os dados no mapa são pesquisáveis ​​por sua chave.

    Operação típica: obtenha um elemento por seu ID (onde ID é de qualquer tipo, não apenas intcomo no caso de Lista).

As diferenças

  • Definir e mapear: em Definir, você pesquisa os dados por si mesmos , enquanto no mapa, por sua chave .

  • Lista e Mapa: na Lista, você acessa o elemento pelo intíndice (posição na Lista), enquanto no Mapa pela chave que os de qualquer tipo (normalmente: ID)

  • Listar e definir: na lista, os elementos são vinculados à sua posição e podem ser duplicados, enquanto que em os elementos são apenas "presentes" (não presentes) e são únicos (no significado de equals()ou compareTo()para SortedSet)

Honza Zidek
fonte
1

É simples: se você precisar armazenar valores com as chaves mapeadas para eles, vá para a interface Map, caso contrário, use List para valores que podem ser duplicados e, finalmente, use a interface Set se não desejar valores duplicados em sua coleção.

Aqui está a explicação completa http://javatutorial.net/choose-the-right-java-collection , incluindo fluxograma etc.

filip_j
fonte
1

Mapa

Ao escolher a Map, fiz esta tabela resumindo os recursos de cada uma das dez implementações incluídas no Java 11.

Tabela de implementações de mapas no Java 11, comparando seus recursos

Basil Bourque
fonte
0

Coleções comuns, Coleções comuns insira a descrição da imagem aqui

Aliaksandr Shpak
fonte
-2

Qual Java Collection devo usar?

Depende de qual problema você está tentando resolver ou de quais requisitos você possui.

Exemplos :

  1. Deseja que os elementos sejam classificados enquanto os armazena? HashSet
  2. Deseja que os pares (Chave, Valor) sejam armazenados? HashMap
  3. Deseja que a ordem dos elementos quando inseridos seja preservada? ArrayList, LinkedList
  4. Deseja que as chaves no par (chave, valor) sejam classificadas? - texto forte
  5. Deseja implementar uma pilha para resolver seu problema? - Pilha
  6. Deseja ter acesso FIFO (primeiro a entrar, primeiro a sair)? - Fila
  7. Deseja que apenas elementos UNIQUE sejam armazenados? - HashSet
  8. Deseja permitir a chave como "Nulo" durante o armazenamento (Chave, Valor)? - HashMap
  9. Deseja nenhum valor NULL para o par (Chave, Valor)? HashTable
Aviral Kumar
fonte
Mesmo com o texto forte no item 4 substituído por, digamos, ConcurrentSkipListMap (K, V) , o que essa resposta adiciona ao gráfico de decisão de Tim B , às "descrições de lista curta" de aliteralmind ?
greybeard
Seu primeiro ponto, o HashSet não classifica os dados, mesmo a ordem de inserção não é mantida. Você deve alterá-lo com o TreeSet
Saurabh Mishra