Que coleção Java devo usar?

Nesta pergunta Como posso selecionar eficientemente um contêiner da Biblioteca Padrão no C ++ 11? é um streamgrama útil para usar ao escolher collections C ++.

Eu pensei que esse era um recurso útil para pessoas que não tinham certeza de qual coleção deveriam usar, então tentei encontrar um streamgrama semelhante para Java e não consegui.

Quais resources 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?

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

Este streamgrama não tenta cobrir itens como access sincronizado, segurança de encadeamento, etc. ou as collections legadas, mas abrange os 3 conjuntos padrão, 3 mapas padrão e 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 a essa pergunta ou a essa resposta.

Outros resources

Provavelmente, a referência mais útil é a seguinte página da documentação do Oracle que descreve cada Coleção .

HashSet vs TreeSet

Há uma discussão detalhada de quando usar o HashSet ou TreeSet aqui: Hashset vs Treeset

ArrayList vs LinkedList

Discussão detalhada: quando usar o LinkedList over ArrayList?

Resumo das principais collections não simultâneas e não sincronizadas

Collection : Uma interface que representa uma “mala” não ordenada de itens, chamada “elementos”. O elemento “next” é indefinido (random).

  • Set : Uma interface que representa uma Collection sem duplicatas.
    • HashSet : Um Set apoiado por uma Hashtable . Utilização de memory mais rápida e menor, quando a encomenda não é importante.
    • LinkedHashSet : um HashSet com a adição de uma linked list para associar elementos no pedido de inserção . O elemento “next” é o elemento inserido mais recentemente.
    • TreeSet : Um Set onde os elementos são ordenados por um Comparator (normalmente ordenação natural ). Uso de memory mais lento e maior, mas necessário para ordenação baseada em comparador.
    • EnumSet : Um conjunto extremamente rápido e eficiente personalizado para um único tipo de enumeração.
  • List : Uma interface que representa uma Collection cujos elementos são ordenados e cada um tem um índice numérico que representa sua posição, onde zero é o primeiro elemento e (length - 1) é o último.
    • ArrayList : Uma List apoiada por uma matriz, em que a matriz tem 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 elemento (capacity + 1)-th é adicionado), o array é recriado com uma nova capacidade de (new length * 1.5) – essa recriação é rápida, pois usa System.arrayCopy() . Excluir e inserir / adicionar elementos requer que todos os elementos vizinhos (à direita) sejam deslocados para dentro ou para fora desse espaço. Acessar 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 é preferido em relação a um LinkedList .
    • LinkedList : Uma List apoiada por um conjunto de objects, cada um vinculado a seus vizinhos “anteriores” e “próximos”. Um LinkedList também é uma Queue e Deque . O access aos elementos é feito a partir do primeiro ou último elemento e passando até o índice desejado ser alcançado. Inserção e exclusão, uma vez que o índice desejado é alcançado através da travessia, é uma questão trivial de mapear novamente apenas os links de vizinho imediato para apontar para o novo elemento ou ignorar o elemento excluído agora.
  • Map : uma interface que representa uma Collection que cada elemento possui uma “chave” de identificação – cada elemento é um par de valores-chave.
    • HashMap : Um Map onde as chaves são desordenadas e apoiadas por uma Hashtable .
    • LinkedhashMap : As chaves são ordenadas por ordem de inserção .
    • TreeMap : Um Map onde as chaves são ordenadas por um Comparator (tipicamente ordenação natural).
  • Queue : Uma interface que representa uma Collection qual os elementos são, normalmente, adicionados a uma extremidade e removidos da outra (FIFO: first-in, first-out).
  • Stack : Uma interface que representa uma Collection onde os elementos são, normalmente, adicionados (pressionados) e removidos (estourados) da mesma extremidade (LIFO: last-in, first-out).
  • Deque : abreviação de “double ended queue”, geralmente pronunciada “deck”. Uma lista encadeada que normalmente é adicionada e lida apenas de uma das extremidades (não do meio).

Diagramas básicos de coleção:

diagrama

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

diagrama

Mesmo a imagem mais simples está aqui. Intencionalmente simplificado!

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

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

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

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

    Os dados no conjunto são armazenados principalmente para saber quais dados estão lá.

  4. Mapa é algo como a Lista, mas ao invés de acessar os elementos pelo seu índice inteiro, você os acessa pela sua chave , que é qualquer object. Como o array no PHP 🙂

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

    A principal diferença entre o Set e o Map é que no Set você busca dados por si , enquanto no mapa pela chave .

É simples: se você precisa armazenar valores com 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 você não quiser valores duplicados em sua coleção.

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