En guide til HashSet i Java

1. Oversigt

I denne artikel dykker vi ind i HashSet. Det er en af ​​de mest populære Sæt implementeringer såvel som en integreret del af Java Collections Framework.

2. Introduktion til HashSet

HashSet er en af ​​de grundlæggende datastrukturer i Java Collections API.

Lad os huske de vigtigste aspekter af denne implementering:

  • Den gemmer unikke elementer og tillader nul
  • Det understøttes af en HashMap
  • Det opretholder ikke indsætningsrækkefølgen
  • Det er ikke trådsikkert

Bemærk, at denne interne HashMap bliver initialiseret, når en forekomst af HashSet er oprettet:

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

Hvis du vil gå dybere ind i, hvordan HashMap fungerer, kan du læse artiklen med fokus på den her.

3. API'et

I dette afsnit vil vi gennemgå de mest anvendte metoder og se på nogle enkle eksempler.

3.1. tilføje()

Det tilføje() metode kan bruges til at tilføje elementer til et sæt. Metodekontrakten siger, at et element kun tilføjes, når det ikke allerede er til stede i et sæt. Hvis der blev tilføjet et element, returneres metoden rigtigt, Ellers - falsk.

Vi kan tilføje et element til en HashSet synes godt om:

@Test offentlig ugyldig nårAddingElement_shouldAddElement () {Set hashset = new HashSet (); assertTrue (hashset.add ("Streng tilføjet")); }

Fra et implementeringsperspektiv er tilføje metoden er ekstremt vigtig. Implementeringsdetaljer illustrerer, hvordan HashSet arbejder internt og udnytter HashMap'ssætte metode:

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

Det kort variabel er en henvisning til det interne, bagvedliggende HashMap:

privat kortvarigt HashMap-kort;

Det ville være en god ide at blive fortrolig med hashcode først for at få en detaljeret forståelse af, hvordan elementerne er organiseret i hash-baserede datastrukturer.

Sammenfatning:

  • EN HashMap er en række af spande med en standardkapacitet på 16 elementer - hver spand svarer til en anden hashcode-værdi
  • Hvis forskellige objekter har den samme hashcode-værdi, gemmes de i en enkelt spand
  • Hvis den belastningsfaktor er nået, en ny matrix bliver oprettet dobbelt så stor som den forrige, og alle elementer bliver genvasket og omfordelt blandt nye tilsvarende spande
  • For at hente en værdi, hash vi en nøgle, modificerer den og går derefter til en tilsvarende spand og søger gennem den potentielt sammenkædede liste, hvis der er mere end et objekt

3.2. indeholder()

Formålet med indeholder metoden er at kontrollere, om et element er til stede i en given HashSet. Det vender tilbage rigtigt hvis elementet findes, ellers falsk.

Vi kan se efter et element i HashSet:

@Test offentlig ugyldig nårCheckingForElement_shouldSearchForElement () {Set hashsetContains = new HashSet (); hashsetContains.add ("Streng tilføjet"); assertTrue (hashsetContains.contains ("Streng tilføjet")); }

Når et objekt sendes til denne metode, beregnes hashværdien. Derefter bliver den tilsvarende skovplacering løst og krydset.

3.3. fjerne()

Metoden fjerner det angivne element fra sættet, hvis det er til stede. Denne metode vender tilbage rigtigt hvis et sæt indeholdt det angivne element.

Lad os se et fungerende eksempel:

@Test offentligt ugyldigt nårRemovingElement_shouldRemoveElement () {Set removeFromHashSet = new HashSet (); removeFromHashSet.add ("Streng tilføjet"); assertTrue (removeFromHashSet.remove ("Streng tilføjet")); }

3.4. klar()

Vi bruger denne metode, når vi har til hensigt at fjerne alle elementerne fra et sæt. Den underliggende implementering rydder simpelthen alle elementer fra den underliggende HashMap.

Lad os se det i aktion:

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

3.5. størrelse()

Dette er en af ​​de grundlæggende metoder i API'en. Det bruges tungt, da det hjælper med at identificere antallet af elementer, der er til stede i HashSet. Den underliggende implementering delegerer simpelthen beregningen til HashMaps størrelse () metode.

