streamalism.org

1. Introduktion

I denne hurtige vejledning vi skal diskutere præstationen af indeholder() metode tilgængelig i java.util.HashSet og java.util.ArrayList. De er begge samlinger til opbevaring og manipulation af objekter.

HashSet er en samling til opbevaring af unikke elementer. For at lære mere om HashSet, tjek dette link.

ArrayList er en populær implementering af java.util.List interface.

Vi har en udvidet artikel om ArrayList tilgængelig her.

2. HashSet.contains ()

Internt er den HashSet implementering er baseret på en HashMap eksempel. Det indeholder() metodeopkald HashMap.containsKey (objekt).

Her kontrolleres det, om objekt er på det interne kort eller ej. Det interne kort gemmer data inde i noderne, kendt som spande. Hver spand svarer til en hash-kode genereret med hashCode () metode. Så indeholder() bruger faktisk hashCode () metode til at finde objekt Beliggenhed.

Lad os nu bestemme kompleksitet i opslagstiden. Før du går videre, skal du sørge for at være fortrolig med Big-O-notationen.

Gennemsnitlig, det indeholder() af HashSet løber ind O (1) tid. At få objekt skovlplacering er en konstant tidsoperation. Under hensyntagen til mulige kollisioner kan opslagstiden stige til log (n) fordi den indvendige skovlstruktur er en TreeMap.

Dette er en forbedring fra Java 7, der brugte en LinkedList til den indvendige skovlstruktur. Generelt er hash-kodekollisioner sjældne. Så vi kan overveje elementernes opslagskompleksitet som O (1).

3. ArrayList.cfortsætter ()

Internt, ArrayList bruger indexOf (objekt) metode til at kontrollere, om objektet er på listen. Det indexOf (objekt) metode gentager hele arrayet og sammenligner hvert element med er lig med (objekt) metode.

At komme tilbage til kompleksitetsanalyse, ArrayList.indeholder() metoden kræver På) tid. Så den tid, vi bruger på at finde et bestemt objekt her, afhænger af antallet af varer, vi har i arrayet.

4. Benchmark-test

Lad os nu varme op på JVM med performance benchmark test. Vi bruger JMH (Java Microbenchmark Harness) OpenJDK-produktet. For at lære mere om opsætning og udførelse, se vores nyttige guide.

For at starte, lad os oprette en simpel SamlingerBenchmark klasse:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterationer = 5) public class CollectionsBenchmark {@State (Scope.Thread) offentlig statisk klasse MyState {privat Set medarbejderSet = nyt HashSet (); privat liste medarbejderliste = ny ArrayList (); private lange iterationer = 1000; privat medarbejdermedarbejder = ny medarbejder (100L, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {medarbejderSet.add (ny medarbejder (i, "John")); medarbejderliste.add (ny medarbejder (i, "John")); } medarbejderliste.add (medarbejder); employeeSet.add (medarbejder); }}}

Her opretter og initialiserer vi HashSet og en ArrayList af Medarbejder genstande:

offentlig klassemedarbejder {privat Lang id; privat strengnavn; // constructor and getter setters go here}

Vi tilføjer medarbejder = ny medarbejder (100L, “Harry”) forekomst som de sidste elementer i begge samlinger. Så vi tester medarbejder objektets opslagstid til det værst mulige tilfælde.

@OutputTimeUnit (TimeUnit.NANOSECONDS) angiver, at vi ønsker resultaterne i nanosekunder. Antallet af standard @Opvarmning iterationer er 5 i vores tilfælde. Det @BenchmarkMode er indstillet til Mode.AverageTime, hvilket betyder, at vi er interesserede i at beregne en gennemsnitlig køretid. For den første udførelse sætter vi iterationer = 1000 genstande i vores samlinger.

Derefter tilføjer vi vores benchmarkmetoder til CollectionsBenchmark klasse:

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

Her kontrollerer vi, om medarbejderliste indeholder medarbejder objekt.

Ligeledes har vi den velkendte test for medarbejderSæt:

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

Endelig kan vi køre testen:

offentlig statisk ugyldig hoved (String [] args) kaster Undtagelse {Valgmuligheder = ny OptionsBuilder (). inkluderer (CollectionsBenchmark.class.getSimpleName ()) .forks (1) .build (); ny Runner (optioner) .run (); }

Her er resultaterne:

Benchmark Mode Cnt Score Fejl Enheder CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns / op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns / op

Vi kan tydeligt se, at testArrayList metoden har 4035.646 ns gennemsnitlig opslagscore, mens testHashSet fungerer hurtigere med 9.456 ns gennemsnitlig.

Lad os nu øge antallet af elementer i vores test og køre det til iterationer = 10.000 poster:

Benchmark Mode Cnt Score Fejl Enheder CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns / op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns / op

Også her indeholder() i HashSet har en enorm præstationsfordel i forhold til ArrayList.

5. Konklusion

Denne hurtige opskrivning forklarer resultaterne af indeholder() metode til HashSet og ArrayList samlinger. Ved hjælp af JMH benchmarking har vi præsenteret præstationen for indeholder() for hver type samling.

Som en konklusion kan vi lære det det indeholder() metoden fungerer hurtigere i HashSet sammenlignet med en ArrayList.

Som sædvanlig er den komplette kode til denne artikel forbi på GitHub-projektet.