HashSet em Java

A classe HashSetimplementa a interface Set, é baseada em uma tabela hash e também é apoiada por uma instância HashMap. Como HashSetos elementos não estão ordenados, não há garantia de que os elementos estarão na mesma ordem após algum tempo. As operações de adição, exclusão e busca serão realizadas em tempo constante, desde que a função hash distribua corretamente os elementos em “buckets”, que serão discutidos posteriormente. Alguns pontos importantes sobre HashSet:

• Porque a classe implementa a interface Set, ela só pode armazenar valores únicos;
• Pode armazenar valores NULL;
• A ordem em que os elementos são adicionados é calculada usando um código hash;
• HashSettambém implementa o Serializablee Cloneable.

Para manter um tempo de execução constante das operações, o tempo gasto em ações com HashSet, deve ser diretamente proporcional ao número de elementos em HashSet+ a “capacidade” da instância integrada HashMap(o número de “cestas”). Portanto, para manter o desempenho, é importante não definir a capacidade inicial muito alta (ou o fator de carga muito baixo). Capacidade inicial – o número inicial de células (“bins”) na tabela hash. Se todas as células forem preenchidas, seu número aumentará automaticamente. O fator de carga é uma medida de quão cheio ele pode estar HashSetantes que sua capacidade aumente automaticamente. Quando o número de elementos HashSettorna-se maior que o produto da capacidade inicial e do fator de carga, a tabela hash é re-hashing (os códigos hash dos elementos são recalculados e a tabela é reconstruída de acordo com os valores obtidos) e o número de células nele é duplicado. Fator de carga = Número de elementos armazenados na tabela / tamanho da tabela hash Por exemplo, se o número inicial de células na tabela for 16 e o ​​fator de carga for 0,75, segue-se que quando o número de células preenchidas atingir 12, o o número de células aumentará automaticamente. O fator de carga e a capacidade inicial são os dois principais fatores que afetam o desempenho do HashSet. Um fator de carga de 0,75 proporciona um bom desempenho em média. Se este parâmetro for aumentado, a carga de memória diminuirá (pois reduzirá o número de operações de re-hashing e reconstrução), mas afetará as operações de acréscimo e pesquisa. Para minimizar o tempo gasto em re-hashing, você precisa escolher o parâmetro de capacidade inicial correto. Se a capacidade inicial for maior que o número máximo de elementos dividido pelo fator de carga, nenhuma operação de re-hashing ocorrerá. Importante: HashSetnão é uma estrutura de dados com sincronização integrada, portanto, se vários threads estiverem trabalhando nela ao mesmo tempo e pelo menos um deles estiver tentando fazer alterações, é necessário fornecer acesso sincronizado de fora. Isso geralmente é feito às custas de outro objeto sincronizado que encapsula o arquivo HashSet. Se não existir tal objeto, então o arquivo Collections.synchronizedSet(). Atualmente, esta é a melhor maneira de evitar operações fora de sincronia com o HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Construtores HashSet:

1. HashSet h = new HashSet(); - construtor padrão. A capacidade inicial padrão é 16, o fator de carga é 0,75.
2. HashSet h = new HashSet(int initialCapacity)– um construtor com uma determinada capacidade inicial. Fator de carga – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— um construtor com uma determinada capacidade inicial e fator de carga.
4. HashSet h = new HashSet(Collection C)– um construtor que adiciona elementos de outra coleção.

O código abaixo demonstra alguns métodos HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Conclusão:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Todas as classes que implementam uma interface Setsão suportadas internamente por implementações Map. HashSetarmazena elementos usando HashMap. Embora HashMapum elemento deva ser representado como um par de valores-chave ao qual adicionar um elemento, HashSetapenas o valor é adicionado. Na verdade, o valor para o qual passamos HashSeté a chave do objeto HashMape uma constante é usada como valor HashMap. Dessa forma, em cada par chave-valor, todas as chaves terão o mesmo valor. Implementação HashSetem java doc:

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

Se você olhar para o método add()y HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Você pode notar que o método add()y HashSetchama o método put()no objeto interno HashMap, passando para ele o elemento a ser adicionado como chave, e a constante PRESENT como valor. O método funciona de maneira semelhante remove(). Ele chama o método remove()do objeto interno HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSeté baseado em uma tabela hash e as operações de adição, exclusão ou pesquisa serão, em média, concluídas em tempo constante (O(1)) . Métodos HashSet:

1. boolean add(E e): adiciona um elemento a HashSet, se não houver nenhum, mas se tal elemento já estiver presente, o método retorna false .
2. void clear():remove todos os elementos de um conjunto.
3. boolean contains(Object o): Retorna verdadeiro se o elemento fornecido estiver presente no conjunto.
4. boolean remove(Object o): Remove o elemento fornecido do conjunto, se presente.
5. Iterator iterator(): Retorna um iterador para os elementos do conjunto.
6. boolean isEmpty(): Retorna verdadeiro se não houver elementos no conjunto.
7. Object clone(): Executa clonagem de superfície HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html