HashSet in Java

La classe HashSetimplementa l'interfaccia Set, è basata su una tabella hash ed è anche supportata da un'istanza HashMap. Poiché HashSetgli elementi non sono ordinati, non vi è alcuna garanzia che dopo un po' di tempo saranno nello stesso ordine. Le operazioni di aggiunta, eliminazione e ricerca verranno eseguite in tempo costante, a condizione che la funzione hash distribuisca correttamente gli elementi in “bucket”, di cui si parlerà in seguito. Alcuni punti importanti su HashSet:

• Perché la classe implementa l'interfaccia Set, può memorizzare solo valori univoci;
• Può memorizzare valori NULL;
• L'ordine in cui vengono aggiunti gli elementi viene calcolato utilizzando un codice hash;
• HashSetimplementa anche il Serializablee Cloneable.

Per mantenere un tempo di esecuzione costante delle operazioni, il tempo impiegato per le azioni con HashSetdeve essere direttamente proporzionale al numero di elementi presenti HashSet+ alla “capacità” dell'istanza integrata HashMap(il numero di “cestini”). Pertanto, per mantenere le prestazioni, è importante non impostare una capacità iniziale troppo alta (o un fattore di carico troppo basso). Capacità iniziale: il numero iniziale di celle ("contenitori") nella tabella hash. Se tutte le celle sono riempite, il loro numero aumenterà automaticamente. Il fattore di carico è una misura di quanto può essere pieno HashSetprima che la sua capacità aumenti automaticamente. Quando il numero di elementi in HashSetdiventa maggiore del prodotto della capacità iniziale e del fattore di carico, la tabella hash viene rieseguita (i codici hash degli elementi vengono ricalcolati e la tabella viene ricostruita in base ai valori ottenuti) e il numero di cellule in esso contenute è raddoppiato. Fattore di carico = Numero di elementi memorizzati nella tabella/dimensione della tabella hash Ad esempio, se il numero iniziale di celle nella tabella è 16 e il fattore di carico è 0,75, ne consegue che quando il numero di celle riempite raggiunge 12, il il numero di celle aumenterà automaticamente. Il fattore di carico e la capacità iniziale sono i due fattori principali che influenzano le prestazioni di HashSet. Un fattore di carico di 0,75 fornisce in media buone prestazioni. Se questo parametro viene aumentato, il carico di memoria verrà ridotto (poiché ridurrà il numero di nuovi hash e ricostruzioni), ma influirà sulle operazioni di aggiunta e ricerca. Per ridurre al minimo il tempo impiegato per il re-hashing, è necessario scegliere il parametro di capacità iniziale corretto. Se la capacità iniziale è maggiore del numero massimo di elementi diviso per il fattore di carico, non verrà eseguita alcuna operazione di re-hashing. Importante: HashSetnon è una struttura dati con sincronizzazione incorporata, quindi se più thread ci lavorano contemporaneamente e almeno uno di loro sta tentando di apportare modifiche, è necessario fornire un accesso sincronizzato dall'esterno. Ciò viene spesso fatto a scapito di un altro oggetto sincronizzato che incapsula il file HashSet. Se non esiste tale oggetto, allora il file Collections.synchronizedSet(). Questo è attualmente il modo migliore per impedire operazioni non sincronizzate con HashSet.

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

Costruttori HashSet:

1. HashSet h = new HashSet(); - costruttore predefinito. La capacità iniziale predefinita è 16, il fattore di carico è 0,75.
2. HashSet h = new HashSet(int initialCapacity)– un costruttore con una data capacità iniziale. Fattore di carico – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— un costruttore con una determinata capacità iniziale e un determinato fattore di carico.
4. HashSet h = new HashSet(Collection C)– un costruttore che aggiunge elementi da un'altra raccolta.

Il codice seguente illustra alcuni metodi 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());
    }
}

Conclusione:

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

Tutte le classi che implementano un'interfaccia Setsono supportate internamente dalle implementazioni Map. HashSetmemorizza gli elementi utilizzando HashMap. Sebbene HashMapun elemento debba essere rappresentato come una coppia chiave-valore a cui aggiungere un elemento, HashSetviene aggiunto solo il valore. Infatti, il valore a cui passiamo HashSetè la chiave dell'oggetto HashMape come valore viene utilizzata una costante HashMap. In questo modo, in ogni coppia chiave-valore, tutte le chiavi avranno lo stesso valore. Implementazione HashSetin 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 guardi il metodo add()y HashSet:

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

Puoi notare che il metodo add()y HashSetchiama il metodo put()sull'oggetto interno HashMap, passandogli l'elemento da aggiungere come chiave e la costante PRESENT come valore. Il metodo funziona in modo simile remove(). Chiama il metodo remove()dell'oggetto interno HashMap:

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

HashSetè basato su una tabella hash e le operazioni di aggiunta, eliminazione o ricerca verranno, in media, completate in un tempo costante (O(1)) . Metodi HashSet:

1. boolean add(E e): aggiunge un elemento a HashSet, se non ce n'è, ma se tale elemento è già presente, il metodo restituisce false .
2. void clear():rimuove tutti gli elementi da un set.
3. boolean contains(Object o): Restituisce vero se l'elemento dato è presente nell'insieme.
4. boolean remove(Object o): Rimuove l'elemento indicato dall'insieme, se presente.
5. Iterator iterator(): Restituisce un iteratore per gli elementi del set.
6. boolean isEmpty(): Restituisce vero se non ci sono elementi nell'insieme.
7. Object clone(): esegue la clonazione della superficie HashSet.

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