Prestazioni di removeAll () in un HashSet

1. Panoramica

HashSet è una raccolta per la memorizzazione di elementi unici.

In questo tutorial, discuteremo le prestazioni del metodo removeAll () nella classe java.util.HashSet .

2. HashSet.removeAll ()

Il metodo removeAll rimuove tutti gli elementi contenuti nella raccolta :

Set set = new HashSet(); set.add(1); set.add(2); set.add(3); set.add(4); Collection collection = new ArrayList(); collection.add(1); collection.add(3); set.removeAll(collection); Integer[] actualElements = new Integer[set.size()]; Integer[] expectedElements = new Integer[] { 2, 4 }; assertArrayEquals(expectedElements, set.toArray(actualElements)); 

Di conseguenza, gli elementi 1 e 3 verranno rimossi dal set.

3. Implementazione interna e complessità temporale

Il metodo removeAll () determina quale è più piccolo: il set o la raccolta. Questo viene fatto invocando il metodo size () sul set e sulla raccolta.

Se la raccolta ha meno elementi dell'insieme , itera sulla raccolta specificata con la complessità temporale O ( n ). Controlla inoltre se l'elemento è presente nell'insieme con complessità temporale O (1). E se l'elemento è presente, viene rimosso dal set utilizzando il metodo remove () del set, che ha ancora una complessità temporale di O (1). Quindi la complessità temporale complessiva è O ( n ) .

Se l'insieme ha meno elementi della raccolta , itera su questo insieme usando O ( n ). Quindi controlla se ogni elemento è presente nella raccolta invocando il suo metodo contains () . E se un tale elemento è presente, l'elemento viene rimosso dal set. Quindi questo dipende dalla complessità temporale del metodo contains () .

In questo caso, se la raccolta è un ArrayList , la complessità temporale del metodo contains () è O ( m ). Quindi la complessità temporale complessiva per rimuovere tutti gli elementi presenti nell'ArrayList dall'insieme è O ( n * m ) .

Se la raccolta è di nuovo HashSet , la complessità temporale del metodo contains () è O (1). Quindi la complessità temporale complessiva per rimuovere tutti gli elementi presenti nell'HashSet dall'insieme è O ( n ) .

4. Prestazioni

Per vedere la differenza di prestazioni tra i 3 casi precedenti, scriviamo un semplice test di benchmark JMH.

Per il primo caso, inizializzeremo il set e la raccolta, dove abbiamo più elementi nel set rispetto alla raccolta. Nel secondo caso, inizializzeremo l'insieme e la raccolta, dove abbiamo più elementi nella raccolta rispetto all'insieme. E nel terzo caso, inizializzeremo 2 set, dove avremo il secondo set con un numero di elementi maggiore del primo:

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 5) public class HashSetBenchmark { @State(Scope.Thread) public static class MyState { private Set employeeSet1 = new HashSet(); private List employeeList1 = new ArrayList(); private Set employeeSet2 = new HashSet(); private List employeeList2 = new ArrayList(); private Set employeeSet3 = new HashSet(); private Set employeeSet4 = new HashSet(); private long set1Size = 60000; private long list1Size = 50000; private long set2Size = 50000; private long list2Size = 60000; private long set3Size = 50000; private long set4Size = 60000; @Setup(Level.Trial) public void setUp() { // populating sets } } }

Successivamente, aggiungiamo i nostri test di benchmark:

@Benchmark public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) { return state.employeeSet1.removeAll(state.employeeList1); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance(MyState state) { return state.employeeSet2.removeAll(state.employeeList2); } @Benchmark public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) { return state.employeeSet3.removeAll(state.employeeSet4); }

Ed ecco i risultati:

Benchmark Mode Cnt Score Error Units HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns/op HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 ns/op HashSetBenchmark.testHashSetSmallerThanOtherHashset avgt 20 2672757.784 ± 224505.866 ns/op

Possiamo vedere che HashSet.removeAll () funziona piuttosto male quando HashSet ha meno elementi rispetto alla Collection , che viene passata come argomento al metodo removeAll () . Ma quando l'altra raccolta è di nuovo HashSet , le prestazioni sono buone.

5. conclusione

In questo articolo, abbiamo visto le prestazioni di removeAll () in HashSet. Quando l'insieme ha meno elementi della raccolta, le prestazioni di removeAll () dipendono dalla complessità temporale del metodo contains () della raccolta.

Come al solito, il codice completo di questo articolo è disponibile su GitHub.