Java

Java Reskilling Data-Structures 02: Map

Quête 30 sur 43 · 1 image archivée

FrançaisEnglish (original)

Les structures de données Java : Map

Dans les quêtes sur les structures de données Java de base, tu vas apprendre à partir d'exemples tirés de notre application de démonstration Tariff-Manager.

Dans cette quête, une structure de données Java fondamentale, la Map (table de correspondance clé-valeur), sert à associer des clés à des valeurs (c'est-à-dire des paires clé-valeur) dans notre application Tariff-Manager. Il existe différentes implémentations de la Map, que nous allons explorer dans le contexte du domaine Tariff-Manager.

🤓 À la fin de cette quête, tu sauras :

✅Créer une Map pour stocker des paires clé-valeur. ✅Utiliser une Map pour travailler sur les valeurs stockées. ✅Comprendre la différence entre les façons d'utiliser une Map pour travailler sur les valeurs stockées.

👀 Contenu de la quête

Interface : Map
Implémentation : HashMap
Implémentation : LinkedHashMap
Implémentation : TreeMap
Comment choisir ta collection Java

👉Interface : `Map`

Que ce soit avec les listes ou les ensembles (set, collection sans doublons), tu as pu regrouper des éléments, triés ou non. Dans le cas des listes, un index numérique est attribué automatiquement.

Mais que se passe-t-il si tu veux attribuer toi-même un index aux éléments ? Et si cet index n'a pas besoin d'être numérique ?

Par exemple, un index pourrait être un pays, la valeur associée étant sa capitale : pour cela, tu auras besoin des tableaux associatifs (ou dictionnaires). En Java, c'est représenté par l'interface Map !

Un tableau associatif de pays avec leurs capitales respectives ressemble à ceci :

json

{
    "Austria": "Vienna",
    "Belgium": "Brussels",
    "Bulgaria": "Sofia",
    "Croatia": "Zagreb",
    "Denmark": "Copenhague",
    "Spain": "Madrid",
    // ...
}

Dans un environnement d'entreprise, on manipule souvent des structures synthétiques comme des correspondances ID-Client, par exemple :

json

{
    "AJ55Y26": "Average Joe",
    "CC55X16": "Chatty Cathy",
    "DD55Z88": "Debbie Downer",
    "DT66B87": "Doubting Thomas",
    "GG99N88": "Gloomy Gus",
    "GC11O66": "Good-Time Charlie",
    // ...
}

L'interface Map<K,V> est représentée par le type de clé K et le type de valeur V ; dans l'exemple, il s'agit de Map<String, String>.

Une Map peut avoir n'importe quel type d'objet comme clé, ainsi que comme valeur. Ça peut même être une liste, un ensemble, ou encore un autre tableau associatif !

Un tableau associatif se compose de trois zones distinctes :

keySet : l'ensemble de ses clés, deux clés ne peuvent pas être identiques
values : la collection de ses valeurs, il est possible d'avoir des valeurs identiques
entrySet : l'ensemble des paires clé-valeur, aucun doublon possible

Il existe plusieurs implémentations de l'interface Map, notamment :

sans ordre défini, avec HashMap
dans l'ordre d'insertion, avec LinkedHashMap
triée selon la valeur des clés, avec TreeMap

Contrairement aux interfaces List et Set, la Map n'hérite pas de Collection.

Collections and Maps: Interfaces and their Implementations Crédit Alla Gorik

👉Implémentation : `HashMap`

Si l'ordre des clés n'a pas d'importance, il est conseillé d'utiliser l'implémentation HashMap.

Pour créer une nouvelle HashMap vide, tu devras créer une instance de la classe et la stocker dans une référence :

java

Map<Employee, Department> company = new HashMap<>();

Ici, on a la représentation d'une entreprise, avec pour chaque Employee un département associé dans l'entreprise Department.

Les clés formant un ensemble, il n'est pas possible d'avoir le même employé plusieurs fois dans différents départements. En revanche, les départements ont très probablement plusieurs employés, donc les valeurs peuvent être des doublons.

Avant de regarder quelques méthodes, commençons par initialiser quelques instances que nous utiliserons plus tard :

java

Employee bernard = new Employee("Bernard");
Employee laverne = new Employee("Laverne");
Employee hoagie = new Employee("Hoagie");
Employee surfer = new Employee("Jeff Woodie");
Department sales = new Department("Sales");
Department hr = new Department("HR");
Department it = new Department("IT");

Insertion

L'insertion d'une paire clé-valeur se fait avec la méthode put(K key, V value) :

java

Map<Employee, Department> company = new HashMap<>();
company.put(bernard,  sales);
company.put(laverne, sales);
company.put(hoagie, hr);
company.put(surfer, it);

Comme tu peux le voir, il est possible d'attribuer la même valeur à différentes clés.

Suppression

Tu peux supprimer un élément grâce à sa clé. L'élément supprimé sera retourné :

java

Employee removed = company.remove(surfer);
System.out.println(removed.getName()); // Jeff Woodie

Ensemble des clés

Il est possible de récupérer l'ensemble des clés (Set) du tableau associatif avec la méthode keySet() :

java

for (Employee employee : company.keySet()) {  
    System.out.println(employee.getName());  
}

bash

$ Bernard
$ Hoagie
$ Laverne

Comme les clés sont dans un ensemble, l'ordre n'est pas garanti.

Collection de valeurs

Il est possible de récupérer la collection de valeurs (Collection) du tableau associatif avec values() :

java

for (Department department : company.values()) {  
    System.out.println(department.getName());  
}

bash

$ Sales
$ Sales
$ HR
$ IT

Remarque : les valeurs sont triées dans l'ordre d'insertion.

Parcourir l'ensemble des paires clé-valeur

Il est possible de récupérer toutes les paires clé-valeur (Set) du tableau associatif avec entrySet(). Le type de la paire clé-valeur sera Map.Entry<K, V>, avec la clé K et la valeur V.

Il est possible de parcourir cet ensemble et, pour chaque paire, de récupérer la clé avec la méthode getKey() et la valeur avec getValue() :

java

for (Map.Entry<Employee, Department> entry : company.entrySet()) {  
    Employee employee = entry.getKey();  
    Department department = entry.getValue();  
    System.out.println(company.getName() + " works in " + department.getName());  
}

bash

$ Bernard works in Sales
$ Hoagie works in Sales
$ Laverne works in HR
$ Jeff works in IT

Comme les paires clé-valeur sont dans un ensemble, l'ordre n'est pas garanti.

Rechercher une clé et une valeur

Il est possible de savoir si un tableau associatif contient une clé ou une valeur, grâce aux méthodes containsKey(Object o) et containsValue(Object o) :

java

System.out.println(company.containsKey(bernard)); // true 
System.out.println(company.containsValue(orga)); // false

👉Implémentation : LinkedHashMap

Si tu veux un tableau associatif trié selon l'ordre dans lequel les éléments sont insérés, c'est du côté de LinkedHashMap qu'il va falloir regarder !

Ainsi, les éléments seront parcourus dans l'ordre où ils ont été ajoutés :

java

Map<Employee, Department> linkedCompany = new LinkedHashMap<>();  
linkedCompany.put(bernard, sales);  
linkedCompany.put(laverne, sales);  
linkedCompany.put(hoagie, hr);
linkedCompany.put(surfer, it);

for (Employee employee : linkedCompany.keySet()) {  
    Department department = linkedCompany.get(employee);  
    System.out.println(employee.getName() + " works in " + department.getName());  
}

bash

$ Bernard works in Sales 
$ Laverne works in Sales
$ Hoagie works in HR
$ Jeff Woodie works in IT

👉Implémentation : TreeMap

Un tableau associatif TreeMap te permet de trier les éléments selon la valeur des clés.

java

Map<Employee, Department> treeCompany = new TreeMap<>();

Mais avec le code tel quel, tu obtiendras l'erreur suivante à la compilation :

shell

class Employee cannot be cast to class java.lang.Comparable

Les clés doivent donc se voir attribuer un ordre par défaut :

soit en implémentant Comparable au préalable
soit au moment de la création du tableau associatif, en instanciant une classe anonyme à partir de Comparator

Ci-dessous, tu peux voir comment créer une instance de TreeMap avec un Comparator :

java

Comparator<Employee> comparator = new Comparator<>() {  
    @Override  
    public int compare(Employee orig, Employee compare) {  
        return orig.getName().compareTo(compare.getName());  
    }  
};  
Map<Employee, Department> treeCompany = new TreeMap<>(comparator);

treeCompany.put(bernard, sales);  
treeCompany.put(laverne, sales);  
treeCompany.put(hoagie, hr);  
treeCompany.put(surfer, it);

Ainsi, les éléments seront parcourus dans l'ordre alphabétique des clés :

java

for (Employee employee : treeCompany.keySet()) {
    Department department = treeCompany.get(employee);
    System.out.println(employee.getName() + " works in " + department.getName());
}

bash

$ Bernard: Sales
$ Hoagie: HR
$ Jeff Woodie: IT
$ Laverne: Sales

👉Comment choisir ton implémentation de Collection ou de Map

Pour voir en situation toutes les notions abordées dans la quête, récupère le dépôt git fourni en ressource.

Après toutes ces quêtes sur les collections, tu dois commencer à te demander lesquelles choisir et quand !

Another Overview on Collection's and Map's Interfaces and Implementations Crédit Yash-777

Voici un super schéma (à garder sous la main) qui t'aidera dans ces décisions difficiles !

Java Map/Collection Cheat Sheet Crédit Ramesh Fadatare

🔬Exercice

On peut stocker n'importe quel objet comme clé ou comme valeur, et pourquoi pas une List ? En réalité, on peut aussi stocker une liste de valeurs comme valeur dans une Map. Un exemple pour nos Maps serait une association de Department vers Employee. Alors qu'un employé ne peut travailler que dans un seul département, un département peut employer de nombreux employés.

Tu dois créer deux départements : HR et IT. Ces départements sont simplement des Strings dans une structure de données Map<String, List<String>>. Les valeurs sont des Lists de Strings, qui représentent les employés.

Tu dois implémenter cette association :

HR: "Joe, Jack, April"
IT: "Roy, Maurice, Jen"

Étapes

Crée d'abord les listes List<String> avec les différents employés
Crée une nouvelle Map<String, List<String>>
Place l'association clé, valeur dans la Map

hidden

Reveal the Map and List implementations|||java||||||1|||
// Create lists of employees (as strings)
List<String> hr = List.of("Joe", "Jack", "April");
List<String> it = List.of("Roy", "Maurice", "Jen");

// Create Map to associate departement (as string) to employees
Map<String, List<String>> departments = new HashMap<>();
departments.put("HR", hr);
departments.put("IT", it);

☝️Résumé

Dans cette quête, tu as appris à stocker des informations non seulement dans une liste séquentielle, mais aussi sous forme de paires clé-valeur, ce qui te permet de récupérer une valeur directement en fournissant sa clé. Tu as vu comment associer des valeurs comme des capitales à des clés comme des pays, ou des employés comme clés à des départements comme valeurs.

Nous avons utilisé toutes sortes d'implémentations de Map pour réaliser ça en Java, certaines triées, d'autres non. Comme avec les Collections, tu as appris à

Créer une nouvelle Map
Itérer sur une Map, ses clés et ses valeurs
Stocker des éléments dans une Map
Récupérer des éléments ou des entrées (paires clé-valeur) depuis une Map

Pour refaire ces tâches, clone l'application de démonstration Tariff-Manager, bascule sur la branche block_2_complete et jette un œil à dev.wcs.nad.tariffmanager.customer.CustomerCollectionTest ainsi qu'au test unitaire shouldDemonstrateJavaMaps.

Challenge

C'est un challenge de type Quizz.

Références

Photo de Max Langelott sur Unsplash

Java Data-Structures: Map

In the quests about basic Java Data-Structures you will learn with examples from the domain of our sample application Tariff-Manager.

In this quest a fundamental Java Data-Structure (Map) is used for mapping keys to values (ie. keys-value-pairs) in our Tariff-Manager application. There are different implementations of Map, which we will investigate in the context of the Tariff-Manager domain.

🤓 By the end of this quest, you will:

✅Know how to create a Map to store key-value pairs. ✅Know how to use a Map to work on stored values. ✅Understand the difference between How to use a Map to work on stored values.

👀 Content of the quest

Interface: Map
Implementation: HashMap
Implementation: LinkedHashMap
Implementation: TreeMap
How to choose your Java collection

👉Interface: `Map`

Whether with lists or sets, you were able to gather elements, sorted or not. In the case of lists, a numerical index is assigned automatically.

But what if you want to assign an index to the elements yourself? What if this index does not have to be numerical?

For example, an index could be a country, its associated value being its capital: to do this, you will need the associative arrays (or dictionaries). In Java, this is represented by the Map interface!

An associative table of countries with their respective capitals looks like this:

json

{
    "Austria": "Vienna",
    "Belgium": "Brussels",
    "Bulgaria": "Sofia",
    "Croatia": "Zagreb",
    "Denmark": "Copenhague",
    "Spain": "Madrid",
    // ...
}

In an enterprise environment, we often deal with synthetic structures like ID-Customer mappings, eg:

json

{
    "AJ55Y26": "Average Joe",
    "CC55X16": "Chatty Cathy",
    "DD55Z88": "Debbie Downer",
    "DT66B87": "Doubting Thomas",
    "GG99N88": "Gloomy Gus",
    "GC11O66": "Good-Time Charlie",
    // ...
}

The interface Map<K,V> is represented by the key types K and the type of value V in the example, it is about Map<String, String>.

A Map can have any object type as a key, as well as a value. There can even be a list, a set, or even another associative array!

An associative array is composed of three distinct areas:

keySet: all of his keys, two keys cannot be identical
values: the collection of its values, it is possible to have identical values
entrySet: the set of key-value pairs, no duplicates possible

There are several implementations of the interface Map, including:

without a defined sequence, with HashMap
in order of insertion, with LinkedHashMap
sorted by the value of the keys, with TreeMap

In contrast to List and Set interface, the Map does not inherit Collection.

Collections and Maps: Interfaces and their Implementations Credit Alla Gorik

👉Implementation: `HashMap`

If the order of the keys does not matter, it is advisable to use the implementation HashMap.

To create a new HashMap empty, you'll have to create an instance of the class and store it in a reference:

java

Map<Employee, Department> company = new HashMap<>();

Here we have the representation of a company, with for each Employee an associated department in the company Department.

The keys being a set, it is not possible to have the same employee several times in different departments. However, departments most likely have multiple employees, therefore the values can be duplicates.

Before looking at some methods, let's start by initializing some instances that we will use later:

java

Employee bernard = new Employee("Bernard");
Employee laverne = new Employee("Laverne");
Employee hoagie = new Employee("Hoagie");
Employee surfer = new Employee("Jeff Woodie");
Department sales = new Department("Sales");
Department hr = new Department("HR");
Department it = new Department("IT");

Insertion

The insertion of a key-value couple is done by the method put(K key, V value):

java

Map<Employee, Department> company = new HashMap<>();
company.put(bernard,  sales);
company.put(laverne, sales);
company.put(hoagie, hr);
company.put(surfer, it);

As you can see, it is possible to assign the same value to different keys.

Deletion

You can delete an item with its key. The deleted item will be returned:

java

Employee removed = company.remove(surfer);
System.out.println(removed.getName()); // Jeff Woodie

Set of keys

It is possible to retrieve the set of keys (Set) of the associative array with the keySet() method:

java

for (Employee employee : company.keySet()) {  
    System.out.println(employee.getName());  
}

bash

$ Bernard
$ Hoagie
$ Laverne

As the keys are in a set, order is not guaranteed.

Collection of values

It is possible to retrieve the collection of values (Collection) of the associative array with values():

java

for (Department department : company.values()) {  
    System.out.println(department.getName());  
}

bash

$ Sales
$ Sales
$ HR
$ IT

Note: The values are sorted in order of insertion.

Browse through the set of key-value pairs

It is possible to retrieve all key-value pairs (Set) of the associative array with the entrySet(). The type of the key-value pair will be Map.Entry<K, V>, key K and valuable V.

It is possible to browse through this set and, for each couple, to retrieve the key with the method getKey() and the value with the getValue():

java

for (Map.Entry<Employee, Department> entry : company.entrySet()) {  
    Employee employee = entry.getKey();  
    Department department = entry.getValue();  
    System.out.println(company.getName() + " works in " + department.getName());  
}

bash

$ Bernard works in Sales
$ Hoagie works in Sales
$ Laverne works in HR
$ Jeff works in IT

As the key-value pairs are in a set, the order is not guaranteed.

Search for a key and a value

It is possible to find out whether an associative array contains a key or a value, using the methods containsKey(Object o) and containsValue(Object o):

java

System.out.println(company.containsKey(bernard)); // true 
System.out.println(company.containsValue(orga)); // false

👉Implementation: LinkedHashMap

If you want to have an associative array sorted by the order in which the elements are inserted, it is on the side of LinkedHashMap that you're gonna have to watch!

Thus, the elements will be browsed in the order in which they were added:

java

Map<Employee, Department> linkedCompany = new LinkedHashMap<>();  
linkedCompany.put(bernard, sales);  
linkedCompany.put(laverne, sales);  
linkedCompany.put(hoagie, hr);
linkedCompany.put(surfer, it);

for (Employee employee : linkedCompany.keySet()) {  
    Department department = linkedCompany.get(employee);  
    System.out.println(employee.getName() + " works in " + department.getName());  
}

bash

$ Bernard works in Sales 
$ Laverne works in Sales
$ Hoagie works in HR
$ Jeff Woodie works in IT

👉Implementation: TreeMap

An associative array TreeMap allows you to sort the elements by key value.

java

Map<Employee, Department> treeCompany = new TreeMap<>();

But with the code as is, you'll get the following error at compile time:

shell

class Employee cannot be cast to class java.lang.Comparable

The keys must therefore be assigned a default order:

either by implementing Comparable beforehand
either at the time of the creation of the associative array, by instantiating an anonymous class from Comparator

Below, you can see how to create an instance of TreeMap with a Comparator:

java

Comparator<Employee> comparator = new Comparator<>() {  
    @Override  
    public int compare(Employee orig, Employee compare) {  
        return orig.getName().compareTo(compare.getName());  
    }  
};  
Map<Employee, Department> treeCompany = new TreeMap<>(comparator);

treeCompany.put(bernard, sales);  
treeCompany.put(laverne, sales);  
treeCompany.put(hoagie, hr);  
treeCompany.put(surfer, it);

So, elements will be browsed in alphabetical order of the keys:

java

for (Employee employee : treeCompany.keySet()) {
    Department department = treeCompany.get(employee);
    System.out.println(employee.getName() + " works in " + department.getName());
}

bash

$ Bernard: Sales
$ Hoagie: HR
$ Jeff Woodie: IT
$ Laverne: Sales

👉How to choose your Collection or Map implementation

In order to see in situation all the notions approached by the quest, retrieve the git repository given as a resource.

After all those collection quests, you have to start asking yourself which ones to choose and when!

Another Overview on Collection's and Map's Interfaces and Implementations Credit Yash-777

Here's a great diagram (to keep on hand) that will help you with those tough decisions!

Java Map/Collection Cheat Sheet Credit Ramesh Fadatare

🔬Exercise

We can store any object as key or as value, how about a List? Actually we can store a list of values as a value in a Map as well. An example for our Maps would be an association of Department to Employee. While an employee can only work in one department, a department can employ many employees.

You should create two departments: HR and IT. These departments are just Strings in a Map<String, List<String>> datastructure. The values are Lists of Strings, which represent the employees.

You should implement this association:

HR: "Joe, Jack, April"
IT: "Roy, Maurice, Jen"

Steps

First create the List<String> lists with the different employees
Create a new Map<String, List<String>>
Put the association as key, value into the Map

hidden

Reveal the Map and List implementations|||java||||||1|||
// Create lists of employees (as strings)
List<String> hr = List.of("Joe", "Jack", "April");
List<String> it = List.of("Roy", "Maurice", "Jen");

// Create Map to associate departement (as string) to employees
Map<String, List<String>> departments = new HashMap<>();
departments.put("HR", hr);
departments.put("IT", it);

☝️Summary

In this Quest, you learned how to store information not only in a sequential list, but in key-value pairs, which allows you to retrieve a value directly by providing its key. You saw how to associate values like capitals with keys like countries or employees as keys to departments as values.

We used all kind of Map implementations to realize this in Java, some sorted, some not. Like with Collections, you learned how to

Create a new Map
Iterator over a Map, their keys and values
Store elements into a Map
Retrieve elements or entries (key-value pairs) from a Map

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 shouldDemonstrateJavaMaps.

Challenge

This is a Quizz challenge.

References

Photo by Max Langelott on Unsplash

Les structures de données Java : Map

🤓 À la fin de cette quête, tu sauras :

👀 Contenu de la quête

👉Interface : Map

👉Implémentation : HashMap

Insertion

Suppression

Ensemble des clés

Collection de valeurs

Parcourir l'ensemble des paires clé-valeur

Rechercher une clé et une valeur

👉Implémentation : LinkedHashMap

👉Implémentation : TreeMap

👉Comment choisir ton implémentation de Collection ou de Map

🔬Exercice

Étapes

☝️Résumé

Challenge

Références

Java Data-Structures: Map

🤓 By the end of this quest, you will:

👀 Content of the quest

👉Interface: Map

👉Implementation: HashMap

Insertion

Deletion

Set of keys

Collection of values

Browse through the set of key-value pairs

Search for a key and a value

👉Implementation: LinkedHashMap

👉Implementation: TreeMap

👉How to choose your Collection or Map implementation

🔬Exercise

Steps

☝️Summary

Challenge

References

👉Interface : `Map`

👉Implémentation : `HashMap`

👉Interface: `Map`

👉Implementation: `HashMap`