Há uma enorme confusão entre esses 3 tipos, e muito das vezes não sabemos qual usar em que situação, e é óbvio que ambas tem suas especificidades, caso contrário não existiram estruturas distintas.
Explicaremos o uso de cada estrutura citada acima, além de mostrar quando cada uma deve ser usada em qual situação, por questões como: performance, utilidade e outras.
Entendendo o SET
Estruturas de dado do tipo “Set” são conhecidas por aceitar apenas valores únicos, ou seja, qualquer valor duplicado inserido em um “Set” será automaticamente excluído, por isso muito cuidado ao escolher uma List ou Set.
O HashSet é o mais rápido de todos, este usa HashTable e seus elementos não são ordenados, a complexidade desta estrutura é O(1), em outras palavras, não importa o quanto você adicione, remova, retire, o tempo de execução sempre será o mesmo. E isso é extremamente crítico em processos onde temos uma situação crítica com milhões de dados a serem inseridos em um Set. Por outro lado, a garantia de continuidade na ordem dos elementos inseridos é zero, ou seja, esse tipo de estrutura é indicada se você precisa apenas garantir a alta performance sem se importar com a ordem com que os elementos estão ordenados.
É importante notar que TreeSet, HashSet e LinkedHashSet implementam a interface “Set”, ou seja, temos os mesmos métodos para as 3 estruturas, o que difere cada uma é a forma com que é implementado o algoritmo, por exemplo, na HashSet já falamos que ela usa HashTable em sua implementação, que por sinal é muito rápido mas não garante a ordenação dos seus elementos. Veja no exemplo da listagem 1 uma implementação do HashSet.
Listagem 1: Usando HashSet
HashSet<Dog> dset = new HashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
Saída: 5 3 2 1 4
O TreeSet implementa um algoritmo conhecido por red-black tree ou árvore rubro-negra. Sua principal característica é que ele é o único Set que implementa a interface SortedSet em vez de Set diretamente, mas de qualquer forma SortedSet implementa Set, assim continuamos tendo os mesmo métodos no TreeSet. Pelo fato de ele implementar SortedSet ele possui elementos ordenados automaticamente, ou seja, independente da ordem que você inserir os elementos, eles serão ordenados. Mas isso tem um custo, a complexidade para os métodos add, remove e contains são bem maiores que do HashSet, são elas O(log (n)), não é bem uma complexidade exponencial mas é bem maior que O(1) que tem seu tempo inalterado.
Por implementar SortedSet o TreeSet oferece mais alguns métodos como: first(), last(), headSet(), tailSet() e etc. Veja no código abaixo um exemplo do TreeSet e sua saída.
Listagem 2: Usando TreeSet
TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
Iterator<Integer> iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
Saída: 12 34 45 63
Temos ainda uma característica a discutir sobre o TreeSet. Veja que funciona normalmente para valores primitivos, como é o caso dos inteiros. Mas se tivéssemos trabalhando com Objetos, como ele saberia como ordenar esses objetos ? Por qual propriedade ele iria ordenar ? Não pense que é a ID, pois nem todo objeto tem a propriedade ID, até mesmo porque ID pode se chamar identificacao, codigo, unique_id, e muitos outros nomes que vem na cabeça do programador.
Listagem 3: Classe Dog
class Dog {
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
}
Suponha a classe Dog acima, e agora vamos tentar aplicar o TreeSet nela.
Listagem 4: Aplicando TreeSet na classe Dog
public class TestTreeSet {
public static void main(String[] args) {
TreeSet<Dog> dset = new TreeSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
Para sua surpresa você receberá um erro em tempo de execução: Exception in thread “main” java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable.
Este erro ocorre por um fato simples: Como o TreeSet vai ordenar uma lista de Dog's se não dissermos a ele por onde ordenar ? Temos então que implementar a interface Comparable, que obrigatoriamente nos fara implementar o método “compareTo”. É através deste método que diremos como o TreeSet deve ordenar nosso Objeto em questão.
Listagem 5: Classe Dog implementando Comparable
class Dog implements Comparable<Dog>{
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
@Override
public int compareTo(Dog o) {
return size - o.size;
}
}
Agora sim, podemos usar o TreeSet que duro será ordenado automaticamente, e a saída da listagem 4 será: 1 2 3.
Enfim, temos a LinkedHashSet que é um meio termo entre HashSet e TreeSet, ou seja, ela nos proporciona um pouco da performance do HashSet e um pouco do poder de ordenação do TreeSet. O LinkedHashSet faz uso também do HashTable com linked list, ou seja, temos aqui a seguinte situação: Os elementos continuam na ordem que são inseridos, diferente do HashSet que “embaralha” tudo. E a complexidade do LinkedHashSet é O(1) para operações básicas.
Listagem 6: Usando LinkedHashSet
LinkedHashSet<Dog> dset = new LinkedHashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
Saída: 2 1 3 5 4
Vimos então que a principal diferença entre as implementos da interface Set está na velocidade e ordenação que elas proporcionam, vamos agora testar a performance de cada um para provar na prática o que explanamos aqui.
Listagem 7: Teste de Performance no TreeSet, HashSet e LinkedHashSet
public static void main(String[] args) {
Random r = new Random();
HashSet<Dog> hashSet = new HashSet<Dog>();
TreeSet<Dog> treeSet = new TreeSet<Dog>();
LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
// start time
long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Dog(x));
}
// end time
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: " + duration);
}
Saída:
Primeiro Lugar: HashSet (como esperado) com tempo de 2244768.
Segundo Lugar: LinkedHashSe com tempo de 2263320 (muito próximo ao HashSet).
Terceiro Lugar: TreeSet com tempo de 3549314 (bem mais lento que os outros por sua ordenação).
É importante salientar uma questão muito importante, nenhuma das implementações da interface Set são thread-safe, ou seja, se você está usando múltiplas threads para acessar o mesmo Set você deve sincronizar esses acessos externamente, pois como dissemos, o Set não o fará. Esse é um ponto fraco para aplicações que trabalham com frequência com múltiplas threads, pois você teria que ficar sincronizando os acessos ao seu Set para garantir a consistência dos dados, porém levando em consideração a rapidez do HashSet ou mesmo a unicidade de elementos do Set como um todo, você deve ponderar se vale a pena deixar de usar o Set por falta de sincronismo nativo.
Conclusão
Esperamos que com este artigo você esteja hábil para escolher entre essas 3 estruturas em situações no qual elas forem adequadas. Podemos ver por exemplo o uso constante do HashSet em mapeamentos OneToMany do Hibernate para garantir uma agilidade na inserção de elementos, que faz-se necessário em aplicações com uma grande quantidade de dados.
Enfim, o uso de ambos deve ser ponderado conforme a necessidade da sua aplicação, ou mesmo deixar de lado o Set e usar outras estruturas como List ou Queue, que também tem suas especificidades para cada situação. Caso deseje entender mais sobre a estrutura interna de cada Set aconselhamos o estudo aprofundado de cada algoritmo usado por estes, por exemplo, como citamos anteriormente o TreeSet usa o algoritmo da árvore rubro-negra.
