Performances de removeAll () dans un HashSet

1. Vue d'ensemble

HashSet est une collection pour stocker des éléments uniques.

Dans ce didacticiel, nous discuterons des performances de la méthode removeAll () dans la classe java.util.HashSet .

2. HashSet.removeAll ()

La méthode removeAll supprime tous les éléments contenus dans la collection :

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)); 

En conséquence, les éléments 1 et 3 seront supprimés de l'ensemble.

3. Mise en œuvre interne et complexité du temps

La méthode removeAll () détermine laquelle est la plus petite - l'ensemble ou la collection. Cela se fait en appelant la méthode size () sur l'ensemble et la collection.

Si la collection a moins d'éléments que l'ensemble , elle itère sur la collection spécifiée avec la complexité temporelle O ( n ). Il vérifie également si l'élément est présent dans l'ensemble avec la complexité temporelle O (1). Et si l'élément est présent, il est supprimé de l'ensemble en utilisant la méthode remove () de l'ensemble, qui a à nouveau une complexité temporelle de O (1). La complexité globale du temps est donc O ( n ) .

Si l'ensemble a moins d'éléments que la collection , alors il itère sur cet ensemble en utilisant O ( n ). Ensuite, il vérifie si chaque élément est présent dans la collection en invoquant sa méthode contains () . Et si un tel élément est présent, alors l'élément est supprimé de l'ensemble. Cela dépend donc de la complexité temporelle de la méthode contains () .

Maintenant, dans ce cas, si la collection est une ArrayList , la complexité temporelle de la méthode contains () est O ( m ). Donc, la complexité temporelle globale pour supprimer tous les éléments présents dans ArrayList de l'ensemble est O ( n * m ) .

Si la collection est à nouveau HashSet , la complexité temporelle de la méthode contains () est O (1). Donc, la complexité temporelle globale pour supprimer tous les éléments présents dans le HashSet de l'ensemble est O ( n ) .

4. Performance

Pour voir la différence de performance entre les 3 cas ci-dessus, écrivons un simple test de référence JMH.

Pour le premier cas, nous initialiserons l'ensemble et la collection, où nous avons plus d'éléments dans l'ensemble que la collection. Dans le second cas, nous initialiserons l'ensemble et la collection, où nous avons plus d'éléments dans la collection que l'ensemble. Et dans le troisième cas, nous initialiserons 2 ensembles, où nous aurons un 2ème ensemble ayant plus de nombre d'éléments que le 1er:

@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 } } }

Ensuite, nous ajoutons nos tests de référence:

@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); }

Et voici les résultats:

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

Nous pouvons voir que HashSet.removeAll () fonctionne assez mal lorsque le HashSet a moins d'éléments que la Collection , qui est passée en argument à la méthode removeAll () . Mais lorsque l'autre collection est à nouveau HashSet , les performances sont bonnes.

5. Conclusion

Dans cet article, nous avons vu les performances de removeAll () dans HashSet. Lorsque l'ensemble contient moins d'éléments que la collection, les performances de removeAll () dépendent de la complexité temporelle de la méthode contains () de la collection.

Comme d'habitude, le code complet de cet article est disponible à l'adresse over sur GitHub.