Structures de données efficaces : ensembles et tables d'association

Optimiser le code en Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Appliquer la complexité espace/temps

Vous connaissez maintenant les complexités en espace et en temps !

Comment appliquer cela pour écrire un code plus efficace ?

En choisissant la bonne structure de données !

Optimiser le code en Java

Un système de gestion des utilisateurs

  • Nous créons un système de gestion des utilisateurs

  • Pour un nom d'utilisateur donné, vérifier si un 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 le code en Java

Ensembles

  • Une collection d'éléments uniques avec des recherches rapides
  • Complexité moyenne $O(1)$ 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 le code en Java

Tables d'association

  • Comme un dictionnaire : mot (clé) -> définition (valeur)
  • HashMap : complexité moyenne $O(1)$ 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 le code en Java

Méthode hashCode

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

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

Optimiser le code en Java

Indexer les éléments

  • HashMap et HashSet reposent sur un tableau interne
  • 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 panier (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 panier !
Optimiser le code en Java

Collisions

  • Quand plusieurs éléments aboutissent dans le même panier
    • On parle de collision
  • LinkedList pour le panier
  • D'où le $O(1)$ en moyenne
Optimiser le 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 pas pour les vis (où un Set conviendrait mieux).

Outils

Optimiser le code en Java

Passons à la pratique !

Optimiser le code en Java

Preparing Video For Download...