Collections #2: HashSet, LinkedHashSet e TreeSet

Tempo de leitura: menos de 1 minuto

Na semana passada falei um pouco sobre Collection no post Collections #1: ArrayList, LinkedList e Vector. Nesse post dei ênfase a interface List e suas implementações ArrayList, LinkedList e Vector.

Hoje vou falar de outra interface da API Collections, a Set. Você sabe quais as diferenças da Set para List? Quando usar uma ou outra?

Interface Set

A interface java.util.Set extende da interface java.util.Collection como havia dito. Sua principal característica é garantir que nenhum dos elementos contidas nela está duplicado, ou seja, ela garante unicidade dos elementos.

Se comparado com a List, a velocidade na pesquisa de dados é mais rápida, no entanto a inserção é mais lenta. O Set não é posicional, não existe a necessidade de especificar a posição a qual você deseja adicionar o elemento, também não possui o método get(<index>), sendo assim, não é possível obter o elemento através do índice.

Como disse, Set não aceita valores duplicados, ao inserir um elemento existente o mesmo não será adicionado. Entenda-se objetos que tenham o mesmo código hash (retornado pelo método hashCode()) e que retornem verdadeiro na comparação feita pelo método equals().

As implementações de Set são:

HashSet
LinkedHashSet
TreeSet

HashSet

O HashSet, é com certeza a implementação de Set mais utilizada, é sempre a primeira que vem a cabeça quando precisamos criar uma coleção sem duplicatas.

Um HashSet não possui ordenação, a ordem de saída de um elemento não é a mesma da entrada, como acontece no ArrayList. Também não aceita elementos nulos, caso isso aconteça, o elemento não será inserido. HashSet tem boa velocidade no acesso, leitura e alteração de dados e não é sincronizada (thread-safe).

Esta implementação é usada no mapeado objeto-relacional, pai e filho. Quando existe uma relação One-to-Many entre duas tabelas, usando o Hibernate por exemplo, a tabela filho será mapeado como um Set no objeto pai, o Hibernate por sua vez, devolverá uma instância de HashSet.

Dada as principais características dos HashSet, podemos afirmar que caso você necessite e unicidade de elementos e alta performance ao trabalhar com coleção de dados, essa é a escolha correta.

Para acessar um elemento no HashSet, será necessário itera-lo. O jeito mais usando para iterar um Set é usando o comando while, no entanto, também é possível iterar usando o comando for. Vejamos os exemplos:

[code language=”java”]
//while
Set<String> set = …
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next());
}

// for
for(Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
System.out.print(iterator.next());
}
[/code]

TreeSet

Agora, caso o que você precise seja mesmo um coleção de objetos que tenha a garantia de unicidade (não duplica), mas que precise ser ordenado, então talvez você deva usar o TreeSet.

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. SortedSet extende Set, assim TreeSet possui os mesmo métodos de leitura e escrita do HashSet.

Nesta implementação os elementos são ordenados automaticamente, ou seja, a ordem que você insere os registros não é importante, no entanto o acesso aos elementos é ordenado.

Mas isso tem um custo, os métodos add, remove e contains são bem maiores e mais complexos que do HashSet, sua complexidade é O(log (n)), enquanto o HashSet é O(1).

Nota: O site Codility (site que aplica teste de lógica de programação), já falei sobre ele nesse post, disponibiliza um PDF muito legal sobre complexidade de algorítimos, caso tenha interesse em conhecer mais, clique aqui!

Outro ponto importante é que, os elementos inseridos neste coleção, devem implementar a interface Comparable, e não podem ser nulo, caso contrário será lançado NullPointerException.

A interface SortedSet oferece mais alguns métodos interessantes, tais como:

first();
last();
headSet();
tailSet().

Para ver na prática a diferença, nada melhor que testar.

[code language=”java” highlight=”40,41,42″]
@Test
public void teste() {
final List<Set<Integer>> sets = new ArrayList<Set<Integer>>() {
{
add(new HashSet<Integer>());
add(new TreeSet<Integer>());
}
};
for (Set<Integer> set : sets) {
final String nomeImplemetacao = set.getClass().getSimpleName();
// add
long inicio = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
set.add(i);
}
long fim = System.currentTimeMillis();
long duration = fim – inicio;
System.out.println(nomeImplemetacao + " add: " + duration);

// contains
inicio = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
set.contains(i);
}
fim = System.currentTimeMillis();
duration = fim – inicio;
System.out.println(nomeImplemetacao + " contains: " + duration);

// remove
inicio = System.currentTimeMillis();
for (int i = 999999; i >= 0; i–) {
set.remove(i);
}
fim = System.currentTimeMillis();
duration = fim – inicio;
System.out.println(nomeImplemetacao + " remove: " + duration);
}
}
// Saídas:
// HashSet add: 136
// HashSet contains: 39
// HashSet remove: 56
// TreeSet add: 305
// TreeSet contains: 136
// TreeSet remove: 1596 [/code]

Em todas as operações o HashSet é mais performático que o TreeSet. Por tanto, é importante analisar bem antes de escolher a implementação para Set.

LinkedHashSet

Por fim, temos o implementação LinkedHashSet. Ela é um meio termo entre HashSet e TreeSet, ou seja, ela nos proporciona uma boa performance e é pode ser ordenada.

No LinkedHashSet os elementos continuam na ordem que são inseridos, diferente do HashSet que “embaralha” tudo, é parecido com ArrayList.

Sua a complexidade também é O(1) para operações básicas, sendo assim, adicionar (add), remover (remove) e verificar (contains), tem performace semelhante ao HashSet.

Quando precisar de um Set ordenado, sugiro o uso do LinkedHashSet, pois tem boa performance e ainda sim poder ser ordenada.

Vejamos agora a comparação de performance de todas as implementaçãoes de Set:

[code language=”java” highlight=”47,48,49″]
@Test
public void teste() {
final List<Set<Integer>> sets = new ArrayList<Set<Integer>>() {
{
add(new HashSet<Integer>());
add(new TreeSet<Integer>());
add(new LinkedHashSet<Integer>());
}
};
for (Set<Integer> set : sets) {
final String nomeImplemetacao = set.getClass().getSimpleName();
// add
long inicio = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
set.add(i);
}
long fim = System.currentTimeMillis();
long duration = fim – inicio;
System.out.println(nomeImplemetacao + " add: " + duration);

Para concluir, nenhuma das implementações da interface Set são thread-safe, caso você use múltiplas threads acessando o mesmo Set você necessitará sincronizar o acesso. Fique atento!

Até mais galera!