Lad os se det i aktion:

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

3.6. er tom()

Vi kan bruge denne metode til at finde ud af, om en given forekomst af en HashSet er tom eller ej. Denne metode vender tilbage rigtigt hvis sættet ikke indeholder nogen elementer:

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

3.7. iterator ()

Metoden returnerer en iterator over elementerne i Sæt. Elementerne besøges i ingen særlig rækkefølge, og iteratorer går hurtigt hurtigt.

Vi kan observere den tilfældige iterationsrækkefølge 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 sættet når som helst ændres efter at iteratoren er oprettet på nogen måde undtagen gennem iteratorens egen fjernelsesmetode, Iterator kaster en ConcurrentModificationException.

Lad os se det i aktion:

@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, hvis vi havde brugt iteratorens fjernelsesmetode, ville vi ikke have stødt på undtagelsen:

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

En iterators fejlsøgte opførsel kan ikke garanteres, da det er umuligt at stille hårde garantier i nærvær af usynkroniseret samtidig ændring.

Fejl-hurtig iteratorskast ConcurrentModificationException på bedst mulig basis. Derfor ville det være forkert at skrive et program, der var afhængigt af denne undtagelse for dets rigtighed.

4. Hvordan HashSet Bevarer unikhed?

Når vi lægger en genstand i en HashSet, det bruger objektets hashcode værdi for at bestemme, om et element ikke allerede er i sættet.

Hver hashkodeværdi svarer til en bestemt skovplacering, der kan indeholde forskellige elementer, for hvilke den beregnede hashværdi er den samme. Men to objekter med det samme hashCode er muligvis ikke lige.

Så objekter inden for den samme spand vil blive sammenlignet ved hjælp af lige med() metode.

5. Udførelse af HashSet

Udførelsen af ​​en HashSet påvirkes hovedsageligt af to parametre - dens Indledende kapacitet og Belastningsfaktor.

Den forventede tidskompleksitet ved at føje et element til et sæt er O (1) som kan falde til På) i værste fald (kun en spand til stede) - derfor det er vigtigt at opretholde retten HashSet er kapacitet.

En vigtig note: siden JDK 8 er tidskompleksiteten i værste tilfælde O (log * n).

Belastningsfaktoren beskriver, hvad der er det maksimale fyldniveau, over hvilket et sæt skal ændres.

Vi kan også oprette en HashSet med brugerdefinerede værdier til startkapacitet og belastningsfaktor:

Indstil hashset = nyt HashSet (); Indstil hashset = nyt HashSet (20); Indstil hashset = nyt HashSet (20, 0,5f); 

I det første tilfælde bruges standardværdierne - startkapaciteten på 16 og belastningsfaktoren på 0,75. I det andet tilsidesætter vi standardkapaciteten, og i den tredje tilsidesætter vi begge.

En lav startkapacitet reducerer pladskompleksiteten, men øger hyppigheden af ​​genopvaskning, hvilket er en dyr proces.

På den anden side, en høj startkapacitet øger omkostningerne ved iteration og det oprindelige hukommelsesforbrug.

Som en tommelfingerregel:

  • En høj startkapacitet er god for et stort antal poster kombineret med ringe eller ingen iteration
  • En lav startkapacitet er god for få poster med meget iteration

Det er derfor meget vigtigt at finde den korrekte balance mellem de to. Normalt er standardimplementeringen optimeret og fungerer fint, hvis vi føler behov for at indstille disse parametre, så de passer til kravene, skal vi gøre det med omtanke.

6. Konklusion

I denne artikel skitserede vi nytten af ​​a HashSet, dets formål såvel som dets underliggende arbejde. Vi så, hvor effektiv det er med hensyn til anvendelighed i betragtning af dets konstante tidseffektivitet og evne til at undgå dubletter.

Vi studerede nogle af de vigtige metoder fra API, hvordan de kan hjælpe os som udvikler med at bruge en HashSet til sit potentiale.

Som altid kan kodeuddrag findes på GitHub.