Problème — Une table de hachage qui s'agrandit

Problème — Une table de hachage qui s'agrandit.

On implémente une table de hachage par chaînage dans une classe TableHachage. Sa taille initiale est $m=4$. Après chaque insertion d'une clé nouvelle, si le facteur de charge $n/m$ dépasse strictement $0,75$, la table est rehachée : on crée une table deux fois plus grande et on y réinsère tous les couples.

• Écrire les méthodes inserer(cle, valeur), rechercher(cle) (qui lève une KeyError si la clé est absente) et la méthode interne de rehachage.
• On insère les clés entières $0,1,\dots ,9$. Quelle est la taille finale de la table, et combien de rehachages ont eu lieu ?
• Pourquoi faut-il recalculer l'indice de chaque couple lors du rehachage, au lieu de recopier les cases telles quelles ?