streamalism.org

1. Oversikt

I denne artikkelen vil vi dykke inn i HashSet. Det er en av de mest populære Sett implementeringer i tillegg til en integrert del av Java Collections Framework.

2. Introduksjon til HashSet

HashSet er en av de grunnleggende datastrukturene i Java Collections API.

La oss huske de viktigste aspektene ved denne implementeringen:

• Den lagrer unike elementer og tillater null
• Det støttes av en HashMap
• Det opprettholder ikke innsettingsrekkefølgen
• Det er ikke trådsikkert

Merk at dette interne HashMap blir initialisert når en forekomst av HashSet er skapt:

offentlig HashSet () {map = ny HashMap (); }

Hvis du vil gå dypere inn i hvordan HashMap fungerer, kan du lese artikkelen fokusert på den her.

3. API

I denne delen skal vi gjennomgå de mest brukte metodene og se på noen enkle eksempler.

3.1. legge til()

De legge til() metoden kan brukes for å legge til elementer i et sett. Metodekontrakten sier at et element bare vil legges til når det ikke allerede er tilstede i et sett. Hvis et element ble lagt til, returnerer metoden ekte, ellers - falsk.

Vi kan legge til et element i en HashSet som:

@Test offentlig ugyldig nårAddingElement_shouldAddElement () {Set hashset = new HashSet (); assertTrue (hashset.add ("String lagt til")); }

Fra et implementeringsperspektiv er legge til metoden er ekstremt viktig. Implementeringsdetaljer illustrerer hvordan HashSet fungerer internt og utnytter HashMap'ssette metode:

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

De kart variabel er en referanse til det interne, støttet HashMap:

privat forbigående HashMap-kart;

Det vil være lurt å bli kjent med hashcode først for å få en detaljert forståelse av hvordan elementene er organisert i hash-baserte datastrukturer.

Oppsummering:

• EN HashMap er en rekke bøtter med en standard kapasitet på 16 elementer - hver bøtte tilsvarer en annen hashcode-verdi
• Hvis forskjellige objekter har samme hashcode-verdi, blir de lagret i en enkelt bøtte
• Hvis den lastfaktor er nådd, en ny matrise blir opprettet dobbelt så stor som den forrige og alle elementene blir vasket og omfordelt blant nye tilsvarende bøtter
• For å hente en verdi, hash vi en nøkkel, modifiserer den, og går deretter til en tilsvarende bøtte og søker gjennom den potensielt koblede listen i tilfelle det er mer enn ett objekt

3.2. inneholder ()

Formålet med inneholder metoden er å sjekke om et element er tilstede i et gitt HashSet. Det kommer tilbake ekte hvis elementet er funnet, ellers falsk.

Vi kan se etter et element i HashSet:

@Test offentlig ugyldig nårCheckingForElement_shouldSearchForElement () {Set hashsetContains = new HashSet (); hashsetContains.add ("String lagt til"); assertTrue (hashsetContains.contains ("Streng lagt til")); }

Når et objekt sendes til denne metoden, blir hashverdien beregnet. Deretter blir den tilsvarende bøtteplasseringen løst og krysset.

3.3. fjerne()

Metoden fjerner det angitte elementet fra settet hvis det er til stede. Denne metoden returnerer ekte hvis et sett inneholdt det spesifiserte elementet.

La oss se et fungerende eksempel:

@Test offentlig ugyldig nårRemovingElement_shouldRemoveElement () {Set removeFromHashSet = new HashSet (); removeFromHashSet.add ("Streng lagt til"); assertTrue (removeFromHashSet.remove ("Streng lagt til")); }

3.4. klar()

Vi bruker denne metoden når vi har til hensikt å fjerne alle elementene fra et sett. Den underliggende implementeringen fjerner ganske enkelt alle elementene fra den underliggende HashMap.

La oss se det i aksjon:

@Test offentlig ugyldig nårClearingHashSet_shouldClearHashSet () {Set clearHashSet = new HashSet (); clearHashSet.add ("Streng lagt til"); clearHashSet.clear (); assertTrue (clearHashSet.isEmpty ()); }

3.5. størrelse()

Dette er en av de grunnleggende metodene i API. Det brukes tungt da det hjelper til med å identifisere antall elementer som er tilstede i HashSet. Den underliggende implementeringen delegerer bare beregningen til HashMaps størrelse () metode.

La oss se det i aksjon:

@Test offentlig ugyldig nårCheckingTheSizeOfHashSet_shouldReturnThesize () {Set hashSetSize = new HashSet (); hashSetSize.add ("Streng lagt til"); assertEquals (1, hashSetSize.size ()); }

3.6. er tom()

Vi kan bruke denne metoden for å finne ut om en gitt forekomst av en HashSet er tom eller ikke. Denne metoden returnerer ekte hvis settet ikke inneholder noen elementer:

