Java HashSet klasse implementerer Set-grensesnittet, støttet av en hash-tabell som faktisk er en HashMap-forekomst. Det gis ingen garanti for iterasjonsrekkefølgen til hashsettene, noe som betyr at klassen ikke garanterer den konstante rekkefølgen av elementer over tid. Denne klassen tillater null-elementet. Klassen tilbyr også konstant tidsytelse for de grunnleggende operasjonene som legg til, fjern, inneholder og størrelse, forutsatt at hash-funksjonen sprer elementene riktig blant bøttene, noe vi skal se videre i artikkelen.
Java HashSet-funksjoner
Noen viktige funksjoner i HashSet er nevnt nedenfor:
- Implementerer Angi grensesnitt .
- Den underliggende datastrukturen for HashSet er Hastbar .
- Ettersom den implementerer Set Interface, er dupliserte verdier ikke tillatt.
- Objekter som du setter inn i HashSet er ikke garantert satt inn i samme rekkefølge. Objekter settes inn basert på deres hash-kode.
- NULL-elementer er tillatt i HashSet.
- HashSet implementerer også Serialiserbar og Klonbar grensesnitt.
Erklæring av HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
hvor OG er typen elementer som er lagret i et HashSet.
HashSet Java Eksempel
Java
// 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());> >}> }> |
fjærmoduler
>
>Produksjon:
1>
Før du lagrer et objekt, sjekker HashSet om det er en eksisterende oppføring ved å bruke hashCode() og equals()-metodene. I eksemplet ovenfor anses to lister som like hvis de har de samme elementene i samme rekkefølge. Når du påkaller hashkode() metoden på de to listene, ville de begge gi samme hasj siden de er like.
Merk: HashSet gjør det ikke lagre dupliserte varer , hvis du gir to objekter som er like, lagrer den bare den første, her er den liste1.
Hierarkiet til HashSet er som følger:
Intern bruk av et hashsett
Alle klassene i Set-grensesnittet er internt sikkerhetskopiert av Map. HashSet bruker HashMap for å lagre objektet internt. Du må lure på at for å legge inn en verdi i HashMap trenger vi et nøkkel-verdi-par, men i HashSet sender vi bare én verdi.
Lagring i HashMap: Faktisk fungerer verdien vi setter inn i HashSet som en nøkkel til kartobjektet, og for verdien bruker java en konstant variabel. Så i nøkkelverdi-paret vil alle verdiene være like.
Implementering av HashSet i 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();> Hvis vi ser på Legg til() metode for HashSet-klassen:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Vi kan legge merke til at add()-metoden til HashSet-klassen internt kaller sette() metode for å sikkerhetskopiere HashMap-objektet ved å sende elementet du har spesifisert som en nøkkel og konstant PRESENT som verdien. fjerne() Metoden fungerer også på samme måte. Den kaller internt fjerningsmetoden til kartgrensesnittet.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet lagrer ikke bare unike objekter, men også en unik samling av objekter som ArrayList , LinkedList , vektor ..osv.
Konstruktører av HashSet-klassen
For å lage et HashSet, må vi lage et objekt av HashSet-klassen. HashSet-klassen består av forskjellige konstruktører som tillater mulig opprettelse av HashSet. Følgende er konstruktørene som er tilgjengelige i denne klassen.
1. HashSet()
Denne konstruktøren brukes til å bygge et tomt HashSet-objekt der standard initialkapasitet er 16 og standard belastningsfaktor er 0,75. Hvis vi ønsker å lage et tomt HashSet med navnet hs, kan det opprettes som:
HashSet hs = new HashSet();>
2. HashSet(int initialCapacity)
Denne konstruktøren brukes til å bygge et tomt HashSet-objekt der initialCapacity er spesifisert på tidspunktet for objektoppretting. Her forblir standard loadFactor 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet(int initialCapacity, float loadFactor)
Denne konstruktøren brukes til å bygge et tomt HashSet-objekt der initialCapacity og loadFactor er spesifisert på tidspunktet for objektoppretting.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (samling)
Denne konstruktøren brukes til å bygge et HashSet-objekt som inneholder alle elementene fra den gitte samlingen. Kort sagt, denne konstruktøren brukes når en konvertering er nødvendig fra et samlingsobjekt til HashSet-objektet. Hvis vi ønsker å lage et HashSet med navnet hs, kan det lages som:
HashSet hs = new HashSet(Collection C);>
Nedenfor er implementeringen av de ovennevnte emnene:
Java
// 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());> >}> }> |
>
>Produksjon:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Metoder i HashSet
| METODE | BESKRIVELSE |
|---|---|
| legg til (Og og) | Brukes til å legge til det spesifiserte elementet hvis det ikke er tilstede, hvis det er til stede, returner false. |
| klar() | Brukes til å fjerne alle elementene fra settet. |
| inneholder(Objekt o) | Brukes for å returnere sann hvis et element er tilstede i et sett. |
| fjern (Objekt o) | Brukes til å fjerne elementet hvis det er tilstede i sett. |
| iterator() | Brukes til å returnere en iterator over elementet i settet. |
| er tom() | Brukes til å sjekke om settet er tomt eller ikke. Returnerer sann for tom og usann for en ikke-tom betingelse for sett. |
| størrelse() | Brukes for å returnere størrelsen på settet. |
| klone() | Brukes til å lage en grunn kopi av settet. |
Utføre forskjellige operasjoner på HashSet
La oss se hvordan du utfører noen få ofte brukte operasjoner på HashSet.
1. Legge til elementer i HashSet
For å legge til et element i HashSet, kan vi bruke add()-metoden . Innsettingsrekkefølgen beholdes imidlertid ikke i HashSet. Vi må merke oss at dupliserte elementer ikke er tillatt og alle dupliserte elementer ignoreres.
Eksempel
Java
// 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);> >}> }> |
>
>Produksjon:
HashSet elements : [Geek, For, Geeks]>
2. Fjerner elementer i HashSet
Verdiene kan fjernes fra HashSet ved å bruke remove()-metoden.
Eksempel
Java
// 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'>));> >}> }> |
>
>Produksjon:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Itererer gjennom HashSet
Iterer gjennom elementene i HashSet ved å bruke iterator()-metoden. Den mest kjente er også å bruke forbedret for loop.
Eksempel
Kodeblokk
ProduksjonA, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Tidskompleksitet for HashSet-operasjoner: Den underliggende datastrukturen for HashSet er hashbar. Så amortiser (gjennomsnittlig eller vanlig kasus) tidskompleksitet for å legge til, fjerne og slå opp (inneholder metode) drift av HashSet O(1) tid.
Ytelse til HashSet
HashSet utvider Abstract Set-klassen og implementerer Sett , Klonbar , og Serialiserbar grensesnitt der E er typen elementer som vedlikeholdes av dette settet. Den direkte kjente underklassen til HashSet er LinkedHashSet .
Nå for opprettholdelse av konstant tidsytelse krever iterasjon over HashSet tid proporsjonal med summen av HashSet-forekomstens størrelse (antall elementer) pluss kapasiteten til den støttende HashMap-forekomsten (antall bøtte). Derfor er det veldig viktig å ikke sette startkapasiteten for høy (eller belastningsfaktoren for lav) hvis iterasjonsytelsen er viktig.
- Opprinnelig kapasitet: Den opprinnelige kapasiteten betyr antall bøtter når hashtabellen (HashSet internt bruker hashbar datastruktur) opprettes. Antall bøtter økes automatisk hvis gjeldende størrelse blir full.
- Belastningsfaktor: Lastfaktoren er et mål på hvor fullt HashSet får bli før kapasiteten automatisk økes. Når antall oppføringer i hash-tabellen overstiger produktet av belastningsfaktoren og gjeldende kapasitet, hash-tabellen rehashes (det vil si at interne datastrukturer bygges opp igjen) slik at hash-tabellen har omtrent dobbelt så mange bøtter.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
Eksempel: Hvis intern kapasitet er 16 og belastningsfaktoren er 0,75, vil antallet bøtter automatisk økes når bordet har 12 elementer i seg.
Effekt på ytelse:
Belastningsfaktor og startkapasitet er to hovedfaktorer som påvirker ytelsen til HashSet-operasjoner. En belastningsfaktor på 0,75 gir svært effektiv ytelse med hensyn til tid og romkompleksitet. Hvis vi øker belastningsfaktorverdien mer enn det, vil minneoverhead reduseres (fordi det vil redusere intern gjenoppbyggingsoperasjon), men det vil påvirke add- og søk-operasjonen i hashtabellen. For å redusere rehashing-operasjonen bør vi velge startkapasitet med omhu. Hvis den opprinnelige kapasiteten er større enn maksimalt antall oppføringer delt på belastningsfaktoren, vil det aldri forekomme noen rehash-operasjon.
Merk: Implementeringen i et HashSet er ikke synkronisert, i den forstand at hvis flere tråder får tilgang til et hashsett samtidig, og minst én av trådene endrer settet, må det synkroniseres eksternt. Dette oppnås vanligvis ved å synkronisere på et objekt som naturlig innkapsler settet. Hvis det ikke finnes noe slikt objekt, bør settet pakkes med Collections.synchronizedSet-metoden. Dette gjøres best ved opprettelsestidspunktet for å forhindre utilsiktet usynkronisert tilgang til settet som vist nedenfor:
Set s = Collections.synchronizedSet(new HashSet(…));
Metoder som brukes med HashSet
1. Metoder arvet fra klassen java.util.AbstractSet
| Metode | Beskrivelse |
|---|---|
| er lik() | Brukes til å verifisere likheten til et objekt med et HashSet og sammenligne dem. Listen returnerer bare sann hvis begge HashSet inneholder de samme elementene, uavhengig av rekkefølge. |
| hashkode() | Returnerer hash-kodeverdien for dette settet. |
| removeAll (samling) | Denne metoden brukes til å fjerne alle elementene fra samlingen som finnes i settet. Denne metoden returnerer true hvis dette settet endres som et resultat av anropet. |
2. Metoder arvet fra klassen java.util.AbstractCollection
| METODE | BESKRIVELSE |
|---|---|
| addAll (samling) | Denne metoden brukes til å legge til alle elementene fra den nevnte samlingen til det eksisterende settet. Elementene legges til tilfeldig uten å følge noen bestemt rekkefølge. |
| inneholder alle (samling) | Denne metoden brukes til å sjekke om settet inneholder alle elementene som finnes i den gitte samlingen eller ikke. Denne metoden returnerer true hvis settet inneholder alle elementene og returnerer false hvis noen av elementene mangler. |
| retainAll (samling) | Denne metoden brukes til å beholde alle elementene fra settet som er nevnt i den gitte samlingen. Denne metoden returnerer sann hvis dette settet endres som et resultat av anropet. |
| toArray() | Denne metoden brukes til å danne en rekke av de samme elementene som settet. |
| toString() | ToString()-metoden til Java HashSet brukes til å returnere en strengrepresentasjon av elementene i HashSet-samlingen. |
3. Metoder deklarert i grensesnittet java.util.Collection
| METODE | BESKRIVELSE |
|---|---|
| parallelStream() | Returnerer en muligens parallell strøm med denne samlingen som kilde. |
| removeIf? (Predikatfilter) | Fjerner alle elementene i denne samlingen som tilfredsstiller det gitte predikatet. |
| strøm() | Returnerer en sekvensiell strøm med denne samlingen som kilde. |
| toArray? (IntFunction generator) | Returnerer en matrise som inneholder alle elementene i denne samlingen, ved å bruke den medfølgende generatorfunksjonen for å allokere den returnerte matrisen. |
4. Metoder deklarert i grensesnittet java.lang.Iterable
| METODE | BESKRIVELSE |
|---|---|
| for hver? (Forbrukerhandling) | Utfører den gitte handlingen for hvert element i Iterable til alle elementene er behandlet eller handlingen gir et unntak. |
5. Metoder deklarert i grensesnittet java.util.Set
| METODE | BESKRIVELSE |
|---|---|
| addAll? (Samling c) | Legger til alle elementene i den angitte samlingen til dette settet hvis de ikke allerede er til stede (valgfri operasjon). |
| inneholder alle? (Samling c) | Returnerer sann hvis dette settet inneholder alle elementene i den angitte samlingen. |
| lik?(Objekt o) | Sammenligner det angitte objektet med dette settet for likhet. |
| hashkode() | Returnerer hash-kodeverdien for dette settet. |
| fjerne alle? (Samling c) | Fjerner fra dette settet alle dets elementer som finnes i den angitte samlingen (valgfri operasjon). |
| beholdeAlle?(Samling c) | Beholder bare elementene i dette settet som finnes i den angitte samlingen (valgfri operasjon). |
| toArray() | Returnerer en matrise som inneholder alle elementene i dette settet. |
| toArray?(T[] a) | Returnerer en matrise som inneholder alle elementene i dette settet; kjøretidstypen for den returnerte matrisen er den for den angitte matrisen. |
Vanlige spørsmål i HashSet i Java
Q1. Hva er HashSet i Java?
Svar:
HashSet er en type klasse som utvider AbstractSet og implementerer Set-grensesnitt.
Q2. Hvorfor brukes HashSet?
Svar:
HashSet brukes for å unngå dupliserte data og for å finne verdi med den raske metoden.
Q3. Forskjeller mellom HashSet og HashMap.
Svar:
| Basis | HashSet | HashMap |
|---|---|---|
| Gjennomføring | HashSet implementerer et Set-grensesnitt. | HashMap implementerer et storesMap-grensesnitt. |
| Duplikater | HashSet tillater ikke dupliserte verdier. | HashMap lagrer nøkkel- og verdiparene og tillater ikke dupliserte nøkler. Hvis nøkkelen er duplikat, erstattes den gamle nøkkelen med den nye verdien. |
| Antall objekter under lagring av objekter | HashSet krever bare ett objekt add(Object o). | HashMap krever to objekter satt (K-tast, V-verdi) for å legge til et element til HashMap-objektet. |
| Dummy verdi | HashSet bruker internt HashMap for å legge til elementer. I HashSet fungerer argumentet sendt i add(Object)-metoden som nøkkel K. Java assosierer internt en dummy-verdi for hver verdi som sendes i add(Object)-metoden. | HashMap har ikke noe begrep om dummy-verdi. |
| Lagre eller legge til en mekanisme | HashSet bruker internt HashMap-objektet til å lagre eller legge til objektene. | HashMap bruker internt hashing for å lagre eller legge til objekter |
| Raskere | HashSet er tregere enn HashMap. | HashMap er raskere enn HashSet. |
| Innsetting | HashSet bruker add()-metoden for å legge til eller lagre data. | HashMap bruker put()-metoden for å lagre data. |
| Eksempel | HashSet er et sett, f.eks. {1, 2, 3, 4, 5, 6, 7}. | HashMap er et nøkkel -> verdipar (nøkkel til verdi) kart, f.eks. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Q4. Forskjeller mellom HashSet og TreeSet i Java.
Svar:
| Basis | HashSet | Tresett markdown fotnoter |
|---|---|---|
| Hastighet og intern implementere, kaste handling | For operasjoner som søk, sett inn og slett. Det tar i gjennomsnitt konstant tid for disse operasjonene. HashSet er raskere enn TreeSet. HashSet er implementert ved hjelp av en hash-tabell. | TreeSet tar O(Log n) for søk, sett inn og slett som er høyere enn HashSet. Men TreeSet holder sorterte data. Den støtter også operasjoner som høyere() (Returnerer minst høyere element), floor(), loft(), osv. Disse operasjonene er også O(Log n) i TreeSet og støttes ikke i HashSet. TreeSet er implementert ved hjelp av et selvbalanserende binært søketre (rød-svart tre). TreeSet er støttet av TreeMap i Java. |
| Bestilling | Elementer i HashSet er ikke bestilt. | TreeSet vedlikeholder objekter i sortert rekkefølge definert av enten Comparable- eller Comparator-metoden i Java. TreeSet-elementer er sortert i stigende rekkefølge som standard. Den tilbyr flere metoder for å håndtere det bestilte settet som first(), last(), headSet(), tailSet(), etc. |
| Null objekt | HashSet tillater null-objektet. | TreeSet tillater ikke null Object og kaster NullPointerException, hvorfor, er fordi TreeSet bruker compareTo()-metoden for å sammenligne nøkler, og compareTo() vil kaste java.lang.NullPointerException. |
| Sammenligning | HashSet bruker equals()-metoden for å sammenligne to objekter i settet og for å oppdage duplikater. | TreeSet bruker compareTo()-metoden til samme formål. Hvis equals() og compareTo() ikke er konsistente, det vil si at for to like objekter skal like returnere true mens compareTo() skal returnere null, vil det bryte kontrakten til Set-grensesnittet og tillate duplikater i Set-implementeringer som TreeSet |