Diferenças em vários tipos de listas e colecções.

[Guest id194]

Alguém me consegue explicar de forma simples e sucinta as diferenças entre os tipos de listas/colecções que se encontram a vermelho na seguinte imagem:

http://www.screencast.com/t/0CrtxXBFmb

Preciso mesmo de entender as diferenças entre todos e julgo que se pode dividir isso em 3 partes, ArrayList, Map e Set e depois dentro do Map/Set deve existir diferenças entre o Tree e o Hash. Preciso mesmo de saber porque preciso de saber decidir qual tipo usar nas mias diversas situações no meu trabalho que já só tenho 2 semanas para entregar e sem saber isso, não posso avançar muito mais o trabalho...

[MX+]

Existe um pequeno "exagero" nas opões disponibilizadas em Java, mas a razão é simples. Pelos nomes é fácil lá chegar:

Supondo que sabes a diferença entra uma colecção e uma tabela de símbolos e sabendo que "Set" é igual a"List", mas "Set" não tem elementos repetidos, as únicas diferenças entre o que tens a vermelho é a implementação.

Entre Hash* e Tree*, a primeira utiliza um array (literalmente) que é aumentando consoante a necessidade (Ver HashTables Dinamicas);

o segundo utiliza Árvores (senão estou engando são Red-Black Trees).

De resto a "ArrayList" é uma implementação muito simples de List que é implementada com um Array (igual áqueles do C).

Já agora LinkedList, tal como o nome indica é uma implementação de ListasLigadas.

Este é dos melhores exemplos da utilização de interfaces e classes abstractas em Java 😄 Este polimorfismo é genial.

Cumprimentos

[Baderous]

ArrayList: implementação de um array dinâmico à custa dos arrays normais que são estáticos. Os elementos são indexáveis.

HashSet: conjunto de elementos não ordenados. Os elementos não são indexáveis e não há elementos repetidos.

TreeSet: igual ao anterior, mas estão ordenados.

HashMap: correspondências chave-valor, onde as chaves não estão ordenadas. Uma chave só tem 1 valor, mas o mesmo valor pode ter 2 chaves diferentes.

TreeMap: igual ao anterior mas com as chaves ordenadas.

A ordenação deve ser feita implementando a interface Comparator na classe dos elementos que queres que se mantenham ordenados, devendo ser implementado o método compare.

A estrutura interna dos Hash's é uma tabela de hash, e dos Tree's é uma árvore balanceada.

Resumidamente.

[Knitter]

Uma colecção Map é uma colecção que pode conter elementos na forma de um par chave-valor.

Uma colecção Set é uma colecção que não admite elementos duplicados. A forma como consegue isso é baseada no método equals dos elementos que tentas inserir.

HashMap é um Map cuja estrutura de apoio onde os dados são guardados á basicamente uma HashTabe com a diferença de permitir elementos e chaves nulos, enquanto uma HashTable normal não permite. Uma HashMap não garante qualquer ordem nos elementos.

Uma TreeMap é uma implementação que se baseia em alguns algoritmos conhecidos e que garante a ordem dos elementos através da sua ordem natural, isto é, os elementos devem providenciar uma implementação da interface Comparator.

Um HashSet é um Set com um HashMap para guardar os dados, garantidos a unicidade de todos os elementos adicionados mas não garantido a ordem dos mesmos.

Um TreeSet é um Set onde a ordem é garantida.

Um ArrayList é uma lista onde a estrutura de apoio é um vector em vez dos nós comummente ligados por referencias como acontece noutras implementações.

Resumindo: Um Set não admite elementos repetidos, um Map admite elementos que são identificados por uma chave, pode conter elementos repetidos; Um HashMap/HashSet, não garante ordem nos elementos, são normalmente guardados usando a ordem na qual foram introduzidos; Uma TreeSet/TreeMap, ordena os elementos usando a sua ordem natural, através da interface Comparator.

Um ArrayList pode ser usado se for necessário eliminar o tempo de criação de um nó, dado que usa um vector como apoio, não tem a perda associada à criação de novos nós a cada inserção. Esta colecção também não garante ordem nenhuma para os elementos.

