Un guide sur HashSet en Java

1. Vue d'ensemble

Dans cet article, nous allons plonger dans HashSet. C'est l'une des implémentations de Set les plus populaires ainsi qu'une partie intégrante du Java Collections Framework.

2. Introduction à HashSet

HashSet est l'une des structures de données fondamentales de l'API Java Collections .

Rappelons les aspects les plus importants de cette implémentation:

  • Il stocke des éléments uniques et autorise les valeurs nulles
  • Il est soutenu par un HashMap
  • Il ne conserve pas l'ordre d'insertion
  • Ce n'est pas thread-safe

Notez que ce HashMap interne est initialisé lorsqu'une instance du HashSet est créée:

public HashSet() { map = new HashMap(); }

Si vous souhaitez approfondir le fonctionnement de HashMap , vous pouvez lire l'article qui y est consacré ici.

3. L'API

Dans cette section, nous allons passer en revue les méthodes les plus couramment utilisées et jeter un œil à quelques exemples simples.

3.1. ajouter()

La méthode add () peut être utilisée pour ajouter des éléments à un ensemble. Le contrat de méthode indique qu'un élément ne sera ajouté que s'il n'est pas déjà présent dans un ensemble. Si un élément a été ajouté, la méthode renvoie true, sinon - false.

Nous pouvons ajouter un élément à un HashSet comme:

@Test public void whenAddingElement_shouldAddElement() { Set hashset = new HashSet(); assertTrue(hashset.add("String Added")); }

Du point de vue de la mise en œuvre, la méthode add est extrêmement importante. Les détails d'implémentation illustrent comment le HashSet fonctionne en interne et exploite la méthode put de HashMap :

public boolean add(E e) { return map.put(e, PRESENT) == null; }

La variable map est une référence au HashMap de sauvegarde interne:

private transient HashMap map;

Ce serait une bonne idée de se familiariser d'abord avec le hashcode pour avoir une compréhension détaillée de la façon dont les éléments sont organisés dans des structures de données basées sur le hachage.

En résumé:

  • Un HashMap est un tableau de buckets avec une capacité par défaut de 16 éléments - chaque bucket correspond à une valeur de hashcode différente
  • Si plusieurs objets ont la même valeur de hashcode, ils sont stockés dans un seul compartiment
  • Si le facteur de charge est atteint, un nouveau tableau est créé deux fois la taille du précédent et tous les éléments sont remaniés et redistribués entre les nouveaux buckets correspondants
  • Pour récupérer une valeur, nous hachons une clé, la modifions, puis allons dans un compartiment correspondant et recherchons dans la liste liée potentielle au cas où il y aurait plus d'un objet

3.2. contient ()

Le but de la méthode contains est de vérifier si un élément est présent dans un HashSet donné . Il renvoie true si l'élément est trouvé, sinon false.

Nous pouvons rechercher un élément dans le HashSet :

@Test public void whenCheckingForElement_shouldSearchForElement() { Set hashsetContains = new HashSet(); hashsetContains.add("String Added"); assertTrue(hashsetContains.contains("String Added")); }

Chaque fois qu'un objet est passé à cette méthode, la valeur de hachage est calculée. Ensuite, l'emplacement du compartiment correspondant est résolu et parcouru.

3.3. retirer()

La méthode supprime l'élément spécifié de l'ensemble s'il est présent. Cette méthode retourne true si un ensemble contenait l'élément spécifié.

Voyons un exemple de travail:

@Test public void whenRemovingElement_shouldRemoveElement() { Set removeFromHashSet = new HashSet(); removeFromHashSet.add("String Added"); assertTrue(removeFromHashSet.remove("String Added")); }

3.4. clair()

Nous utilisons cette méthode lorsque nous avons l'intention de supprimer tous les éléments d'un ensemble. L'implémentation sous-jacente efface simplement tous les éléments du HashMap sous-jacent .

Voyons cela en action:

@Test public void whenClearingHashSet_shouldClearHashSet() { Set clearHashSet = new HashSet(); clearHashSet.add("String Added"); clearHashSet.clear(); assertTrue(clearHashSet.isEmpty()); }

3.5. Taille()

C'est l'une des méthodes fondamentales de l'API. Il est largement utilisé car il aide à identifier le nombre d'éléments présents dans le HashSet . L'implémentation sous-jacente délègue simplement le calcul à la méthode size () de HashMap .

Voyons cela en action:

@Test public void whenCheckingTheSizeOfHashSet_shouldReturnThesize() { Set hashSetSize = new HashSet(); hashSetSize.add("String Added"); assertEquals(1, hashSetSize.size()); }

3.6. est vide()

Nous pouvons utiliser cette méthode pour déterminer si une instance donnée d'un HashSet est vide ou non. Cette méthode renvoie true si l'ensemble ne contient aucun élément:

@Test public void whenCheckingForEmptyHashSet_shouldCheckForEmpty() { Set emptyHashSet = new HashSet(); assertTrue(emptyHashSet.isEmpty()); }

3.7. itérateur ()

La méthode renvoie un itérateur sur les éléments de l' ensemble . Les éléments sont visités sans ordre particulier et les itérateurs sont rapides .

Nous pouvons observer l'ordre d'itération aléatoire ici:

@Test public void whenIteratingHashSet_shouldIterateHashSet() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } }

If the set is modified at any time after the iterator is created in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException.

Let's see that in action:

@Test(expected = ConcurrentModificationException.class) public void whenModifyingHashSetWhileIterating_shouldThrowException() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while (itr.hasNext()) { itr.next(); hashset.remove("Second"); } } 

Alternatively, had we used the iterator's remove method, then we wouldn't have encountered the exception:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while (itr.hasNext()) { String element = itr.next(); if (element.equals("Second")) itr.remove(); } assertEquals(2, hashset.size()); }

The fail-fast behavior of an iterator cannot be guaranteed as it's impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.

Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it'd be wrong to write a program that depended on this exception for its correctness.

4. How HashSet Maintains Uniqueness?

When we put an object into a HashSet, it uses the object's hashcode value to determine if an element is not in the set already.

Each hash code value corresponds to a certain bucket location which can contain various elements, for which the calculated hash value is the same. But two objects with the same hashCode might not be equal.

So, objects within the same bucket will be compared using the equals() method.

5. Performance of HashSet

The performance of a HashSet is affected mainly by two parameters – its Initial Capacity and the Load Factor.

The expected time complexity of adding an element to a set is O(1) which can drop to O(n) in the worst case scenario (only one bucket present) – therefore, it's essential to maintain the right HashSet's capacity.

An important note: since JDK 8, the worst case time complexity is O(log*n).

The load factor describes what is the maximum fill level, above which, a set will need to be resized.

We can also create a HashSet with custom values for initial capacity and load factor:

Set hashset = new HashSet(); Set hashset = new HashSet(20); Set hashset = new HashSet(20, 0.5f); 

In the first case, the default values are used – the initial capacity of 16 and the load factor of 0.75. In the second, we override the default capacity and in the third one, we override both.

A low initial capacity reduces space complexity but increases the frequency of rehashing which is an expensive process.

On the other hand, a high initial capacity increases the cost of iteration and the initial memory consumption.

As a rule of thumb:

  • A high initial capacity is good for a large number of entries coupled with little to no iteration
  • A low initial capacity is good for few entries with a lot of iteration

It's, therefore, very important to strike the correct balance between the two. Usually, the default implementation is optimized and works just fine, should we feel the need to tune these parameters to suit the requirements, we need to do judiciously.

6. Conclusion

In this article, we outlined the utility of a HashSet, its purpose as well as its underlying working. We saw how efficient it is in terms of usability given its constant time performance and ability to avoid duplicates.

We studied some of the important methods from the API, how they can help us as a developer to use a HashSet to its potential.

As always, code snippets can be found over on GitHub.