Structures de données efficaces : Sets & Maps

Optimiser son code en Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Appliquer la complexité espace/temps

Nous connaissons désormais les complexités en temps et en espace !

Comment appliquer cela pour écrire un code plus efficace ?

En choisissant la bonne structure de données !

Optimiser son code en Java

Un système de gestion des utilisateurs

  • Nous construisons un système de gestion des utilisateurs

  • Pour un nom d'utilisateur donné, nous devons vérifier si l'utilisateur existe

  • Avec une liste : complexité $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}
Optimiser son code en Java

Sets

  • Une collection d'éléments uniques avec une recherche rapide
  • $O(1)$ en moyenne pour ajouter, supprimer et vérifier l'existence d'un élément

Solution améliorée pour la gestion des utilisateurs :

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}
Optimiser son code en Java

Maps

  • Comme un dictionnaire : mot (clé) -> définition (valeur)
  • HashMap : $O(1)$ en moyenne pour les opérations
public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}
Optimiser son code en Java

Méthode hashCode

  • Ce qui les rend rapides -> hashCode()
  • Dans notre exemple avec ArrayList, nous ne connaissions pas l'index du nom d'utilisateur à trouver
  • Avec la méthode hashcode(), on convertit un objet en un index à rechercher
  • Par exemple : pavlos.2020 -> 35189

« pavlos.2020 » traité par hashcode, donnant 35189

Optimiser son code en Java

Indexer les éléments

  • HashMap et HashSet reposent sur un tableau sous-jacent
  • Lorsqu'on ajoute un élément :
    • Java appelle hashCode() sur l'élément pour obtenir un entier
    • Puis applique le modulo pour obtenir le numéro de « bucket »

Exemple :

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implémenté par Java
1406313774 % 16 = 14 <- c'est notre bucket !
Optimiser son code en Java

Collisions

  • Quand plusieurs éléments aboutissent dans le même bucket
    • On parle de collision
  • LinkedList pour le bucket
  • D'où $O(1)$ en moyenne
Optimiser son code en Java

À retenir

Choisir une structure de données, c'est comme choisir le bon outil : un marteau (ArrayList) est parfait pour les clous, mais mauvais pour les vis (où un Set sera plus adapté).

Une boîte à outils ouverte avec un marteau, un tournevis, une clé et une pince côte à côte

Optimiser son code en Java

Passons à la pratique !

Optimiser son code en Java

Preparing Video For Download...