streamalism.org

1. Overzicht

In dit artikel gaan we dieper in op HashSet. Het is een van de meest populaire Set implementaties en een integraal onderdeel van het Java Collections Framework.

2. Inleiding tot HashSet

HashSet is een van de fundamentele gegevensstructuren in de Java Collections API.

Laten we de belangrijkste aspecten van deze implementatie in herinnering brengen:

• Het slaat unieke elementen op en laat nullen toe
• Het wordt ondersteund door een Hash kaart
• Het handhaaft de invoegvolgorde niet
• Het is niet draadveilig

Merk op dat deze interne Hash kaart wordt geïnitialiseerd wanneer een instantie van de HashSet is gecreëerd:

openbare HashSet () {map = nieuwe HashMap (); }

Als je dieper wilt ingaan op hoe de Hash kaart werkt, kunt u het artikel dat erop is gericht hier lezen.

3. De API

In dit gedeelte gaan we de meest gebruikte methoden bekijken en enkele eenvoudige voorbeelden bekijken.

3.1. toevoegen()

De toevoegen() methode kan worden gebruikt om elementen aan een set toe te voegen. In het methode contract staat dat een element alleen wordt toegevoegd als het nog niet aanwezig is in een set. Als er een element is toegevoegd, keert de methode terug waar, anders - false.

We kunnen een element toevoegen aan een HashSet Leuk vinden:

@Test openbare leegte whenAddingElement_shouldAddElement () {Set hashset = nieuwe HashSet (); assertTrue (hashset.add ("String toegevoegd")); }

Vanuit een implementatieperspectief is het toevoegen methode is een uiterst belangrijke. Implementatiedetails illustreren hoe het HashSet werkt intern en maakt gebruik van de HashMap'sleggen methode:

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

De kaart variabele is een verwijzing naar de interne, back-up Hash kaart:

privé tijdelijke HashMap-kaart;

Het zou een goed idee zijn om vertrouwd te raken met het hashcode eerst om een ​​gedetailleerd begrip te krijgen van hoe de elementen zijn georganiseerd in hash-gebaseerde datastructuren.

Samenvatten:

• EEN Hash kaart is een reeks van emmers met een standaardcapaciteit van 16 elementen - elke bucket komt overeen met een andere hashcode-waarde
• Als verschillende objecten dezelfde hashcode-waarde hebben, worden ze opgeslagen in een enkele bucket
• Als het ladingsfactor wordt bereikt, wordt een nieuwe array gemaakt die twee keer zo groot is als de vorige en worden alle elementen opnieuw gehasht en opnieuw verdeeld over nieuwe overeenkomstige buckets
• Om een ​​waarde op te halen, hashen we een sleutel, passen deze aan en gaan dan naar een overeenkomstige bucket en doorzoeken de potentieel gekoppelde lijst in het geval dat er meer dan één object is

3.2. bevat ()

Het doel van de bevat methode is om te controleren of een element aanwezig is in een gegeven HashSet. Het keert terug waar als het element wordt gevonden, anders false.

We kunnen controleren op een element in het HashSet:

@Test openbare leegte whenCheckingForElement_shouldSearchForElement () {Set hashsetContains = nieuwe HashSet (); hashsetContains.add ("String toegevoegd"); assertTrue (hashsetContains.contains ("String toegevoegd")); }

Telkens wanneer een object aan deze methode wordt doorgegeven, wordt de hash-waarde berekend. Vervolgens wordt de bijbehorende bucketlocatie opgelost en doorlopen.

3.3. verwijderen()

De methode verwijdert het opgegeven element uit de set als dit aanwezig is. Deze methode keert terug waar als een set het opgegeven element bevat.

Laten we een werkend voorbeeld bekijken:

@Test openbare leegte whenRemovingElement_shouldRemoveElement () {Set removeFromHashSet = nieuwe HashSet (); removeFromHashSet.add ("String toegevoegd"); assertTrue (removeFromHashSet.remove ("String toegevoegd")); }

3.4. Doorzichtig()

We gebruiken deze methode wanneer we van plan zijn alle items uit een set te verwijderen. De onderliggende implementatie wist eenvoudigweg alle elementen uit de onderliggende Hash kaart.

Laten we dat in actie zien:

@Test openbare leegte whenClearingHashSet_shouldClearHashSet () {Set clearHashSet = nieuwe HashSet (); clearHashSet.add ("String toegevoegd"); clearHashSet.clear (); assertTrue (clearHashSet.isEmpty ()); }

3.5. grootte()

Dit is een van de fundamentele methoden in de API. Het wordt veel gebruikt omdat het helpt bij het identificeren van het aantal elementen dat aanwezig is in het HashSet. De onderliggende implementatie delegeert de berekening eenvoudigweg naar het HashMap's grootte () methode.

Laten we dat in actie zien:

@Test openbare leegte whenCheckingTheSizeOfHashSet_shouldReturnThesize () {Set hashSetSize = nieuwe HashSet (); hashSetSize.add ("String toegevoegd"); assertEquals (1, hashSetSize.size ()); }

3.6. is leeg()

We kunnen deze methode gebruiken om te bepalen of een bepaald exemplaar van een HashSet is leeg of niet. Deze methode keert terug waar als de set geen elementen bevat:

