streamalism.org

1. Introduksjon

I denne hurtigveiledningen, vi skal diskutere ytelsen til inneholder () metoden tilgjengelig i java.util.HashSet og java.util.ArrayList. De er begge samlinger for lagring og manipulering av gjenstander.

HashSet er en samling for lagring av unike elementer. For å lære mer om HashSet, sjekk ut denne lenken.

ArrayList er en populær implementering av java.util.Liste grensesnitt.

Vi har en utvidet artikkel om ArrayList tilgjengelig her.

2. HashSet.contains ()

Internt, den HashSet implementering er basert på en HashMap forekomst. De inneholder () metode samtaler HashMap.containsKey (objekt).

Her sjekker det om gjenstand er på det interne kartet eller ikke. Det interne kartet lagrer data inne i nodene, kjent som bøtter. Hver bøtte tilsvarer en hash-kode generert med hashCode () metode. Så inneholder () bruker faktisk hashCode () metode for å finne objektets plassering.

La oss nå bestemme kompleksiteten i oppslagstiden. Før du går videre, må du sørge for at du er kjent med Big-O-notasjonen.

Gjennomsnittlig, de inneholder () av HashSet løper inn O (1) tid. Å få objektets bøtteplassering er en konstant tidsoperasjon. Tatt i betraktning mulige kollisjoner, kan oppslagstiden stige til logg (n) fordi den interne skuffestrukturen er en TreeMap.

Dette er en forbedring fra Java 7 som brukte en LinkedList for den interne skuffestrukturen. Generelt er hash-kodekollisjoner sjeldne. Så vi kan vurdere kompleksiteten til elementoppslag som O (1).

3. ArrayList.cfortsetter ()

Internt, ArrayList bruker indexOf (objekt) metode for å sjekke om objektet er i listen. De indexOf (objekt) metoden itererer hele matrisen og sammenligner hvert element med er lik (objekt) metode.

Å komme tilbake til kompleksitetsanalyse, ArrayList.inneholder () metoden krever På) tid. Så tiden vi bruker på å finne et bestemt objekt her, avhenger av antall elementer vi har i matrisen.

4. Referansetesting

La oss nå varme opp JVM med ytelsestest. Vi bruker JMH (Java Microbenchmark Harness) OpenJDK-produktet. For å lære mer om oppsett og utførelse, sjekk ut vår nyttige guide.

For å starte, la oss lage en enkel CollectionsBenchmark klasse:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterasjoner = 5) public class CollectionsBenchmark {@State (Scope.Thread) public static class MyState {private Set employeeSet = new HashSet (); private List medarbeiderliste = ny ArrayList (); private lange iterasjoner = 1000; privat ansatt ansatt = ny ansatt (100L, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {medarbeiderSet.add (ny ansatt (i, "John")); ansatteList.add (ny ansatt (jeg, "John")); } ansatteListe.add (ansatt); ansatteSet.add (ansatt); }}}

Her oppretter og initialiserer vi HashSet og en ArrayList av Ansatt gjenstander:

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

Vi legger til ansatt = ny ansatt (100L, “Harry”) forekomst som de siste elementene i begge samlingene. Så vi tester ansatt gjenstandens oppslagstid for det verste mulige tilfellet.

@OutputTimeUnit (TimeUnit.NANOSECONDS) indikerer at vi vil ha resultatene i nanosekunder. Antall standardinnstillinger @Varme opp iterasjoner er 5 i vårt tilfelle. De @BenchmarkMode er satt til Mode.AverageTime, noe som betyr at vi er interessert i å beregne en gjennomsnittlig kjøretid. For den første henrettelsen setter vi iterasjoner = 1000 gjenstander i samlingene våre.

Etter legger vi til våre referansemetoder i CollectionsBenchmark klasse:

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

Her sjekker vi om ansatteliste inneholder ansatt gjenstand.

På samme måte har vi den kjente testen for ansatt:

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

Til slutt kan vi kjøre testen:

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

Her er resultatene:

Referansemodus Cnt Score feil Enheter CollectionsBenchmark.testArrayList avgt 20 4035,646 ± 598,541 ns / op CollectionsBenchmark.testHashSet avgt 20 9,456 ± 0,729 ns / op

Vi kan tydelig se at testArrayList metoden har 4035.646 ns gjennomsnittlig oppslagspoeng, mens testHashSet utfører raskere med 9.456 ns gjennomsnittlig.

La oss nå øke antall teller i testen og kjøre den for iterasjoner = 10.000 elementer:

Referansemodus Cnt Score feil Enheter CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns / op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns / op

Også her er inneholder () i HashSet har en enorm ytelsesfordel i forhold til ArrayList.

5. Konklusjon

Denne raske oppskriften forklarer ytelsen til inneholder () metoden for HashSet og ArrayList samlinger. Ved hjelp av JMH benchmarking har vi presentert ytelsen til inneholder () for hver type samling.

Som en konklusjon kan vi lære det de inneholder () metoden fungerer raskere i HashSet sammenlignet med en ArrayList.

Som vanlig er den fullstendige koden for denne artikkelen over på GitHub-prosjektet.