NSI (première) · Chapitre 5 · Exercice supplémentaire
Écrire à la main une table de hachage à seaux
Les dictionnaires · Sous le capot : le hachage · niveau 3 (difficile)
Énoncé
Écrire à la main une table de hachage à seaux : un tableau de listes, où la clé désigne le seau par hash(cle) % nb_seaux. Y ranger clés dans seaux et mesurer la longueur du plus long. Recommencer avec entiers dans seaux.
Pour démarrer : comment l'IA t'aide
Élève
Je ne vois pas trop par où commencer. On me parle de seaux et de hash(cle) % nb_seaux, mais je ne sais pas ce que je dois construire concrètement.
IA
Commence par relire l'énoncé : il décrit une structure précise. Qu'est-ce qu'un seau, d'après la phrase « un tableau de listes » ? Et combien de seaux le premier essai demande-t-il ?
Élève
Un seau, ce serait une liste, et le tableau contient plusieurs listes. Pour le premier essai, il y a 8 seaux. Mais je ne sais pas quoi mettre dans chaque liste.
IA
Tu as le squelette : un tableau de 8 listes. Reste à décider ce qu'on range dans une liste quand on ajoute une clé. Que doit-on pouvoir retrouver à partir d'une clé, et que calcule hash(cle) % nb_seaux ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. Le corrigé de cet exercice n'est pas publié : à toi de continuer.
Continue cet exercice avec l'IA
Reprends l'exercice là où le dialogue s'arrête.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.