Implémentation naïve d'une table de hachage en C,

Un billet de blog d'ericb2

Introduction

Cet article présente brièvement une implémentation "naïve" d'une table de hachage en C, à base de liste chaînée. L'idée, c'est simplement de valider le modèle et de jouer avec, car le code n'a rien de professionnel. Il pourrait (devrait) facilement être porté en C++.

J'ajoute qu'il doit même exister des bibliothèques comme Boost qui proposent des exemples prêts à l'emploi, et certainement plus robustes. En fait, je n'en sais rien, mais je ne serais pas surpris.

Donc c'est en C, c'est tout :-)

Comme le but c'est de tester, tout est disponible en ligne. Si vous souhaitez faire des essais, notez que ça ne fonctionne que sous Linux, mais ça doit se porter facilement sous Mac OS X (je ne sais pas si popen existe, et strlcpy est protégé par des macros, car Apple propose sa propre implémentation).

=> lien pour télécharger le code source

Commentaires sur le code :

• j'ai beaucoup (trop) documenté le code. Je vais bientôt les enlever (git diff version1...version2 > documentation.diff permettra de les retrouver facilement)
• les saisies, que ce soit d'une chaîne de caractères, d'un entier court (signé), ou encore d'un nombre réel (y compris en notation scientifique) sont effectuées par l'API saisie, que j'ai écrite pour éviter à mes élèves de perdre du temps avec les entrées/sorties en C, qui sont une véritable horreur (cette API m'a demandé beaucoup de temps, et j'ai probablement encore quelques trous dans la raquette). Cette abstraction étant réalisée c'est beaucoup plus simple pour eux.
• la compilation est réalisée par make (+ un Makefile, qui peut aussi être utilisé avec LateX) [étude d'un Makefile]
• les sources sont découpées en plusieurs fichiers .c [notion de compilation séparée, cf Méthodologie de programmation en C, de JP Braquelaire]
• les flags de compilation permettent de traquer un maximum de warnings possibles, afin d'être sûr que le code est suffisamment propre. Il suffit de commenter une ligne dans le Makefile pour simplifier
  

Les dépendances sont les suivantes :

• git si vous souhaitez utiliser le dépôt complet
• gcc ( sudo apt-get install build-essential)
• make pour la création du binaire
• gdb (pour déboguer le binaire qui inclut les symboles ad hoc)
  

À venir (un jour) : amélioration de la documentation, avec des compléments sur la complexité et les propriétés des tables de hachages

Si vous avez des questions, n'hésitez pas. En particulier, j'ai commencé à écrire une documentation type approche documentaire autour de ce sujet, mais toute aide est bienvenue !!

Merci d'avance pour vos retours, et vos suggestions d'améliorations, et n'hésitez pas à me contacter si vous avez des questions.

Quelques définitions

En informatique, une table de hachage est une structure de données qui permet l'association de paires clé/valeur. Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par des entiers).

La clé étant une chaîne de caractère, la valeur un nombre, ou une suite de nombres comme un numéro de téléphone ou n'importe quelle donnée associée à une "valeur". Il est aussi possible, certaines fois, d'avoir plusieurs valeurs pour la même clé, par exemple dans le but d'éviter des collisions.


Principe de fonctionnement : on accède à chaque élément de la table via sa clé. Les paires sont stockées dans les alvéoles du tableau. En fonction de la méthode utilisée, le remplissage peut poser problème ou pas. Selon la nature de la table de hachage, le nombre d'alvéoles peut être fixe ou variable dynamiquement (comme ici).

Les opérations que l'on peut réaliser avec cette table de hachage sont :

• créer la table (et l'initialiser) ;
• ajouter une paire clé/valeur ;
• supprimer une paire en donnant la clé (la valeur sera supprimée en même temps que la clé) ;
• chercher si une clé existe dans la table ;
• retrouver la valeur associée à une clé ;
• modifier la valeur associée à une clé.
  

Dans notre cas, la taille de la table est a priori indéfinie (mais de valeur finie), et dépend des ressources mémoire dont on dispose.

Il n'y a pas de relation d'ordre dans une table de hachage, et la position des paires clé-valeur est pseudo-aléatoire dans cette table.

Illustration : imaginons que l'on crée la clé "AAA",associée à la valeur "1984". Ensuite, on ajoute deux clés "Odyssée de l'espace" (associée à "2001") et enfin la clé "Marignan" associée à "1515". On peut évidemment supprimer la clé AAA (la valeur sera perdue avec la suppression de cette clé) et recréer AAA. Mais cette fois, l'alvéole qui contient AAA sera en fin de liste, et aura changé de place. L'ordre n'est donc pas prévisible, ni immuable.

Cette structure n'est donc pas adaptée au feuilletage (browsing) de données voisines. Des types de structures de données comme les arbres équilibrés [4], généralement plus lents (en O(log n) [3]) et un peu plus complexes à implémenter, maintiennent une structure ordonnée.

On associe la notion de dictionnaire (très utilisé avec Mac OSX) à la notion de table de hachage.

Exemple de table de hachage

Pour illustrer la notion de table de hachage, on utilise l'exemple donné sur wikipedia [1], cf figure ci-dessous.


Les données saisies par l'utilisateur sont en bleu et en vert. L'indice associé à l'index est attribué de façon interne par le logiciel, et représente la position dans la liste chaînée qui n'est pas ordonnée. Dans le code l'indice sera appelé refcount (très utile en C++ aussi) dans le code écrit en langage C.

Remarque : ne pas confondre table de hachage avec fonction de hachage : On nomme fonction de hachage, de l'anglais hash function (hash*: pagaille, désordre, recouper et mélanger) par analogie avec la cuisine, une fonction particulière qui, à partir d'une donnée fournie en entrée, calcule une empreinte numérique servant à identifier rapidement la donnée initiale, au même titre qu'une signature pour identifier une personne. Les fonctions de hachage sont utilisées en informatique et en cryptographie notamment pour reconnaître rapidement des fichiers ou des mots de passe.

Les deux notions sont toutefois proches, puisqu'on réalise une opération au sens mathématique sur la clé, pour obtenir la valeur. Quand la valeur est obtenue (grâce à une fonction qui prend pour argument la clé), on parle de fonction de hachage.

Exemple : calcul d'une somme de contrôle md5 d'une chaîne de caractère (qui peut être longue)

Pour en savoir plus

Sources type URL :

[1] https://fr.wikipedia.org/wiki/Table_de_hachage
[2] https://fr.wikipedia.org/wiki/Fonction_de_hachage

[3] https://fr.wikipedia.org/wiki/Comparaison_asymptotique
[4] https://fr.wikipedia.org/wiki/Arbre_équilibré

La page du département informatique de l'ENS Cachan (bouh, Paris Saclay maintenant) :
http://www.dptinfo.ens-cachan.fr/Agregation/

Document de Mme Cristina Sirangelo :
http://www.dptinfo.ens-cachan.fr/Agr...es-hachage.pdf

http://www.lsv.fr/~jacomme/agreg/index.html : fiches d'algorithmique

Les dictionnaires (Université de Montréal) :
https://www.iro.umontreal.ca/~hamels...ionnaires4.pdf