Performances de contains () dans un HashSet vs ArrayList

1. Introduction

Dans ce guide rapide, nous allons discuter des performances de la méthode contains () disponible dans java.util. HashSet et java.util. ArrayList . Ce sont tous deux des collections pour stocker et manipuler des objets.

HashSet est une collection pour stocker des éléments uniques. Pour en savoir plus sur le HashSet, consultez ce lien.

ArrayList est une implémentation populaire de l' interface java.util.List .

Nous avons un article détaillé sur la ArrayList disponible ici.

2. HashSet.contains ()

En interne, l' implémentation HashSet est basée sur une instance HashMap . La méthode contains () appelle HashMap.containsKey (object) .

Ici, il vérifie si l' objet est dans la carte interne ou non. La carte interne stocke les données à l'intérieur des nœuds, appelés buckets. Chaque compartiment correspond à un code de hachage généré avec la méthode hashCode () . Donc contains () utilise en fait la méthode hashCode () pour trouver l' emplacement de l' objet .

Déterminons maintenant la complexité du temps de recherche. Avant d'aller de l'avant, assurez-vous que vous êtes familiarisé avec la notation Big-O.

En moyenne, le contient () de HashSet fonctionne en O (1) temps . L'obtention de l' emplacement du compartiment de l' objet est une opération à temps constant. En tenant compte des collisions possibles, le temps de recherche peut passer à log (n) car la structure interne du compartiment est une TreeMap .

Il s'agit d'une amélioration par rapport à Java 7 qui utilisait une LinkedList pour la structure interne du bucket. En général, les collisions de code de hachage sont rares. Nous pouvons donc considérer la complexité de la recherche d'éléments comme O (1) .

3. ArrayList.c ontains ()

En interne, ArrayList utilise la méthode indexOf (object) pour vérifier si l'objet est dans la liste . La méthode indexOf (object) itère le tableau entier et compare chaque élément avec la méthode equals (object) .

Revenons à l'analyse de complexité, la ArrayList . La méthode contains () nécessite un temps O (n) . Ainsi, le temps que nous passons à trouver un objet spécifique ici dépend du nombre d'éléments que nous avons dans le tableau.

4. Tests de référence

Maintenant, réchauffons la JVM avec le test de performance. Nous utiliserons le produit OpenJDK JMH (Java Microbenchmark Harness). Pour en savoir plus sur la configuration et l'exécution, consultez notre guide utile.

Pour commencer, créons une classe CollectionsBenchmark simple :

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

Ici, nous créons et initialisons HashSet et une ArrayList d' objets Employee :

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

Nous ajoutons l' instance employee = new Employee (100L, «Harry») comme dernier élément des deux collections. Nous testons donc l' heure de recherche de l'objet employé pour le pire des cas.

@OutputTimeUnit (TimeUnit.NANOSECONDS) indique que nous voulons les résultats en nanosecondes. Le nombre d' itérations @Warmup par défaut est de 5 dans notre cas. Le @BenchmarkMode est défini sur Mode.AverageTime , ce qui signifie que nous sommes intéressés par le calcul d'un temps d'exécution moyen. Pour la première exécution, nous mettons des itérations = 1000 éléments dans nos collections.

Ensuite, nous ajoutons nos méthodes de référence à la classe CollectionsBenchmark :

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

Ici, nous vérifions si la liste d' employés contient un objet employé .

De même, nous avons le test familier pour employeeSet :

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

Enfin, nous pouvons lancer le test:

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

Voici les résultats:

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

Nous pouvons clairement voir que la méthode testArrayList a un score de recherche moyen de 4035,646 ns , tandis que le testHashSet fonctionne plus rapidement avec 9,456 ns en moyenne.

Maintenant, augmentons le nombre d'éléments dans notre test et exécutons-le pour des itérations = 10.000 éléments:

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

Ici aussi, le contains () dans HashSet a un énorme avantage en termes de performances par rapport à ArrayList .

5. Conclusion

Cette description rapide explique les performances de la méthode contains () des collections HashSet et ArrayList . Avec l'aide du benchmarking JMH, nous avons présenté les performances de contains () pour chaque type de collection.

En conclusion, nous pouvons apprendre que la méthode contains () fonctionne plus rapidement dans HashSet par rapport à une ArrayList .

Comme d'habitude, le code complet de cet article est terminé sur le projet GitHub.