Prestazioni di contains () in un HashSet rispetto a un ArrayList

1. Introduzione

In questa guida rapida, discuteremo le prestazioni del metodo contains () disponibile in java.util. HashSet e java.util. ArrayList . Sono entrambe raccolte per immagazzinare e manipolare oggetti.

HashSet è una raccolta per la memorizzazione di elementi unici. Per saperne di più su HashSet, controlla questo link.

ArrayList è un'implementazione popolare dell'interfaccia java.util.List .

Abbiamo un articolo esteso su ArrayList disponibile qui.

2. HashSet.contains ()

Internamente, l' implementazione di HashSet è basata su un'istanza di HashMap . Il metodo contains () chiama HashMap.containsKey (object) .

Qui controlla se l' oggetto è nella mappa interna o meno. La mappa interna memorizza i dati all'interno dei nodi, noti come bucket. Ogni bucket corrisponde a un codice hash generato con il metodo hashCode () . Quindi contiene () sta effettivamente utilizzando il metodo hashCode () per trovare la posizione dell'oggetto .

Ora determiniamo la complessità del tempo di ricerca. Prima di andare avanti, assicurati di avere familiarità con la notazione Big-O.

In media, il contains () di HashSet viene eseguito in O (1) tempo . Ottenere la posizione del bucket dell'oggetto è un'operazione a tempo costante. Tenendo conto delle possibili collisioni, il tempo di ricerca può aumentare fino a log (n) perché la struttura del bucket interno è una TreeMap .

Si tratta di un miglioramento rispetto a Java 7 che utilizzava un LinkedList per la struttura del bucket interno. In generale, le collisioni di codice hash sono rare. Quindi possiamo considerare la complessità della ricerca degli elementi come O (1) .

3. ArrayList.c ontains ()

Internamente, ArrayList utilizza il metodo indexOf (oggetto) per verificare se l'oggetto è nell'elenco . Il metodo indexOf (oggetto) itera l'intero array e confronta ogni elemento con il metodo equals (oggetto) .

Tornando all'analisi della complessità, ArrayList . Il metodo contiene () richiede O (n) tempo. Quindi il tempo che impieghiamo per trovare un oggetto specifico qui dipende dal numero di elementi che abbiamo nell'array.

4. Test di benchmark

Ora, riscaldiamo la JVM con il test di benchmark delle prestazioni. Useremo il prodotto OpenJDK JMH (Java Microbenchmark Harness). Per saperne di più sulla configurazione e l'esecuzione, consulta la nostra guida utile.

Per iniziare, creiamo una semplice classe CollectionsBenchmark :

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 5) public class CollectionsBenchmark { @State(Scope.Thread) public static class MyState { private Set employeeSet = new HashSet(); private List 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); } } }

Qui creiamo e inizializziamo HashSet e un ArrayList di oggetti Employee :

public class Employee { private Long id; private String name; // constructor and getter setters go here }

Aggiungiamo l' istanza dipendente = new Employee (100L, "Harry") come ultimi elementi di entrambe le raccolte. Quindi testiamo il tempo di ricerca dell'oggetto dipendente per il caso peggiore possibile.

@OutputTimeUnit (TimeUnit.NANOSECONDS) indica che vogliamo i risultati in nanosecondi. Il numero di iterazioni @Warmup predefinite è 5 nel nostro caso. Il @BenchmarkMode è impostato su Mode.AverageTime , il che significa che siamo interessati a calcolare un tempo medio di esecuzione. Per la prima esecuzione, inseriamo iterazioni = 1000 elementi nelle nostre raccolte.

Successivamente, aggiungiamo i nostri metodi di benchmark alla classe CollectionsBenchmark :

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

Qui controlliamo se l'employeeList contiene dipendente oggetto.

Allo stesso modo, abbiamo il test familiare per EmployeeSet :

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

Infine, possiamo eseguire il test:

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

Ecco i risultati:

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

Possiamo vedere chiaramente che il metodo testArrayList ha un punteggio medio di ricerca di 4035,646 ns , mentre testHashSet si comporta più velocemente con una media di 9,456 ns .

Ora, aumentiamo il conteggio degli elementi nel nostro test ed eseguiamolo per iterazioni = 10.000 elementi:

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

Anche in questo caso, il contains () in HashSet ha un enorme vantaggio in termini di prestazioni rispetto a ArrayList .

5. conclusione

Questo breve articolo spiega le prestazioni del metodo contains () delle raccolte HashSet e ArrayList . Con l'aiuto del benchmarking JMH, abbiamo presentato le prestazioni di contains () per ogni tipo di raccolta.

In conclusione, possiamo imparare che il metodo contains () funziona più velocemente in HashSet rispetto a un ArrayList .

Come al solito, il codice completo per questo articolo è finito sul progetto GitHub.