@Test openbare leegte whenCheckingForEmptyHashSet_shouldCheckForEmpty () {Set emptyHashSet = nieuwe HashSet (); assertTrue (emptyHashSet.isEmpty ()); }

3.7. iterator ()

De methode retourneert een iterator over de elementen in de Set. De elementen worden in willekeurige volgorde bezocht en iteratoren werken niet snel.

We kunnen de willekeurige iteratievolgorde hier bekijken:

@Test openbare leegte whenIteratingHashSet_shouldIterateHashSet () {Set hashset = nieuwe HashSet (); hashset.add ("Eerste"); hashset.add ("Tweede"); hashset.add ("Derde"); Iterator itr = hashset.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Als de set op enig moment wordt gewijzigd nadat de iterator op enigerlei wijze is gemaakt, behalve via de eigen verwijderingsmethode van de iterator, de Iterator gooit een ConcurrentModificationException.

Laten we dat in actie zien:

@Test (verwacht = ConcurrentModificationException.class) public void whenModifyingHashSetWhileIterating_shouldThrowException () {Set hashset = new HashSet (); hashset.add ("Eerste"); hashset.add ("Tweede"); hashset.add ("Derde"); Iterator itr = hashset.iterator (); while (itr.hasNext ()) {itr.next (); hashset.remove ("Tweede"); }} 

Als alternatief, als we de verwijderingsmethode van de iterator hadden gebruikt, zouden we de uitzondering niet zijn tegengekomen:

@Test openbare leegte whenRemovingElementUsingIterator_shouldRemoveElement () {Set hashset = new HashSet (); hashset.add ("Eerste"); hashset.add ("Tweede"); hashset.add ("Derde"); Iterator itr = hashset.iterator (); while (itr.hasNext ()) {String element = itr.next (); if (element.equals ("Second")) itr.remove (); } assertEquals (2, hashset.size ()); }

Het faalgedrag van een iterator kan niet worden gegarandeerd, aangezien het onmogelijk is om harde garanties te geven in de aanwezigheid van niet-gesynchroniseerde gelijktijdige modificatie.

Fail-fast iterators gooien ConcurrentModificationException op een best mogelijke basis. Daarom zou het verkeerd zijn om een ​​programma te schrijven dat vanwege de juistheid van deze uitzondering afhing.

4. Hoe HashSet Behoudt uniekheid?

Wanneer we een object in een HashSet, het gebruikt de hashcode waarde om te bepalen of een element niet al in de set zit.

Elke hash-codewaarde komt overeen met een bepaalde bucketlocatie die verschillende elementen kan bevatten, waarvoor de berekende hash-waarde hetzelfde is. Maar twee objecten met hetzelfde hashCode misschien niet gelijk.

Objecten binnen dezelfde bucket worden dus vergeleken met de is gelijk aan () methode.

5. Prestaties van HashSet

De uitvoering van een HashSet wordt voornamelijk beïnvloed door twee parameters - its Initiële capaciteit en de Ladingsfactor.

De verwachte tijdcomplexiteit van het toevoegen van een element aan een set is O (1) die kan dalen tot Aan) in het ergste geval (slechts één emmer aanwezig) - daarom het is essentieel om het recht te behouden Van HashSet capaciteit.

Een belangrijke opmerking: sinds JDK 8 is de tijdcomplexiteit in het slechtste geval O (log * n).

De belastingsfactor beschrijft wat het maximale vulniveau is, waarboven een set moet worden aangepast.

We kunnen ook een HashSet met aangepaste waarden voor initiële capaciteit en ladingsfactor:

Set hashset = new HashSet (); Set hashset = new HashSet (20); Set hashset = new HashSet (20, 0.5f); 

In het eerste geval worden de standaardwaarden gebruikt - de initiële capaciteit van 16 en de belastingsfactor van 0,75. In de tweede overschrijven we de standaardcapaciteit en in de derde overschrijven we beide.

Een lage initiële capaciteit vermindert de complexiteit van de ruimte, maar verhoogt de frequentie van opnieuw haspelen, wat een duur proces is.

Aan de andere kant, een hoge initiële capaciteit verhoogt de kosten van iteratie en het initiële geheugengebruik.

Als vuistregel:

• Een hoge initiële capaciteit is goed voor een groot aantal inzendingen in combinatie met weinig tot geen iteratie
• Een lage initiële capaciteit is goed voor weinig inzendingen met veel iteratie

Het is daarom erg belangrijk om de juiste balans tussen beide te vinden. Gewoonlijk is de standaardimplementatie geoptimaliseerd en werkt deze prima. Mochten we de behoefte voelen om deze parameters af te stemmen op de vereisten, dan moeten we dit oordeelkundig doen.

6. Conclusie

In dit artikel hebben we het nut van een HashSet, zowel het doel als de onderliggende werking. We hebben gezien hoe efficiënt het is in termen van bruikbaarheid, gezien de constante tijdprestaties en het vermogen om duplicaten te vermijden.

We hebben enkele van de belangrijke methoden van de API bestudeerd, hoe ze ons als ontwikkelaar kunnen helpen om een HashSet tot zijn potentieel.

Zoals altijd zijn codefragmenten te vinden op GitHub.