Java HashSet La classe implementa l'interfaccia Set, supportata da una tabella hash che in realtà è un'istanza HashMap. Non viene fornita alcuna garanzia sull'ordine di iterazione degli hash set, il che significa che la classe non garantisce la costanza dell'ordine degli elementi nel tempo. Questa classe consente l'elemento null. La classe offre anche prestazioni costanti nel tempo per le operazioni di base come aggiungere, rimuovere, contenere e ridimensionare, presupponendo che la funzione hash disperda correttamente gli elementi tra i bucket, come vedremo più avanti nell'articolo.
Funzionalità Java HashSet
Alcune caratteristiche importanti di HashSet sono menzionate di seguito:
- Implementa Imposta l'interfaccia .
- La struttura dei dati sottostante per HashSet è Tabella hash .
- Poiché implementa l'interfaccia Set, non sono consentiti valori duplicati.
- Non è garantito che gli oggetti inseriti in HashSet vengano inseriti nello stesso ordine. Gli oggetti vengono inseriti in base al relativo codice hash.
- Gli elementi NULL sono consentiti in HashSet.
- Implementa anche HashSet Serializzabile E Clonabile interfacce.
Dichiarazione di HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
Dove E è il tipo di elementi memorizzati in un HashSet.
Esempio Java di HashSet
Giava
// Java program to illustrate the concept> // of Collection objects storage in a HashSet> import> java.io.*;> import> java.util.*;> > class> CollectionObjectStorage {> > >public> static> void> main(String[] args)> >{> >// Instantiate an object of HashSet> >HashSet set =>new> HashSet();> > >// create ArrayList list1> >ArrayList list1 =>new> ArrayList();> > >// create ArrayList list2> >ArrayList list2 =>new> ArrayList();> > >// Add elements using add method> >list1.add(>1>);> >list1.add(>2>);> >list2.add(>1>);> >list2.add(>2>);> >set.add(list1);> >set.add(list2);> > >// print the set size to understand the> >// internal storage of ArrayList in Set> >System.out.println(set.size());> >}> }> |
panda e intorpiditi
>
>Produzione:
1>
Prima di memorizzare un oggetto, HashSet controlla se esiste una voce esistente utilizzando i metodi hashCode() ed equals(). Nell'esempio precedente, due elenchi sono considerati uguali se contengono gli stessi elementi nello stesso ordine. Quando invochi il codice hash() metodo sui due elenchi, entrambi darebbero lo stesso hash poiché sono uguali.
Nota: HashSet lo fa non memorizzare elementi duplicati , se fornisci due oggetti uguali, memorizza solo il primo, eccolo list1.
La gerarchia di HashSet è la seguente:
Funzionamento interno di un HashSet
Tutte le classi dell'interfaccia Set sono supportate internamente da Map. HashSet utilizza HashMap per archiviare internamente il suo oggetto. Ti starai chiedendo che per inserire un valore in HashMap abbiamo bisogno di una coppia chiave-valore, ma in HashSet stiamo passando solo un valore.
Archiviazione in HashMap: In realtà il valore che inseriamo in HashSet funge da chiave per l'Oggetto della mappa e per il suo valore Java utilizza una variabile costante. Pertanto, nella coppia chiave-valore, tutti i valori saranno gli stessi.
Implementazione di HashSet in Java doc
private transient HashMap map; // Constructor - 1 // All the constructors are internally creating HashMap Object. public HashSet() { // Creating internally backing HashMap object map = new HashMap(); } // Constructor - 2 public HashSet(int initialCapacity) { // Creating internally backing HashMap object map = new HashMap(initialCapacity); } // Dummy value to associate with an Object in Map private static final Object PRESENT = new Object();> Se guardiamo il aggiungere() metodo della classe HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Possiamo notare che il metodo add() della classe HashSet chiama internamente il file Mettere() metodo di backup dell'oggetto HashMap passando l'elemento specificato come chiave e la costante PRESENT come valore. rimuovere() anche il metodo funziona allo stesso modo. Chiama internamente il metodo di rimozione dell'interfaccia Map.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet non memorizza solo oggetti unici ma anche una raccolta unica di oggetti Piace Lista di array , Lista collegata , vettore ,..ecc.
Costruttori della classe HashSet
Per creare un HashSet, dobbiamo creare un oggetto della classe HashSet. La classe HashSet è composta da vari costruttori che permettono l'eventuale creazione dell'HashSet. Di seguito sono riportati i costruttori disponibili in questa classe.
1. HashSet()
Questo costruttore viene utilizzato per creare un oggetto HashSet vuoto in cui la capacità iniziale predefinita è 16 e il fattore di carico predefinito è 0,75. Se desideriamo creare un HashSet vuoto con il nome hs, allora può essere creato come:
HashSet hs = new HashSet();>
2. HashSet(int capacità iniziale)
Questo costruttore viene utilizzato per creare un oggetto HashSet vuoto in cui l'initialCapacity è specificato al momento della creazione dell'oggetto. In questo caso il loadFactor predefinito rimane 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet (int capacità iniziale, float loadFactor)
Questo costruttore viene utilizzato per creare un oggetto HashSet vuoto in cui individualCapacity e loadFactor sono specificati al momento della creazione dell'oggetto.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (raccolta)
Questo costruttore viene utilizzato per creare un oggetto HashSet contenente tutti gli elementi della raccolta specificata. In breve, questo costruttore viene utilizzato quando è necessaria una conversione da qualsiasi oggetto Collection all'oggetto HashSet. Se desideriamo creare un HashSet con il nome hs, possiamo crearlo come:
HashSet hs = new HashSet(Collection C);>
Di seguito è riportata l'implementazione degli argomenti di cui sopra:
Giava
// Java program to Demonstrate Working> // of HashSet Class> > // Importing required classes> import> java.util.*;> > // Main class> // HashSetDemo> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> > >// Creating an empty HashSet> >HashSet h =>new> HashSet();> > >// Adding elements into HashSet> >// using add() method> >h.add(>'India'>);> >h.add(>'Australia'>);> >h.add(>'South Africa'>);> > >// Adding duplicate elements> >h.add(>'India'>);> > >// Displaying the HashSet> >System.out.println(h);> >System.out.println(>'List contains India or not:'> >+ h.contains(>'India'>));> > >// Removing items from HashSet> >// using remove() method> >h.remove(>'Australia'>);> >System.out.println(>'List after removing Australia:'> >+ h);> > >// Display message> >System.out.println(>'Iterating over list:'>);> > >// Iterating over hashSet items> >Iterator i = h.iterator();> > >// Holds true till there is single element remaining> >while> (i.hasNext())> > >// Iterating over elements> >// using next() method> >System.out.println(i.next());> >}> }> |
>
>Produzione:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metodi in HashSet
| METODO | DESCRIZIONE |
|---|---|
| add(E e) | Utilizzato per aggiungere l'elemento specificato se non è presente, se è presente restituisce false. |
| chiaro() | Utilizzato per rimuovere tutti gli elementi dal set. |
| contiene(Oggetto o) | Utilizzato per restituire true se un elemento è presente in un set. |
| rimuovi(Oggetto o) | Utilizzato per rimuovere l'elemento se è presente nell'insieme. |
| iteratore() | Utilizzato per restituire un iteratore sull'elemento nel set. |
| è vuoto() | Utilizzato per verificare se il set è vuoto o meno. Restituisce vero per vuoto e falso per una condizione non vuota per set. |
| misurare() | Utilizzato per restituire la dimensione del set. |
| clone() | Utilizzato per creare una copia superficiale del set. |
Esecuzione di varie operazioni su HashSet
Vediamo come eseguire alcune operazioni utilizzate di frequente sull'HashSet.
1. Aggiunta di elementi in HashSet
Per aggiungere un elemento all'HashSet, possiamo utilizzare il metodo add() . Tuttavia, l'ordine di inserimento non viene mantenuto nell'HashSet. Dobbiamo tenere presente che gli elementi duplicati non sono consentiti e tutti gli elementi duplicati vengono ignorati.
Esempio
Giava
// Java program to Adding Elements to HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // AddingElementsToHashSet> class> GFG {> > >// Method 1> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty HashSet of string entities> >HashSet hs =>new> HashSet();> > >// Adding elements using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> > >// Printing all string el=ntries inside the Set> >System.out.println(>'HashSet elements : '> + hs);> >}> }> |
>
>Produzione:
HashSet elements : [Geek, For, Geeks]>
2. Rimozione di elementi in HashSet
I valori possono essere rimossi dall'HashSet utilizzando il metodoremove().
Esempio
Giava
// Java program Illustrating Removal Of Elements of HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // RemoveElementsOfHashSet> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an> >HashSet hs =>new> HashSet();> > >// Adding elements to above Set> >// using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> >hs.add(>'A'>);> >hs.add(>'B'>);> >hs.add(>'Z'>);> > >// Printing the elements of HashSet elements> >System.out.println(>'Initial HashSet '> + hs);> > >// Removing the element B> >hs.remove(>'B'>);> > >// Printing the updated HashSet elements> >System.out.println(>'After removing element '> + hs);> > >// Returns false if the element is not present> >System.out.println(>'Element AC exists in the Set : '> >+ hs.remove(>'AC'>));> >}> }> |
>
>Produzione:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Iterazione attraverso HashSet
Scorrere gli elementi di HashSet utilizzando il metodo iterator(). Inoltre, il più famoso è usare il file migliorato per il ciclo.
Esempio
Blocco di codice
ProduzioneA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Complessità temporale delle operazioni HashSet: La struttura dati sottostante per HashSet è hashtable. Quindi ammortizza la complessità temporale (media o caso normale) per l'operazione di aggiunta, rimozione e ricerca (contiene il metodo) di HashSet O(1) tempo.
Prestazioni di HashSet
HashSet estende la classe Abstract Set e la implementa Impostato , Clonabile e Serializzabile interfacce dove E è il tipo di elementi mantenuti da questo insieme. La sottoclasse direttamente conosciuta di HashSet è LinkedHashSet .
Ora, per mantenere prestazioni costanti nel tempo, l'iterazione su HashSet richiede un tempo proporzionale alla somma delle dimensioni dell'istanza HashSet (il numero di elementi) più la capacità dell'istanza HashMap di supporto (il numero di bucket). Pertanto, è molto importante non impostare la capacità iniziale troppo alta (o il fattore di carico troppo basso) se le prestazioni di iterazione sono importanti.
- Capacità iniziale: La capacità iniziale indica il numero di bucket quando viene creata la tabella hash (HashSet utilizza internamente la struttura dei dati della tabella hash). Il numero di contenitori verrà automaticamente aumentato se la dimensione corrente si riempie.
- Fattore di carico: Il fattore di carico è una misura del livello di riempimento consentito per l'HashSet prima che la sua capacità venga aumentata automaticamente. Quando il numero di voci nella tabella hash supera il prodotto del fattore di carico e della capacità corrente, la tabella hash viene rieseguita (ovvero, le strutture dati interne vengono ricostruite) in modo che la tabella hash abbia circa il doppio del numero di bucket.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Esempio: Se la capacità interna è 16 e il fattore di carico è 0,75, il numero di contenitori verrà automaticamente aumentato quando la tabella conterrà 12 elementi.
Effetto sulle prestazioni:
Il fattore di carico e la capacità iniziale sono due fattori principali che influenzano le prestazioni delle operazioni HashSet. Un fattore di carico di 0,75 fornisce prestazioni molto efficaci rispetto alla complessità temporale e spaziale. Se aumentiamo il valore del fattore di carico più di quello, il sovraccarico della memoria verrà ridotto (perché diminuirà l'operazione di ricostruzione interna) ma influenzerà l'operazione di aggiunta e ricerca nella tabella hash. Per ridurre l'operazione di ripetizione dovremmo scegliere saggiamente la capacità iniziale. Se la capacità iniziale è maggiore del numero massimo di voci diviso per il fattore di carico, non verrà mai eseguita alcuna operazione di ripetizione dell'hash.
Nota: L'implementazione in un HashSet non è sincronizzata, nel senso che se più thread accedono contemporaneamente a un set di hash e almeno uno dei thread modifica il set, deve essere sincronizzato esternamente. Ciò viene in genere ottenuto mediante la sincronizzazione su alcuni oggetti che incapsulano naturalmente il set. Se non esiste alcun oggetto di questo tipo, il set deve essere racchiuso utilizzando il metodo Collections.synchronizedSet. È meglio farlo al momento della creazione, per impedire l'accesso accidentale e non sincronizzato al set, come mostrato di seguito:
Set s = Collections.synchronizedSet(new HashSet(…));
Metodi utilizzati con HashSet
1. Metodi ereditati dalla classe java.util.AbstractSet
| Metodo | Descrizione |
|---|---|
| equivale() | Utilizzato per verificare l'uguaglianza di un Oggetto con un HashSet e confrontarli. L'elenco restituisce true solo se entrambi gli HashSet contengono gli stessi elementi, indipendentemente dall'ordine. |
| codice hash() | Restituisce il valore del codice hash per questo set. |
| rimuovi tutto(raccolta) | Questo metodo viene utilizzato per rimuovere dalla collezione tutti gli elementi presenti nell'insieme. Questo metodo restituisce true se questo set cambia come risultato della chiamata. |
2. Metodi ereditati dalla classe java.util.AbstractCollection
| METODO | DESCRIZIONE |
|---|---|
| aggiungiTutto(raccolta) | Questo metodo viene utilizzato per aggiungere tutti gli elementi della raccolta menzionata al set esistente. Gli elementi vengono aggiunti in modo casuale senza seguire alcun ordine specifico. |
| contieneTutto(raccolta) | Questo metodo viene utilizzato per verificare se l'insieme contiene o meno tutti gli elementi presenti nella raccolta data. Questo metodo restituisce true se l'insieme contiene tutti gli elementi e restituisce false se manca uno qualsiasi degli elementi. |
| keepAll(raccolta) | Questo metodo viene utilizzato per conservare tutti gli elementi dell'insieme menzionati nella raccolta data. Questo metodo restituisce true se questo set è cambiato come risultato della chiamata. |
| toArray() | Questo metodo viene utilizzato per formare un array degli stessi elementi di quello del Set. |
| accordare() | Il metodo toString() di Java HashSet viene utilizzato per restituire una rappresentazione di stringa degli elementi della raccolta HashSet. |
3. Metodi dichiarati nell'interfaccia java.util.Collection
| METODO | DESCRIZIONE |
|---|---|
| parallelStream() | Restituisce uno Stream possibilmente parallelo con questa raccolta come origine. |
| rimuoviSe?(Filtro predicato) | Rimuove tutti gli elementi di questa raccolta che soddisfano il predicato specificato. |
| flusso() | Restituisce uno stream sequenziale con questa raccolta come origine. |
| toArray?(Generatore IntFunction) | Restituisce un array contenente tutti gli elementi di questa raccolta, utilizzando la funzione generatrice fornita per allocare l'array restituito. |
4. Metodi dichiarati nell'interfaccia java.lang.Iterable
| METODO | DESCRIZIONE |
|---|---|
| forEach?(Azione del consumatore) | Esegue l'azione specificata per ciascun elemento dell'Iterable fino a quando tutti gli elementi non sono stati elaborati o l'azione genera un'eccezione. |
5. Metodi dichiarati nell'interfaccia java.util.Set
| METODO | DESCRIZIONE |
|---|---|
| addAll?(Raccolta c) | Aggiunge tutti gli elementi della raccolta specificata a questo insieme se non sono già presenti (operazione facoltativa). |
| contieneTutto?(Raccolta c) | Restituisce vero se questo insieme contiene tutti gli elementi della raccolta specificata. |
| è uguale a?(Oggetto o) | Confronta l'oggetto specificato con questo set per verificarne l'uguaglianza. |
| codice hash() | Restituisce il valore del codice hash per questo set. |
| rimuovi tutto?(Raccolta c) | Rimuove da questo set tutti gli elementi contenuti nella raccolta specificata (operazione facoltativa). |
| keepAll?(Raccolta c) | Mantiene solo gli elementi di questo set contenuti nella raccolta specificata (operazione facoltativa). |
| toArray() | Restituisce un array contenente tutti gli elementi di questo set. |
| toArray?(T[] a) | Restituisce un array contenente tutti gli elementi di questo set; il tipo di runtime dell'array restituito è quello dell'array specificato. |
Domande frequenti su HashSet in Java
Q1. Cos'è HashSet in Java?
Risposta:
HashSet è un tipo di classe che estende AbstractSet e implementa le interfacce Set.
Q2. Perché viene utilizzato HashSet?
Risposta:
HashSet viene utilizzato per evitare dati duplicati e per trovare valore con il metodo veloce.
Q3. Differenze tra HashSet e HashMap.
Risposta:
| Base ospitare Linux | HashSet | HashMap |
|---|---|---|
| Implementazione | HashSet implementa un'interfaccia Set. | HashMap implementa un'interfaccia storeMap. |
| Duplicati | HashSet non consente valori duplicati. | HashMap memorizza le coppie chiave e valore e non consente chiavi duplicate. Se la chiave è duplicata, la vecchia chiave viene sostituita con il nuovo valore. |
| Numero di oggetti durante la memorizzazione degli oggetti | HashSet richiede solo l'aggiunta di un oggetto (Oggetto o). | HashMap richiede due oggetti put (chiave K, valore V) per aggiungere un elemento all'oggetto HashMap. |
| Valore fittizio | HashSet utilizza internamente HashMap per aggiungere elementi. In HashSet, l'argomento passato nel metodo add(Object) funge da chiave K. Java associa internamente un valore fittizio per ogni valore passato nel metodo add(Object). | HashMap non ha alcun concetto di valore fittizio. |
| Memorizzazione o aggiunta di un meccanismo | HashSet utilizza internamente l'oggetto HashMap per archiviare o aggiungere gli oggetti. | HashMap utilizza internamente l'hashing per archiviare o aggiungere oggetti |
| Più veloce | HashSet è più lento di HashMap. | HashMap è più veloce di HashSet. |
| Inserimento | HashSet utilizza il metodo add() per aggiungere o archiviare dati. | HashMap utilizza il metodo put() per archiviare i dati. |
| Esempio | HashSet è un set, ad es. {1, 2, 3, 4, 5, 6, 7}. | HashMap è una mappa chiave -> coppia valore (chiave-valore), ad es. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Q4. Differenze tra HashSet e TreeSet in Java.
Risposta:
| Base | HashSet | Set di alberi |
|---|---|---|
| La velocità e l'interno implementano l'azione di lancio | Per operazioni come ricerca, inserimento ed eliminazione. In media, per queste operazioni è necessario un tempo costante. HashSet è più veloce di TreeSet. HashSet viene implementato utilizzando una tabella hash. | TreeSet accetta O (Log n) per la ricerca, l'inserimento e l'eliminazione che è superiore a HashSet. Ma TreeSet mantiene i dati ordinati. Inoltre, supporta operazioni come upper() (restituisce l'elemento meno alto), floor(), ceiling(), ecc. Queste operazioni sono anche O(Log n) in TreeSet e non supportate in HashSet. TreeSet è implementato utilizzando un albero di ricerca binario autobilanciante (albero rosso-nero). TreeSet è supportato da TreeMap in Java. |
| Ordinare | Gli elementi in HashSet non sono ordinati. | TreeSet mantiene gli oggetti in ordine definito dal metodo Comparable o Comparator in Java. Per impostazione predefinita, gli elementi TreeSet sono ordinati in ordine crescente. Offre diversi metodi per gestire l'insieme ordinato come first(), last(), headSet(), tailSet(), ecc. |
| Oggetto nullo | HashSet consente l'oggetto null. | TreeSet non consente oggetti null e lancia NullPointerException, perché TreeSet utilizza il metodo compareTo() per confrontare le chiavi e compareTo() lancerà java.lang.NullPointerException. |
| Confronto | HashSet utilizza il metodo equals() per confrontare due oggetti nel Set e per rilevare i duplicati. | TreeSet utilizza il metodo compareTo() per lo stesso scopo. Se equals() e compareTo() non sono coerenti, cioè per due oggetti uguali equals dovrebbe restituire true mentre compareTo() dovrebbe restituire zero, allora interromperà il contratto dell'interfaccia Set e consentirà duplicati nelle implementazioni Set come TreeSet |