streamalism.org

1. Bemutatkozás

Ebben a gyors útmutatóban megbeszéljük a tartalmaz () ban elérhető módszer java.util.HashSet és java.util.Tömb lista. Mindkettő tárgyak tárolására és manipulálására szolgáló gyűjtemény.

HashSet gyűjtemény egyedi elemek tárolására. Ha többet szeretne megtudni a HashSet, nézze meg ezt a linket.

Tömb lista a. népszerű megvalósítása java.util.List felület.

Van egy kiterjesztett cikkünk a Tömb lista elérhető itt.

2. A HashSet. Tartalmaz ()

Belsőleg az HashSet a megvalósítás a HashMap példa. A tartalmaz () metódus hívások HashMap.containsKey (object).

Itt ellenőrzi, hogy a tárgy szerepel a belső térképen, vagy sem. A belső térkép adatokat tárol a csomópontok belsejében, úgynevezett vödrök. Minden vödör megfelel a hash kód() módszer. Így tartalmaz () valójában használja hash kód() módszer a objektumé elhelyezkedés.

Most határozzuk meg a keresési idő összetettségét. Mielőtt továbblépne, győződjön meg róla, hogy ismeri a Big-O jelölést.

Átlagban, a tartalmaz () nak,-nek HashSet befut O (1) idő. A objektumé a vödör helye állandó idejű művelet. Az esetleges ütközéseket figyelembe véve a keresési idő elérheti napló (n) mert a belső vödörszerkezet a TreeMap.

Ez a Java 7 javítása, amely a LinkedList a belső vödörszerkezethez. Általában a hash-kód ütközések ritkák. Tehát tekinthetjük az elemek keresésének összetettségét O (1).

3. ArrayList.cmegkapja ()

Belsőleg, Tömb lista használja a indexOf (objektum) módszer annak ellenőrzésére, hogy az objektum szerepel-e a listán. A indexOf (objektum) metódus a teljes tömböt iterálja, és minden elemet összehasonlít a egyenlő (tárgy) módszer.

Visszatérve a komplexitás elemzéséhez, a Tömb lista.tartalmaz () módszer megköveteli Tovább) idő. Tehát az idő, amelyet egy adott objektum keresésére fordítunk itt, a tömbben lévő elemek számától függ.

4. Benchmark tesztelés

Most melegítsük fel a JVM-et a teljesítmény benchmark tesztjével. A JMH (Java Microbenchmark Harness) OpenJDK terméket fogjuk használni. Ha többet szeretne megtudni a beállításról és a végrehajtásról, olvassa el hasznos útmutatónkat.

Először hozzunk létre egy egyszerű CollectionsBenchmark osztály:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterációk = 5) public class CollectionsBenchmark {@State (Scope.Thread) public static class MyState {private Set workerSet = new HashSet (); private List workerList = new ArrayList (); privát hosszú iterációk = 1000; magán alkalmazott alkalmazott = új alkalmazott (100L, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {workerSet.add (new Employee (i, "John")); workerList.add (új alkalmazott (i, "John")); } workerList.add (alkalmazott); workerSet.add (alkalmazott); }}}

Itt létrehozunk és inicializálunk HashSet és egy Tömb lista nak,-nek Munkavállaló tárgyak:

public class Alkalmazott {private Long id; privát karakterlánc neve; // a konstruktor és a getter-beállítók ide mennek}

Hozzáadjuk a alkalmazott = új alkalmazott (100L, „Harry”) példát mindkét gyűjtemény utolsó elemeként. Tehát teszteljük a munkavállaló az objektum keresési ideje a lehető legrosszabb esetre.

@OutputTimeUnit (TimeUnit.NANOSECONDS) azt jelzi, hogy nanoszekundumokban akarjuk az eredményeket. Az alapértelmezettek száma @Bemelegítés az iterációk esetünkben 5. A @BenchmarkMode értékre van állítva Mode.AverageTime, ami azt jelenti, hogy érdekel minket egy átlagos futási idő kiszámítása. Az első kivégzéshez feltettük iterációk = 1000 gyűjteményeink tárgyai.

Ezt követően hozzáadjuk a benchmark módszereket a CollectionsBenchmark osztály:

@Benchmark nyilvános logikai tesztArrayList (MyState állapot) {return state.employeeList.contains (state.employee); }

Itt ellenőrizzük, hogy a workerList tartalmazza munkavállaló tárgy.

Hasonlóképpen, megvan a megszokott teszt alkalmazottSet:

@Benchmark nyilvános logikai tesztHashSet (MyState állapot) {return state.employeeSet.contains (state.employee); }

Végül lefuttathatjuk a tesztet:

public static void main (String [] args) dobja a Kivételt {Opciók opciók = új OpciókBuilder () .include (CollectionsBenchmark.class.getSimpleName ()) .villa (1) .build (); új Runner (opciók) .run (); }

Itt vannak az eredmények:

Benchmark Mode Cnt Score Hibaegységek CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns / op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns / op

Világosan láthatjuk, hogy a testArrayList módszer van 4035,646 ns átlagos keresési pontszám, míg a testHashSet gyorsabban teljesít 9.456 ns átlagban.

Most növeljük a tesztünk elemszámát, és futtassuk iterációk = 10 000 elem esetén:

Összehasonlító mód Cnt pontszám hiba egységek gyűjtemények gyűjteményekBenchmark.testArrayList átlag 20 20 57499,620 ± 11388,645 ns / op gyűjteményekBenchmark.testHashSet átlag 20 20,802 ± 1,164 ns / op

Itt is a tartalmaz () ban ben HashSet hatalmas teljesítményelőnnyel rendelkezik a Tömb lista.

5. Következtetés

Ez a gyors írás megmagyarázza a tartalmaz () módszere HashSet és Tömb lista gyűjtemények. A JMH benchmarking segítségével bemutattuk a teljesítményét tartalmaz () az egyes gyűjteménytípusokhoz.

Következtetésként megtudhatjuk, hogy a tartalmaz () módszer gyorsabban működik HashSet egy anhoz képest Tömb lista.

Szokás szerint a cikk teljes kódja befejeződött a GitHub projekten.