Java >> Java tutorial >  >> Tag >> ArrayList

Ydelse af contains() i et HashSet vs ArrayList

ArrayList

1. Introduktion

I denne hurtige guide skal vi diskutere ydeevnen af ​​contains() 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 få flere oplysninger om HashSet, tjek dette link.

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

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

2. HashSet.contains()

Internt HashSet implementering er baseret på et HashMap  eksempel. Den contains() metode kalder HashMap.containsKey(object) .

Her tjekker den, om objektet er på det interne kort eller ej. Det interne kort gemmer data inde i noderne, kendt som buckets. Hver bucket svarer til en hash-kode genereret med hashCode()  metode. Så indeholder() bruger faktisk hashCode()  metode til at finde objektets  placering.

Lad os nu bestemme kompleksiteten af ​​opslagstiden. Før du går videre, skal du sørge for, at du er fortrolig med Big-O-notationen.

I gennemsnit indeholder () af HashSet kører i O(1) tid . Hent objektets skovlplacering er en konstant tidsoperation. Under hensyntagen til mulige kollisioner kan opslagstiden stige til log(n) fordi den interne bucket-struktur er et TreeMap .

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

3. ArrayList.c ontains()

Internt, ArrayList bruger indexOf(objekt) metode til at kontrollere, om objektet er på listen . indeksOf(objekt) metoden itererer hele arrayet og sammenligner hvert element med equals(object) metode.

For at komme tilbage til kompleksitetsanalyse, ArrayList .indeholder() metode kræver O(n) tid. Så den tid, vi bruger på at finde et bestemt objekt her, afhænger af antallet af elementer, vi har i arrayet.

4. Benchmark-test

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

Lad os starte med at oprette et simpelt CollectionsBenchmark klasse:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class CollectionsBenchmark {

    @State(Scope.Thread)
    public static class MyState {
        private Set<Employee> employeeSet = new HashSet<>();
        private List<Employee> employeeList = new ArrayList<>();

        private long iterations = 1000;

        private Employee employee = new Employee(100L, "Harry");

        @Setup(Level.Trial)
        public void setUp() {

            for (long i = 0; i < iterations; i++) {
                employeeSet.add(new Employee(i, "John"));
                employeeList.add(new Employee(i, "John"));
            }

            employeeList.add(employee);
            employeeSet.add(employee);
        }
    }
}

Her opretter og initialiserer vi HashSet og en ArrayList af medarbejder objekter:

public class Employee {

    private Long id;
    private String name;

    // constructor and getter setters go here
}

Vi tilføjer employee =new Employee(100L, "Harry")  instans som de sidste elementer til begge samlinger. Så vi tester medarbejderen objektets opslagstid for det værst tænkelige tilfælde.

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

Derefter føjer vi vores benchmarkmetoder til CollectionsBenchmark klasse:

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

Her tjekker vi om employeeList indeholder medarbejder objekt.

Ligeledes har vi den velkendte test for employeeSet :

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

Endelig kan vi køre testen:

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

Her er resultaterne:

Benchmark                           Mode  Cnt     Score     Error  Units
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 opslagsscore, mens testHashSet yder hurtigere med 9.456 ns i gennemsnit.

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

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

Også her indeholder contains() i HashSet har en enorm fordel i forhold til ArrayList .

5. Konklusion

Denne hurtige opskrivning forklarer ydelsen af ​​contains() metoden for HashSet og ArrayList samlinger. Ved hjælp af JMH-benchmarking har vi præsenteret ydeevnen for contains() for hver type samling.

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

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


Java tag