Nenhuma das colecções mencionadas é sincronizada.

[Guest id194]

Ok, acho que já percebi a ideia... Só umas pequenas dúvidas...

1)

No caso do HashSet e TreeSet onde não pode existir elementos duplicados. O que acontece se eu tentar adicionar o mesmo objecto 2 vezes? É lançada uma excepção?

2)

E só para ver se realmente percebi:

Se quero uma simples lista indexada, uso ArrayList.

Se quero algo que me permita identificar um elemento por uma chave uso o HashMap/TreeMap.

Se quero certificar-me que não existem elementos repetidos uso HashSet/TreeSet.

Uso TreeSet/TreeMap quando preciso que os elementos sejam ordenados e HashSet/HashMap quando não preciso.

Correcto?

3)

No entanto uma pequena dúvida... Se o facto de existir elementos repetidos, elementos indexados ou elementos ordenados não for for importante para o problema em questão, devo optar por ArrayList ou HashSet ou TreeSet?

[Baderous]

1) If this set already contains the element, the call leaves the set unchanged and returns false.

2) Sim.

3) Entre HashSet e TreeSet, o Tree é mais eficiente em tudo, excepto na inserção (pois precisa de realizar o algoritmo de ordenação em cada inserção). O Tree é mais equilibrado entre as várias operações do que o Hash. Entre ArrayList e TreeSet, mais uma vez, o TreeSet costuma ter pior desempenho apenas nas funções de inserção, de resto costuma ser melhor.

[Rui Carlos]

3) Entre HashSet e TreeSet, o Tree é mais eficiente em tudo, excepto na inserção (pois precisa de realizar o algoritmo de ordenação em cada inserção). O Tree é mais equilibrado entre as várias operações do que o Hash. Entre ArrayList e TreeSet, mais uma vez, o TreeSet costuma ter pior desempenho apenas nas funções de inserção, de resto costuma ser melhor.

O HashSet também é capaz de ser melhor a aceder aos elementos do que o TreeSet... A menos que a função de hash seja demorada. A nível de inserção, o TreeSet tem a vantagem de o tempo nunca ser muito elevado (mesmo quando precisa de mexer na estrutura da árvore, a complexidade não aumenta). Já o HashSet e o ArrayList, são normalmente bastante eficientes nas inserções, o problema é quando precisam de redimensionar a estrutura.

3)

No entanto uma pequena dúvida... Se o facto de existir elementos repetidos, elementos indexados ou elementos ordenados não for for importante para o problema em questão, devo optar por ArrayList ou HashSet ou TreeSet?

Pelo menos relativamente aos elementos repetidos, deves saber à partida se é ou não permitido existirem...

De resto, podes por exemplo ver quais as operações que vais realizar mais vezes, em ver qual te traz melhor eficiência.

[Knitter]

1)

A primeira situação já te deram. Mas há uma segunda hipótese, a de te teres esquecido de implementar correctamente o método equals que é necessário para um Set. Se não o implementares, vais conseguir inserir tantos objectos iguais quantas referências diferentes tiveres, se o implementares incorrectamente, pode correr o risco de colocares objectos que deviam ser iguais mas o teu método não o considera.

Só menciono porque não é a primeira vez que vejo alguém tentar usar um dessas estruturas sem implementar bem os métodos.

3)

Dado os pontos que indicaste, é irrelevante a escolha. A velocidade das inserções, pesquisas, ordenações, etc., é notada apenas quando a acção penalizadora é executada em grande quantidade. E mesmo assim, a velocidade resultante só poderia ser ponderada se conseguisses testar as duas estruturas e verificasses que o teu programa tem uma penalização quando usa as estruturas, de outra forma é micro-optimização, simplesmente não vale o esforço.

Resultado, usa a estrutura que te der mais jeito, de acordo com o problema. Estou a assumir que neste problema, conseguires espremer uns  nonagésimos de segundo não seja muito relevante 😄

[Guest id194]

Ok, obrigado a todos 😄