Les tables de hachage sont l'une des structures de données les plus utiles. Leur rapidité à insérer, rechercher, supprimer et leur extensibilité rendent leur utilisation pertinante pour résoudre un grand nombre de problèmes informatiques.
Dans ce tutoriel, nous implémenterons une table de hachage à adressage ouvert utilisant une méthode de sondage de type double hachage. Le language utilisé est le language C.
En suivant ce tutoriel vous pourrez :
- Comprendre le fonctionnement interne d'une structure de données
- Savoir quand utiliser (ou non) une table de hachage et pourquoi elle peuvent ne pas etre efficaces.
- Manipuler du code C
Le language C est un bon language pour cet exercice car :
- Il n'inclut pas d'implémentation de table de hachage.
- C'est un language bas niveau. On se rapproche donc du fonctionnement de la machine pour l'implémentation.
Ce tutoriel part du postulat que vous avez une connaissance de la programmation et de la syntaxe du C. Le code est relativement simple et la plupart des problèmes peuvent etre résolus avec une recherche Internet. Si vous rencontrez d'autres problèmes, ouvrez un ticket (issue) sur GitHub.
L'implémentation complète fait autour de 200 lignes de code et suivre le tutoriel vous prendra une à deux heures.
- Introduction
- Structure d'une table de hachage
- Fonctions de hachage
- Gestion des collisions
- Méthodes de la table de Hachage
- Redimensionnement
- Annexe : Gestion de collisions alternative
Ce tutoriel a été écrit par James Routley, qui blog ici : routley.io.
Traduit par Sylvestre Antoine. Corrigé par Agathe Begault.