Implémentation

Quelles fonctions utiliser ?

Pour réaliser cet exercice, vous aurez besoin d'utiliser des listes. Étant donné que notre implémentation des listes n'est pas exhaustive, certaines méthodes sont manquantes, et il est donc préférable dans cet exercice d'utiliser les listes en Python classiques.

Pour calculer le hash, utilisez la fonction hash() fournie par Python. N'oubliez pas l'opérateur % pour borner le résultat.

Question

Implémentez un dictionnaire en Python. Votre classe doit se nommer Dict et doit comporter :

  • Une méthode __init__ qui crée un dictionnaire vide (correspondant à la primitive creer_dictionnaire())

  • Une méthode inserer qui insère un couple (clé, valeur) dans le dictionnaire et lève une exception si la clé est déjà présente.

  • Une méthode modifier qui modifie un couple (clé, valeur) dans le dictionnaire et lève une exception si la clé n'est pas présente.

  • Une méthode supprimer qui supprime un couple (clé, valeur) dans le dictionnaire à partir d'une clé donnée et lève une exception si la clé n'est pas présente.

  • Une méthode rechercher qui renvoie la valeur associée à une clé et lève une exception si la clé n'est pas présente.

Question

Doublez la taille de la table de hachage lorsque le dictionnaire contient plus de trois quart de couples par rapport à la taille de la table de hachage.

Indice

Comptez le nombre d'éléments et vérifiez sa valeur lors d'une insertion.