Výkonnosť contains () v HashSet vs ArrayList

1. Úvod

V tomto rýchlom sprievodcovi ideme diskutovať o výkonnosti obsahuje () metóda dostupná v java.util.HashSet a java.util.ArrayList. Sú to zbierky na ukladanie a manipuláciu s objektmi.

HashSet je kolekcia na ukladanie jedinečných prvkov. Ak sa chcete dozvedieť viac o HashSet, pozrite sa na tento odkaz.

ArrayList je populárna implementácia java.util.List rozhranie.

Máme rozšírený článok o ArrayList k dispozícii tu.

2. HashSet.contains ()

Vnútorne HashSet implementácia je založená na a HashMap inštancia. The obsahuje () volania metód HashMap.containsKey (objekt).

Tu sa kontroluje, či objekt je na internej mape alebo nie. Interná mapa uchováva údaje vo vnútri uzlov, známe ako segmenty. Každému segmentu zodpovedá hash kód vygenerovaný pomocou hashCode () metóda. Takže obsahuje () v skutočnosti používa hashCode () metóda na vyhľadanie objektu umiestnenie.

Teraz poďme určiť časovú náročnosť vyhľadávania. Predtým, ako budete pokračovať, nezabudnite poznať zápis Big-O.

V priemere, the obsahuje () z HashSet vbehne dovnútra O (1) čas. Získanie objektu umiestnenie lopaty je operácia v konštantnom čase. Ak vezmeme do úvahy možné kolízie, môže čas na vyhľadanie stúpnuť denník (n) pretože vnútorná štruktúra vedra je a TreeMap.

Toto je vylepšenie oproti Java 7, ktorá používa a LinkedList pre vnútornú štruktúru vedra. Vo všeobecnosti sú kolízie hash kódu zriedkavé. Zložitosť vyhľadávania prvkov teda môžeme považovať za O (1).

3. ArrayList.cvlastní ()

Interne, ArrayList používa indexOf (objekt) metóda na kontrolu, či je objekt v zozname. The indexOf (objekt) metóda iteruje celé pole a porovnáva každý prvok s rovná sa (objekt) metóda.

Návrat k analýze zložitosti ArrayList.obsahuje () metóda vyžaduje O (n) čas. Takže čas, ktorý tu strávime nájdením konkrétneho objektu, závisí od počtu položiek, ktoré máme v poli.

4. Porovnávacie testovanie

Poďme si teraz zahriať JVM testom výkonnosti. Použijeme produkt OpenJDK JMH (Java Microbenchmark Harness). Ak sa chcete dozvedieť viac informácií o nastavení a vykonaní, prečítajte si nášho užitočného sprievodcu.

Na začiatok si vytvoríme jednoduchý CollectionBenchmark trieda:

@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.NANOSECONDS) @Warmup (iterations = 5) verejná trieda CollectionsBenchmark {@State (Scope.Thread) verejná statická trieda MyState {private Set employeeSet = new HashSet (); private List employeeList = nový ArrayList (); súkromné ​​dlhé iterácie = 1 000; súkromný zamestnanec zamestnanec = nový zamestnanec (100 l, "Harry"); @Setup (Level.Trial) public void setUp () {for (long i = 0; i <iterations; i ++) {employeeSet.add (new Employee (i, "John")); employeeList.add (nový zamestnanec (i; "John")); } employeeList.add (zamestnanec); employeeSet.add (zamestnanec); }}}

Tu tvoríme a inicializujeme HashSet a an ArrayList z Zamestnanec objekty:

public class Employee {private Long id; súkromné ​​meno reťazca; // nastavovač konštruktorov a getrov nájdete tu}

Pridáme zamestnanec = nový zamestnanec (100 l, „Harry“) inštancia ako posledné prvky oboch zbierok. Takže otestujeme zamestnanec čas vyhľadania objektu pre najhorší možný prípad.

@OutputTimeUnit (TimeUnit.NANOSECONDS) naznačuje, že chceme výsledky v nanosekundách. Počet predvolených @ Zahrievanie iterácie sú v našom prípade 5. The @BenchmarkMode je nastavený na Mode.AverageTime, čo znamená, že nás zaujíma výpočet priemernej doby chodu. Pri prvej poprave sme dali iterácie = 1 000 položiek v našich zbierkach.

Potom pridáme naše referenčné metódy do CollectionBenchmark trieda:

@Benchmark public boolean testArrayList (stav MyState) {návrat state.employeeList.contains (state.employee); }

Tu skontrolujeme, či zoznam zamestnancov obsahuje zamestnanec objekt.

Rovnako máme známy test na zamestnanecSet:

@Benchmark public boolean testHashSet (stav MyState) {návrat state.employeeSet.contains (state.employee); }

Nakoniec môžeme spustiť test:

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

Tu sú výsledky:

Režim Benchmark Cnt Skóre Chyba Jednotky CollectionsBenchmark.testArrayList priem. 20 4035 646 ± 598 541 ns / op CollectionsBenchmark.testHashSet priem. 20 9 456 ± 0,729 ns / op

Jasne vidíme, že testArrayList metóda má 4035,646 ns priemerné skóre vyhľadávania, zatiaľ čo testHashSet vykonáva rýchlejšie s 9,456 ns v priemere.

Teraz zvýšime počet prvkov v našom teste a spustme ho pre iterácie = 10 000 položiek:

Režim Benchmark Cnt Skóre Chyba Jednotky CollectionsBenchmark.testArrayList priem. 20 57499,620 ± 11388,645 ns / op CollectionsBenchmark.testHashSet priem. 20 11,802 ± 1,164 ns / op

Aj tu obsahuje () v HashSet má obrovskú výkonnostnú výhodu oproti ArrayList.

5. Záver

Toto rýchle napísanie vysvetľuje výkon systému obsahuje () metóda HashSet a ArrayList zbierky. S pomocou benchmarkingu JMH sme predstavili výkonnosť obsahuje () pre každý typ zberu.

Na záver sa to môžeme naučiť the obsahuje () metóda funguje rýchlejšie v HashSet v porovnaní s ArrayList.

Úplný kód tohto článku je ako obvykle v projekte GitHub ukončený.


$config[zx-auto] not found$config[zx-overlay] not found