Introduction
Les dictionnaires sont une structure de données qui permet de stocker et de récupérer des informations de manière efficace. Ils sont implémentés en utilisant une structure appelée « table de hachage », qui est ce qui permet aux dictionnaires d’avoir une complexité temporelle moyenne de O(1) pour les opérations d’insertion, de recherche et de suppression.
Un dictionnaire est une collection non ordonnée de paires clé-valeur. Chaque clé dans le dictionnaire est unique et est associée à une valeur spécifique. Les dictionnaires sont mutables, ce qui signifie que nous pouvons ajouter, supprimer et modifier les éléments d’un dictionnaire après sa création.
Nous noterons Dict[K,V] la structure de données du dictionnaire nommée Dict et dont les clés sont de type K et les valeurs sont de type V.
Une compréhension de l’implémentation des dictionnaires peut nous aider à écrire un code plus performant. Par exemple, si nous savons que les opérations d’insertion, de recherche et de suppression ont une complexité temporelle moyenne de O(1) dans un dictionnaire, nous pouvons choisir d’utiliser un dictionnaire au lieu d’une liste lorsque nous avons besoin d’effectuer un grand nombre de ces opérations.
Nous avons dans le dictionnaire plusieurs primitives importantes qui vont nous permettre de créer et manipuler les valeurs de notre dictionnaire :
creer_dictionnaire() -> Dict[K,V]: crée un dictionnaire vide et renvoie ce nouveau dictionnaire.inserer(Dict[K,V], K, V) -> None: associe une nouvelle valeur à une nouvelle clé.modifier(Dict[K,V], K, V) -> None: associe une nouvelle valeur à une ancienne clé.supprimer(Dict[K,V], K) -> None: supprime la valeur associée à une clé, et la clé.rechercher(Dict[K,V], K) -> V: renvoie la valeur associée à une clé.