Adressage ouvert à la main

Adressage ouvert à la main.

Une table de hachage de taille $m=7$ (cases numérotées de $0$ à $6$) range des clés entières avec la fonction $h(k)=k\mathrm{mod}7$ et résout les collisions par sondage linéaire : si la case $i$ est occupée, on essaie $i+1$, $i+2$, … (modulo $7$).

• Insérer successivement les clés $10$, $24$, $17$, $3$, $31$, $12$. Donner l'état final de la table et, pour chaque clé, le nombre de cases examinées.
• Combien de cases faut-il examiner pour conclure que la clé $38$ est absente ?
• Calculer le facteur de charge et commenter.