streamalism.org

1. Inleiding

In deze korte handleiding we gaan de prestaties van de bevat () methode beschikbaar in java.util.HashSet en java.util.ArrayList. Het zijn beide verzamelingen voor het opslaan en manipuleren van objecten.

HashSet is een collectie voor het opbergen van unieke elementen. Voor meer informatie over het HashSet, bekijk deze link.

ArrayList is een populaire implementatie van de java.util.List koppel.

We hebben een uitgebreid artikel over de ArrayList beschikbaar Hier.

2. HashSet. Bevat ()

Intern is het HashSet implementatie is gebaseerd op een Hash kaart voorbeeld. De bevat () methode aanroepen HashMap.containsKey (object).

Hier controleert het of het voorwerp staat op de interne kaart of niet. De interne kaart slaat gegevens op in de knooppunten, ook wel buckets genoemd. Elke bucket komt overeen met een hashcode die is gegenereerd met hashCode () methode. Zo bevat () daadwerkelijk gebruikt hashCode () methode om het voorwerpen plaats.

Laten we nu de complexiteit van de opzoektijd bepalen. Zorg ervoor dat u bekend bent met de Big-O-notatie voordat u verder gaat.

Gemiddeld, de bevat () van HashSet loopt naar binnen O (1) tijd. Verkrijgen van het voorwerpen emmerlocatie is een constante tijdoperatie. Rekening houdend met mogelijke botsingen, kan de opzoektijd oplopen tot logboek (n) omdat de interne bakconstructie een TreeMap.

Dit is een verbetering ten opzichte van Java 7 waarin een LinkedList voor de interne bakconstructie. Over het algemeen zijn botsingen met hash-codes zeldzaam. We kunnen dus de opzoekcomplexiteit van de elementen beschouwen als O (1).

3. ArrayList.contains ()

Intern, ArrayList gebruikt de indexOf (object) methode om te controleren of het object in de lijst staat. De indexOf (object) methode itereert de hele array en vergelijkt elk element met de is gelijk aan (object) methode.

Terugkomend op complexiteitsanalyse, de ArrayList.bevat () methode vereist Aan) tijd. Dus de tijd die we besteden om hier een specifiek object te vinden, hangt af van het aantal items dat we in de array hebben.

4. Benchmark testen

Laten we nu de JVM opwarmen met de prestatiebenchmarktest. We gebruiken het JMH-product (Java Microbenchmark Harness) OpenJDK. Raadpleeg onze handige gids voor meer informatie over installatie en uitvoering.

Laten we om te beginnen een eenvoudig Collecties Benchmark klasse:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iteraties = 5) openbare klasse CollectionsBenchmark {@State (Scope.Thread) openbare statische klasse MyState {privé Set employeeSet = nieuwe HashSet (); private List employeeList = nieuwe ArrayList (); privé lange iteraties = 1000; privé werknemer werknemer = nieuwe werknemer (100L, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {employeeSet.add (new Employee (i, "John")); employeeList.add (nieuwe medewerker (i, "John")); } employeeList.add (medewerker); employeeSet.add (medewerker); }}}

Hier maken en initialiseren we HashSet en een ArrayList van Werknemer voorwerpen:

openbare klasse Medewerker {privé Lange id; private String naam; // constructor en getter setters gaan hier}

We voegen de werknemer = nieuwe werknemer (100L, "Harry") instantie als de laatste elementen voor beide collecties. Dus we testen de werknemer de opzoektijd van het object voor het ergst mogelijke geval.

@OutputTimeUnit (TimeUnit.NANOSECONDS) geeft aan dat we de resultaten in nanoseconden willen. Het aantal default @Opwarmen iteraties zijn 5 in ons geval. De @BenchmarkMode ingesteld op Modus. Gemiddelde tijd, wat betekent dat we geïnteresseerd zijn in het berekenen van een gemiddelde looptijd. Voor de eerste executie zetten we iteraties = 1000 items in onze collecties.

Daarna voegen we onze benchmarkmethoden toe aan het Collecties Benchmark klasse:

@Benchmark openbare boolean testArrayList (MyState state) {return state.employeeList.contains (state.employee); }

Hier controleren we of de medewerkerLijst bevat werknemer voorwerp.

Evenzo hebben we de bekende test voor medewerker:

@Benchmark openbare boolean testHashSet (MyState state) {return state.employeeSet.contains (state.employee); }

Eindelijk kunnen we de test uitvoeren:

public static void main (String [] args) gooit Uitzondering {Options options = new OptionsBuilder () .include (CollectionsBenchmark.class.getSimpleName ()) .forks (1) .build (); nieuwe Runner (opties) .run (); }

Hier zijn de resultaten:

Benchmarkmodus Cnt Score Fout Eenheden CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns / op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns / op

We kunnen duidelijk zien dat de testArrayList methode heeft 4035.646 ns gemiddelde opzoekscore, terwijl de testHashSet presteert sneller met 9.456 ns gemiddeld.

Laten we nu het aantal elementen in onze test verhogen en het uitvoeren voor iteraties = 10.000 items:

Benchmarkmodus Cnt Score Fout Eenheden CollectionsBenchmark.testArrayList gem. 20 57499.620 ± 11388.645 ns / op CollectionsBenchmark.testHashSet gem. 20 11.802 ± 1.164 ns / op

Ook hier de bevat () in HashSet heeft een enorm prestatievoordeel ten opzichte van de ArrayList.

5. Conclusie

Dit korte artikel legt de prestaties van het bevat () methode van de HashSet en ArrayList collecties. Met behulp van de JMH-benchmarking hebben we de prestaties van bevat () voor elk type collectie.

Als conclusie kunnen we dat leren de bevat () methode werkt sneller in HashSet vergeleken met een ArrayList.

Zoals gewoonlijk is de volledige code voor dit artikel voorbij op het GitHub-project.