In questo post vedremo come HashSet funziona internamente in Java, che è anche una domanda preferiteJava Collections interview ma prima di entrare nell’implementazione interna di HashSet in Java è importante conoscere due punti su HashSet.
- HashSet in Java memorizza solo valori univoci, ovvero non sono consentiti duplicati.
- HashSet funziona sul concetto di hashing proprio come HashMap in Java, ma il suo funzionamento differisce da HashMap nel modo seguente:
- In HashMap viene aggiunta una coppia (Chiave, Valore) e la funzione hash viene calcolata usando key.
- Dove come nella funzione HashSet hash viene calcolato utilizzando il valore stesso. Si noti che in HashSet abbiamo il metodo add (E e) che prende solo l’elemento da aggiungere come parametro.
Inoltre potresti aver indovinato ormai, dal momento che la funzione hash è calcolata usando il valore, ecco perché solo uniquevalues sono memorizzati nell’HashSet. Se si tenta di memorizzare nuovamente lo stesso elemento, la funzione hash calcolata sarà la stessa, quindi l’elemento verrà sovrascritto.
HashSet utilizza internamente HashMap
Ora tornando all’implementazione interna di HashSet in Java il punto più importante è l’implementazione della classe HashSet utilizza internamente HashMap per memorizzare i suoi elementi.
All’interno dell’HashSet ci sono molti costruttori uno senza alcun parametro e molti altri con capacità iniziale o fattore di carico, ma ognuno di questi costruttori crea una HashMap.Poiché HashSet utilizza internamente HashMap, sapere come funziona HashMap internamente in Java ti aiuterà a capire come funziona HashSet internamente in Java.
HashSet Constructor snippets
Nella classe HashSet in Java puoi vedere che i costruttori della classe creano una HashMap.
/*** Constructs a new, empty set; the backing <tt>HashMap</tt> instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() { map = new HashMap<>();}
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor);}
E la mappa, che viene utilizzata per memorizzare i valori, è definita come
private transient HashMap<E,Object> map;
Nel costruttore, se hai notato, ci sono parametri denominati capacità iniziale e fattore di carico.Per HashSet, la capacità iniziale predefinita è 16, ovvero verrà creato un array (o bucket) di lunghezza 16 e il fattore di carico predefinito è 0,75. Dove il fattore di carico è una misura di quanto è possibile ottenere la tabella hash prima che la sua capacità venga automaticamente aumentata.
Come vengono aggiunti gli elementi – Implementazione interna di HashSet
Ho dichiarato nel punto 2 sopra che HashSet calcola la funzione hash usando il valore stesso e non esiste una coppia (chiave, valore) in HashSet e poi è arrivata l’affermazione che HashSet utilizza internamente HashMap per memorizzare oggetti.Queste due affermazioni possono sembrare contraddittorie poiché i negozi HashMap (chiave, valore) si accoppiano, quindi vediamo come queste due dichiarazioni di contrasto sono vere.
In realtà dal metodo add della classe HashSet viene chiamato il metodo put() di HashMap dove il valore, che deve essere aggiunto nel Set, diventa Chiave e un oggetto costante “PRESENTE” viene utilizzato come valore.
Che OGGI è definito in attuazione HashSet-
// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
E che come metodo è implementato nella classe HashSet –
public boolean add(E e) { return map.put(e, PRESENT)==null;}
Così si può vedere con l’implementazione interna di HashSet è una (chiave, valore) che in realtà è sempre aggiunto.È solo che l’effettivo valore aggiunto per l’HashSet) diventa la chiave e un valore fittizio “PRESENTE” è aggiunto come valore whenstoring in appoggio HashMap.
Ad esempio un’istruzione per aggiungere un elemento a HashSet – set.aggiungi (“Mumbai”); internamente si traduce in mappa.put (“Mumbai”, PRESENTE); e poi aggiunto all’istanza HashMap di supporto.
Una cosa da notare qui è che in HashMap il valore può essere duplicato ma la chiave dovrebbe essere unica. È così che HASHSETSI assicura che al suo interno siano memorizzati solo valori univoci, poiché il valore che deve essere memorizzato in HashSetdiventa la chiave mentre lo memorizza in HashMap.
Come elemento viene rimosso – HashSet implementazione interna
Quando abbiamo bisogno di rimuovere un elemento dal HashSet, internamente di nuovo rimuovere il metodo di HashSetcalls remove(Object key) metodo della HashMap.
Ecco come viene implementato nella classe HashSet.
public boolean remove(Object o) { return map.remove(o)==PRESENT;}
Qui si noti che il metodo remove(Object key) di HashMap restituisce il valore associato alla chiave.Mentre il metodo remove (Object o) dell’HashSet restituisce il valore booleano. Inoltre sappiamo che per ogni valueadded in HashSet, internamente quando viene aggiunto alla HashMap associata, il valore diventa Chiave e il valore è sempre anobject chiamato PRESENT. Pertanto il valore che viene restituito dal metodo remove (Object key) di HashMap è sempre PRESENTE quindi la mappa delle condizioni.rimuovi (o) = = PRESENTE.
Come gli elementi vengono recuperati da HashSet in Java
In HashSet non esiste un metodo get come fornito in Map o List. In HashSet iterator è lì che iteratethrough i valori del Set. Internamente chiamerà il keyset della HashMap, poiché i valori sono memorizzati come keysin HashMap, quindi ciò che otterremo sono i valori memorizzati nell’HashSet.
Ecco come iterator è implementato internamente nell’HashSet in Java.
/*** Returns an iterator over the elements in this set. The elements* are returned in no particular order.** @return an Iterator over the elements in this set* @see ConcurrentModificationException*/public Iterator<E> iterator() { return map.keySet().iterator();}
Punti da notare
- A differenza di HashMap in cui la funzione hash viene calcolata utilizzando la chiave HashSet utilizza il valore stesso per calcolare la funzione hash.
- Poiché la funzione hash viene calcolata utilizzando il valore, è per questo che solo i valori univoci sono memorizzati nell’HashSet.
- HashSet utilizza internamente HashMap per memorizzare i suoi elementi.
- Quando l’elemento viene aggiunto a HashSet utilizzando il metodo add(E e) internamente HashSet chiama il metodo put () della HashMap wherethe valore passato nel metodo add diventa chiave nel metodo put (). Un valore fittizio “PRESENTE” viene passato come valore nel metodo put ().
Raccomandazioni per l’apprendimento (Corsi Udemy)
- Java Programming Masterclass Course
- Java In-Depth: diventa un ingegnere Java completo!
- Spring Framework Master Class Course
- Complete Python Bootcamp Course
- Python for Data Science and Machine Learning
Questo è tutto per questo argomento Come HashSet funziona internamente in Java. Se avete dubbi o suggerimenti per fare si prega di rilasciare un commento. Grazie!
Argomenti Correlati
- Come ArrayList Funziona Internamente in Java
- Come HashMap Funziona Internamente in Java
- Come Funziona la Classe LinkedList Internamente in Java
- LinkedHashSet in Java Con Esempi
- TreeSet in Java Con Esempi
Si può anche come-