@Test offentlig ugyldig nårCheckingForEmptyHashSet_shouldCheckForEmpty () {Set emptyHashSet = new HashSet (); assertTrue (emptyHashSet.isEmpty ()); }

3.7. iterator ()

Metoden returnerer en iterator over elementene i Sett. Elementene blir besøkt i ingen spesiell rekkefølge, og iteratorer går raskt.

Vi kan observere den tilfeldige iterasjonsrekkefølgen her:

@Test offentlig ugyldig nårIteratingHashSet_shouldIterateHashSet () {Set hashset = new HashSet (); hashset.add ("First"); hashset.add ("Second"); hashset.add ("Tredje"); Iterator itr = hashset.iterator (); mens (itr.hasNext ()) {System.out.println (itr.next ()); }}

Hvis settet endres når som helst etter at iteratoren er opprettet på noen måte unntatt gjennom iteratorens egen fjerningsmetode, vil Iterator kaster en ConcurrentModificationException.

La oss se det i aksjon:

@Test (forventet = ConcurrentModificationException.class) offentlig ugyldig nårModifyingHashSetWhileIterating_shouldThrowException () {Set hashset = new HashSet (); hashset.add ("First"); hashset.add ("Second"); hashset.add ("Tredje"); Iterator itr = hashset.iterator (); mens (itr.hasNext ()) {itr.next (); hashset.remove ("Second"); }} 

Alternativt, hadde vi brukt iteratorens fjerningsmetode, ville vi ikke ha opplevd unntaket:

@Test offentlig ugyldig nårRemovingElementUsingIterator_shouldRemoveElement () {Set hashset = new HashSet (); hashset.add ("First"); hashset.add ("Second"); hashset.add ("Tredje"); Iterator itr = hashset.iterator (); while (itr.hasNext ()) {Strengelement = itr.next (); if (element.equals ("Second")) itr.remove (); } assertEquals (2, hashset.size ()); }

Den mislykkede oppførselen til en iterator kan ikke garanteres, da det er umulig å gi noen harde garantier i nærvær av usynkronisert samtidig modifikasjon.

Fail-fast iterators throw ConcurrentModificationException på best mulig basis. Derfor ville det være galt å skrive et program som var avhengig av dette unntaket for sin korrekthet.

4. Hvordan HashSet Opprettholder unikhet?

Når vi legger et objekt i en HashSet, den bruker objektets hashcode verdi for å bestemme om et element ikke allerede er i settet.

Hver hashkodeverdi tilsvarer et bestemt bøttested som kan inneholde forskjellige elementer, som den beregnede hashverdien er den samme for. Men to gjenstander med det samme hashCode kanskje ikke like.

Så, objekter i samme bøtte vil bli sammenlignet med er lik() metode.

5. Utførelse av HashSet

Utførelsen av en HashSet påvirkes hovedsakelig av to parametere - dens Startkapasitet og Lastfaktor.

Den forventede tidskompleksiteten for å legge til et element i et sett er O (1) som kan falle til På) i verste fall (bare en bøtte til stede) - derfor det er viktig å opprettholde retten HashSet er kapasitet.

En viktig merknad: siden JDK 8 er tidskompleksiteten i verste fall O (log * n).

Lastfaktoren beskriver hva som er det maksimale fyllnivået, over hvilket et sett må endres.

Vi kan også lage en HashSet med tilpassede verdier for startkapasitet og lastfaktor:

Sett hashset = nytt HashSet (); Sett hashset = nytt HashSet (20); Sett hashset = nytt HashSet (20, 0.5f); 

I det første tilfellet brukes standardverdiene - startkapasiteten på 16 og lastfaktoren på 0,75. I det andre overstyrer vi standardkapasiteten, og i den tredje overstyrer vi begge.

En lav startkapasitet reduserer plasskompleksiteten, men øker hyppigheten av gjenvasking, noe som er en kostbar prosess.

På den andre siden, høy initial kapasitet øker kostnadene for iterasjon og det første minneforbruket.

Som en tommelregel:

• En høy startkapasitet er bra for et stort antall oppføringer kombinert med liten eller ingen iterasjon
• En lav startkapasitet er bra for få oppføringer med mye iterasjon

Det er derfor veldig viktig å finne den rette balansen mellom de to. Vanligvis er standardimplementeringen optimalisert og fungerer helt fint, hvis vi føler behov for å justere disse parametrene for å dekke kravene, må vi gjøre det med omhu.

6. Konklusjon

I denne artikkelen skisserte vi nytten av a HashSet, dens formål så vel som dens underliggende arbeid. Vi så hvor effektiv det er når det gjelder brukervennlighet gitt sin konstante tidsytelse og evne til å unngå duplikater.

Vi studerte noen av de viktige metodene fra API, hvordan de kan hjelpe oss som utvikler med å bruke en HashSet til potensialet.

Som alltid kan du finne kodebiter på GitHub.