Java Reskilling Collections 02: Set
Collections Java : utiliser les Sets
Dans les quêtes sur les collections Java, tu apprendras à partir d'exemples tirés du domaine de notre application d'exemple Tariff-Manager.
Dans cette quête, les collections Java servent à stocker et récupérer les clients de notre application Tariff-Manager. Il existe différents types de collections, et dans cette quête nous allons nous intéresser aux Sets.
🤓 À la fin de cette quête, tu sauras :
✅Comprendre comment fonctionne le Set (ensemble, une collection sans doublons) en Java
✅Connaître la différence entre les implémentations de Collection (collection, l'interface parente de toutes ces structures) que sont List (liste) et Set
✅Savoir utiliser Set pour des collections d'éléments uniques
✅Savoir créer un Set trié par ordre d'insertion ou par valeur
👀 Contenu de la quête
- Interface
Set - Implémentation
HashSet - Utilisation et méthodes
👉Interface Set
Tu as vu précédemment comment ajouter et trier des éléments dans une List. C'est pratique, mais il y a un inconvénient : un élément sera forcément ajouté à une liste, même s'il est déjà présent. Tu te retrouves inévitablement avec des doublons.
Il existe une interface pour contourner ce problème : le Set !
Contrairement à une liste, un set n'est pas ordonné : il ne faut pas le voir comme un tableau, mais plutôt comme un tiroir dans lequel tu rangerais tes éléments.
La duplication n'est pas possible : si tu insères un élément déjà existant dans un set, rien ne se passera. C'est aussi valable pour la valeur null. Un set ne peut la contenir qu'une seule fois !
Les sets sont représentés en Java par l'interface Set, qui hérite de Collection.
Comme indiqué plus haut, contrairement à une List, les éléments ajoutés à un Set ne sont pas ordonnés : quand un élément est ajouté, aucun indice numérique ne lui est attribué.
Il existe plusieurs implémentations de l'interface Set, parmi lesquelles :
- sans ordre défini, avec
HashSet - dans l'ordre d'insertion, avec
LinkedHashSet - dans l'ordre de la valeur, avec
TreeSet
👉Implémentation HashSet
Si l'ordre des éléments n'a pas d'importance, il est conseillé d'utiliser l'implémentation HashSet.
Pour créer un nouveau HashSet vide, tu devras créer une instance de la classe et la stocker dans une référence :
// is ok, but unneccesarily restricted by HashSet
HashSet<Customer> market = new HashSet<>();
// better use interfaces if possible (Set), use HashSet as implementation
Set<Customer> market = new HashSet<>();
Un HashSet fonctionnera presque à l'identique d'une ArrayList, avec l'avantage de ne pas pouvoir contenir d'élément en double, mais l'inconvénient de ne pas avoir d'ordre.
Les méthodes sont globalement les mêmes que pour une ArrayList, avec quelques différences notables :
👉Utilisation et méthodes
Insertion
Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
Customer deb = new Customer("Debbie Downer");
Customer gus = new Customer("Gloomy Gus");
Set<Customer> market = new HashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
Ajouter un élément à un set renvoie un boolean : il indique si l'élément a vraiment été ajouté ou non (dans le cas d'un doublon) :
boolean addJoeFirst = market.add(joe); // true
boolean addJoeAgain = market.add(joe); // false
Suppression
Un élément n'ayant pas d'indice dans un set, tu ne peux le supprimer qu'avec l'objet d'origine en paramètre :
boolean removeJoeFirst = market.remove(joe); // true
boolean removeJoeAgain = market.remove(joe); // false
Parcourir
Comme un set n'a pas d'indices, tu ne peux le parcourir qu'avec une boucle... for-each :
Set<Customer> market = new HashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(food.getName());
}
Attention : l'ordre des éléments n'est pas garanti !
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
Performance
Il faut donc se poser la question : dans le cas où limiter la duplication des objets n'est pas ta priorité, y a-t-il un intérêt à utiliser un HashSet ?
Ça dépend : c'est une question de performance. Quand on ajoute et supprime des éléments de façon répétée :
- avec peu d'éléments, une
ArrayListest meilleure qu'unHashSet - au-delà de ce seuil, plus tu as d'éléments, plus un
HashSetsera performant face à uneArrayList
Crédit Jeff Bridgman
Tu trouveras les détails de la procédure dans la ressource.
Si tu n'as pas besoin de parcourir ta collection d'éléments dans un ordre précis et que tu as régulièrement des actions d'ajout et de suppression : utilise un HashSet !
Implémentation LinkedHashSet
Un set LinkedHashSet évite toujours la duplication, mais permet aussi d'ordonner les éléments de la collection selon l'ordre des insertions.
Ainsi, si tu ajoutes des éléments à un set puis que tu le parcours, l'itération se fera dans l'ordre, du premier au dernier élément ajouté.
Set<Customer> market = new LinkedHashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(food.getName());
}
Cette fois, l'ordre sera garanti :
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
Supprimer un élément d'un LinkedHashSet ne changera pas l'ordre d'origine (l'élément supprimé sera bien sûr retiré !).
Bien que les éléments soient classés dans l'ordre d'insertion, ils n'ont pas d'indice attribué. Chaque élément connaît l'élément qui le précède et celui qui le suit directement (puisqu'ils sont liés !), mais il ne connaît pas sa place dans la chaîne.
Implémentation triée : TreeSet
Un TreeSet permet de trier les éléments par valeur.
Si tu essaies de stocker puis de parcourir les éléments Food contenus dans un TreeSet :
Set<Customer> market = new TreeSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(customer.getName());
}
Tu vas obtenir l'erreur suivante :
class Customer cannot be cast to class java.lang.Comparable
En effet : tu n'as jamais précisé comment les éléments devaient être triés !
Pour utiliser un TreeSet, ta classe d'éléments doit implémenter Comparable.
Voici une implémentation qui permet de trier les éléments par ordre alphabétique sur le nom :
public class Customer implements Comparable<Customer> {
@Override
public int compareTo(Customer customer) {
return this.getName().compareTo(customer.getName());
}
//...
}
Ainsi, le résultat du parcours sera :
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
Pas besoin d'utiliser le
sortavec unTreeSet: les éléments sont triés par défaut !
La classe TreeSet contient quelques méthodes supplémentaires, par exemple :
Accéder aux éléments : first() et last()
Permettent de récupérer respectivement le premier et le dernier élément d'un set :
Customer first = market.first();
Customer last = market.last();
boolean containFirst = market.contains(first); // true
boolean containLast = market.contains(last); // true
Récupérer les éléments : pollFirst() et pollLast()
Permettent de récupérer et de supprimer le premier et le dernier élément d'un set :
Customer first = market.pollFirst();
Customer last = market.pollLast();
boolean containFirst = market.contains(first); // false
boolean containLast = market.contains(last); // false
Inverser l'ordre : descendingSet()
Permet de parcourir un set dans le sens inverse :
for (Customer customer : market.descendingSet()) {
System.out.println(customer.getName());
}
Extraire des sous-ensembles : subSet(E fromElement, E toElement)
Renvoie un sous-ensemble d'éléments, allant de fromElement (inclus) à toElement (non inclus).
Il est possible de décider d'inclure ou non le premier et le dernier élément, grâce à la surcharge de la méthode : subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive).
La sélection se fait sur l'implémentation de Comparable. Dans notre exemple, les éléments sont triés par nom : tu sélectionneras donc les éléments entre le nom de départ (inclus) et le nom de fin (non inclus) :
Set<Customer> market = new TreeSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(customer.getName());
}
// customer order : ["..."]
for (Customer customer : market.subSet(cat, deb)) {
System.out.println(customer.getName());
}
Les éléments, par ordre alphabétique de nom, entre Cathy (inclus) et Gus (non inclus) sont :
$ Chatty Cathy
$ Debbie Downer
☝️Résumé
Java propose une interface Collection pour stocker, récupérer, mettre à jour et supprimer des objets Java. Pour utiliser l'interface, une implémentation doit être instanciée. Il existe plusieurs implémentations de l'interface Collection :
Set(interface qui étend Collection) ->HashSet(implémentation, non triée, non ordonnée)Set(interface qui étend Collection) ->LinkedHashSet(implémentation, ordonnée)Set(interface qui étend Collection) ->TreeSet(implémentation, triée)
Dans nos exemples, nous avons utilisé Set, qui est lui-même une interface. Comme implémentation pour les exemples, nous avons utilisé HashSet. Il existe beaucoup d'autres implémentations de Set disponibles en Java, qui diffèrent en complexité et en comportement à l'exécution, et qui doivent être évaluées selon le cas d'usage précis.
La différence entre les listes et les sets : les listes sont ordonnées (mais pas triées !) les sets ne contiennent pas de doublons !
Dans cette quête, tu as appris à...
- Créer un Set
- Insérer, modifier et supprimer des éléments dans un Set
- Parcourir les éléments d'un Set
- Utiliser des sous-ensembles et des méthodes de l'interface Set, comme
subSetoudescendingSet
Pour refaire ces tâches, clone l'application d'exemple Tariff-Manager, bascule sur la branche block_2_complete et regarde dev.wcs.nad.tariffmanager.customer.CustomerCollectionTest ainsi que le test unitaire shouldDemonstrateJavaCollectionsWithSets.
Challenge
C'est un challenge de type Quizz.
Références
- Photo de Sebastian Svenson sur Unsplash
Java Collections: Using Sets
In the quests about Java Collections you will learn with examples from the domain of our sample application Tariff-Manager.
In this quest Java Collections are used for storing and retrieving customers of our Tariff-Manager application. There are different types of collections, in this quest we will look at Sets.
🤓 By the end of this quest, you will:
✅Understand how Set works in Java
✅Know the difference between the Collection implementations List and Set
✅Know how to use Set for collections of unique elements
✅Know how to create a Set sorted by order of insertion or by value
👀 Content of the quest
- Interface
Set - Implementation
HashSet - Use and Methods
👉Interface Set
You saw earlier how to add and sort items in a List. It is convenient, but there is a drawback: an element will necessarily be added to a list, even if it is already present. You inevitably end up with duplicates.
There is an interface to overcome this problem: Set!
Unlike a list, a set is not ordered: you should not think of it as an array, but more like a drawer in which you would store your items.
Duplication is not possible: if you insert an already existing element into a set, nothing will happen. This is also valid for the value null. A set can only contain it once!
The sets are represented in Java by the interface Set who inherits Collection.
As mentioned earlier, unlike a List, items added to a Set are not ordered: when an element is added, no numerical index is assigned to it.
There are several implementations of the interface Set including:
- without a defined sequence, with
HashSet - in order of insertion, with
LinkedHashSet - in order of value, with
TreeSet
👉Implementation HashSet
If the order of the elements does not matter, it is advisable to use the implementation HashSet.
To create a new HashSet empty, you'll have to create an instance of the class and store it in a reference:
// is ok, but unneccesarily restricted by HashSet
HashSet<Customer> market = new HashSet<>();
// better use interfaces if possible (Set), use HashSet as implementation
Set<Customer> market = new HashSet<>();
A HashSet will function almost identically to a ArrayList with the advantage of not being able to contain a duplicate element, but the disadvantage of not having an order.
The methods are essentially the same as for a ArrayList with some notable differences:
👉Use and Methods
Insertion
Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
Customer deb = new Customer("Debbie Downer");
Customer gus = new Customer("Gloomy Gus");
Set<Customer> market = new HashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
Adding an element to a set returns a boolean: it indicates whether the element has really been added or not (in the case of a duplicate):
boolean addJoeFirst = market.add(joe); // true
boolean addJoeAgain = market.add(joe); // false
Deletion
An element having no index in a set, you can only delete it with the original object in parameter:
boolean removeJoeFirst = market.remove(joe); // true
boolean removeJoeAgain = market.remove(joe); // false
Iterate
Since a set has no clues, you can only go through it with a loop... for-each:
Set<Customer> market = new HashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(food.getName());
}
Attention: the order of the elements is not guaranteed!
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
Performance
So you have to ask yourself the question: when the case where limiting the duplication of objects is not your priority, is there any interest in using an HashSet?
It depends: it's performance-based. When repeatedly adding and deleting items in it:
- with few elements, an
ArrayListis better than aHashSet - beyond that threshold, the more elements you have, the more of a
HashSetwill perform well in the face of anArrayList
Credit Jeff Bridgman
You'll find the details of the procedure in the resource.
If you don't need to browse your collection of items in a specific order and you regularly have add and delete actions: use a HashSet!
Implementation LinkedHashSet
One set LinkedHashSet always avoids duplication, but also allows you to order the elements in the collection by the sequence of insertions.
Thus, if you add elements to a set and then browse through the set, the iteration will be done in order from the first to the last element added.
Set<Customer> market = new LinkedHashSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(food.getName());
}
This time order will be guaranteed:
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
Delete an item from a LinkedHashSet will not change the original order (the deleted item will be removed, of course!).
Although the items are sorted in order of insertion, they do not have an assigned index. Each element knows the element that precedes it and the element that directly follows it (as they are linked!), but it does not know its place in the chain.
Sorted Implementation: TreeSet
A TreeSet allows you to sort items by value.
If you try to store and then browse through the items Food contained in a TreeSet:
Set<Customer> market = new TreeSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(customer.getName());
}
You're gonna get the next mistake:
class Customer cannot be cast to class java.lang.Comparable
Indeed: you never specified how the items should be sorted!
In order to use a TreeSet your element class has to implement Comparable.
Here is an implementation that allows you to sort the elements in alphabetical order on the name:
public class Customer implements Comparable<Customer> {
@Override
public int compareTo(Customer customer) {
return this.getName().compareTo(customer.getName());
}
//...
}
Thus, the result of the course will be:
$ Average Joe
$ Cathy Cat
$ Debbie Downer
$ Gloomy Gus
No need to use the
sortwith aTreeSet: items are sorted by default!
The class TreeSet contains some additional methods, for example:
Accessing Elements: first() and last()
Allow to retrieve respectively the first and the last element of a set:
Customer first = market.first();
Customer last = market.last();
boolean containFirst = market.contains(first); // true
boolean containLast = market.contains(last); // true
Retrieving Elements: pollFirst() and pollLast()
Allows you to retrieve and remove the first and last elements of a set:
Customer first = market.pollFirst();
Customer last = market.pollLast();
boolean containFirst = market.contains(first); // false
boolean containLast = market.contains(last); // false
Reversing Order: descendingSet()
Allows you to browse a set in the opposite direction:
for (Customer customer : market.descendingSet()) {
System.out.println(customer.getName());
}
Extracting Subsets: subSet(E fromElement, E toElement)
Returns a subset of elements, ranging from fromElement (included) and toElement (not included).
It is possible to decide whether or not to include the first and last elements, thanks to the overloading of the method: subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive).
The selection is made on the implementation of Comparable. In our example, the elements are sorted by name: you will therefore select the elements between the start name (included) and the finish name (not included):
Set<Customer> market = new TreeSet<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(gus);
for (Customer customer : market) {
System.out.println(customer.getName());
}
// customer order : ["..."]
for (Customer customer : market.subSet(cat, deb)) {
System.out.println(customer.getName());
}
Elements in alphabetical order of name, between Cathy (included) and Gus (not included) are:
$ Chatty Cathy
$ Debbie Downer
☝️Summary
Java offers an interface Collection for storing, retrieving, updating and removing Java objects. To use the interface, an implementation has to be instantiated. There are several implementations of the Collection interface:
Set(Interface extends Collection) ->HashSet(Implementation, unsorted, unordered)Set(Interface extends Collection) ->LinkedHashSet(Implementation, ordered)Set(Interface extends Collection) ->TreeSet(Implementation, sorted)
In our examples we used Set, which itself is an interface. As implementation for the samples we used HashSet. There are many other implementations of Set available in Java which differ in complexity and runtime behavior and should be evaluated for the specific use case.
The difference between Lists and Sets: Lists are ordered (but not sorted!) Sets do not contain duplicates!
In this quest, you learned how to...
- Create a Set
- Insert, Modify and Remove elements within a Set
- Iterate over elements in a Set
- Use Subsets and methods on the Set interface, like
subSetordescendingSet
To reiterate these tasks, clone the sample application Tariff-Manager, switch to the branch block_2_complete and take a look at dev.wcs.nad.tariffmanager.customer.CustomerCollectionTest and the unit test shouldDemonstrateJavaCollectionsWithSets.
Challenge
This is a Quizz challenge.
References
- Photo by Sebastian Svenson on Unsplash