Voir le flux RSS

ericb2

[Actualité] Implémentation naïve d'une table de hachage en C

Note : 2 votes pour une moyenne de 4,50.
par , 24/07/2020 à 19h36 (990 Affichages)
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).



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.
Nom : hash01.png
Affichages : 2503
Taille : 67,1 Ko

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

Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Viadeo Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Twitter Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Google Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Facebook Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Digg Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Delicious Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog MySpace Envoyer le billet « Implémentation naïve d'une table de hachage en C » dans le blog Yahoo

Mis à jour 24/07/2020 à 22h07 par ericb2 (suppression du doublon)

Catégories
Programmation , C

Commentaires

  1. Avatar de neuneutrinos
    • |
    • permalink
    Félicitation de proposer du contenu, moi je n'arrive pas à aller jusqu'au bout

    Je vais revenir sur le code , et je te propose de mettre ton code dans un compilateur en ligne (ideone, repl.it par exemple)
    Comme ça il sera plus simple de tester le code.

    Choisis entre l'anglais et le français pour les commentaires.

    scanf (fscanf , sscanf , etc ...) permettent la lecture formatée.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    float x;
    char txt[] = "4e-4";
    sscanf(txt,"%f",&x);
    printf("%f\n",x);//affichera 0.000400
    Donc pas besoin de le recoder (sauf format particulier)
    Il faudra simplement faire attention au retour et à l'encadrement de tes valeurs

    Ce qui simplifiera grandement ton saisie.c

    utils.h

    Voici ta fonction strlcpy
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    /*
     * Copy src to string dst of size siz.  At most siz-1 characters
     * will be copied.  Always NUL terminates (unless siz == 0).
     * Returns strlen(src); if retval >= siz, truncation occurred.
     */
    size_t strlcpy(char *dst, const char *src, size_t siz)
    {
            char *d = dst;
            const char *s = src;
            size_t n = siz;
    
            /* Copy as many bytes as will fit */
            if (n != 0 && --n != 0) {
                    do {
                            if ((*d++ = *s++) == 0)
                                    break;
                    } while (--n != 0);
            }
    
            /* Not enough room in dst, add NUL and traverse rest of src */
            if (n == 0) {
                    if (siz != 0)
                            *d = '\0';                /* NUL-terminate dst */
                    while (*s++)
                            ;
            }
    
            return(s - src - 1);        /* count does not include NUL */
    }
    Je te propose une forme plus épurée.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    size_t strlcpy(char *dst, const char *src, size_t siz)
    {
      size_t destLen=siz;
      char *buf=dst;
      if(siz!=0)//siz==0 ? on ne fait rien
      {
        while(*src!='\0' && --siz > 0)//for(;*src!='\0' && --siz > 0;dst++,src++) mais peut être moins lisible
        {
          *dst=*src;
          dst++;
          src++;
        }
        *dst = '\0';
        destLen=destLen-siz;
        //-1 à cause de la troncature.
        if(siz==0)destLen--;
        
      }
      return destLen;
    }
    Si tu mets tous tes MENU_ENTRY_X dans une enum énuméré par défaut , alors ce serait plus simple à utiliser
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    enum MenuEntry
    {
     MENU_ENTRY_1,
     MENU_ENTRY_2,
     //...
     MENU_ENTRY_NB
    };
    //MENU_ENTRY_NB correspondra au nombre de MENU_ENTRY , si j'en ajoute , ça se changera tout seul !
    L'utilisation d'enum permet de faire plus simple.
    Mais il y a encore mieux si on prévoit des ajouts dans le menu. On pourrait prévoir un tableau de "MenuItem" par exemple (et pointeurs de fonction pour éviter de hardcoder un gros switch par exemple).

    'HASH' tout en majuscule , est curieuse par rapport au reste de ton code.
    'Hash' ou bien 'hash' serait mieux.

    Ensuite, ta hashTable ... est une liste , pourquoi ne pas la renommer hashList ?

    Le "singleton" est assez étrange, ne serait-il pas intéressant de permettre l'utilisation de plusieurs tables de hashage ?
    Simplement InitHashTable(Hash* hashTable); par exemple ?
    d'ailleurs certaines fonctions n'utilisent pas ce fameux "singleton" comme push , pop , etc ...

    Question idiote ... il n'y a pas de fonction de hashage ?

    Dans le cas où tu n'as pas de collision, une table de hashage doit te retourner/ajouter un élément en O(1) voir O(log(n)).
    Là on est en O(n)...

    On ne profite pas des avantages que l'on attend d'une table de hashage (même naïve).
    On se retrouve avec une liste simplement chainée avec un identifiant pour chaque élément...

    https://jipe.developpez.com/articles.../?page=theorie

    Si tu souhaites un peu d'aide , ce serait avec plaisir
  2. Avatar de ericb2
    • |
    • permalink
    Bonjour,

    Citation Envoyé par neuneutrinos
    Félicitation de proposer du contenu, moi je n'arrive pas à aller jusqu'au bout


    Tout d'abord, merci pour tes commentaires. En fait, c'est difficile de définir le bout d"un article. j'essaye de mettre à jour progressivement, et d'améliorer.





    Je vais revenir sur le code , et je te propose de mettre ton code dans un compilateur en ligne (ideone, repl.it par exemple)


    J'avoue ne pas avoir pensé à ça. ça marche même avec un Makefile ?






    Comme ça il sera plus simple de tester le code.

    Choisis entre l'anglais et le français pour les commentaires.


    Oui tu as raison : en fait j'ai assemblé du code que j'ai écrit pour d'autres projets, avec d'abord l'idée de réutiliser, et d'améliorer prochainement.






    scanf (fscanf , sscanf , etc ...) permettent la lecture formatée.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    float x;
    char txt[] = "4e-4";
    sscanf(txt,"%f",&x);
    printf("%f\n",x);//affichera 0.000400
    Donc pas besoin de le recoder (sauf format particulier)
    Il faudra simplement faire attention au retour et à l'encadrement de tes valeurs

    Ce qui simplifiera grandement ton saisie.c



    Je ne sais plus pourquoi je l'avais utilisé, mais il y avait une (plusieurs même) bonne raison (s). Il me semble que j'avais séparé en 2 : pour la saisie d'une chaîne de caractères => fgets() et pour la saisie d'un nombre (à vérifier ensuite) : sscanf

    Parce que les risques de dépassement sont réels avec sscanf().







    utils.h

    Voici ta fonction strlcpy
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    /*
     * Copy src to string dst of size siz.  At most siz-1 characters
     * will be copied.  Always NUL terminates (unless siz == 0).
     * Returns strlen(src); if retval >= siz, truncation occurred.
     */
    size_t strlcpy(char *dst, const char *src, size_t siz)
    {
            char *d = dst;
            const char *s = src;
            size_t n = siz;
    
            /* Copy as many bytes as will fit */
            if (n != 0 && --n != 0) {
                    do {
                            if ((*d++ = *s++) == 0)
                                    break;
                    } while (--n != 0);
            }
    
            /* Not enough room in dst, add NUL and traverse rest of src */
            if (n == 0) {
                    if (siz != 0)
                            *d = '\0';                /* NUL-terminate dst */
                    while (*s++)
                            ;
            }
    
            return(s - src - 1);        /* count does not include NUL */
    }
    Je te propose une forme plus épurée.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    size_t strlcpy(char *dst, const char *src, size_t siz)
    {
      size_t destLen=siz;
      char *buf=dst;
      if(siz!=0)//siz==0 ? on ne fait rien
      {
        while(*src!='\0' && --siz > 0)//for(;*src!='\0' && --siz > 0;dst++,src++) mais peut être moins lisible
        {
          *dst=*src;
          dst++;
          src++;
        }
        *dst = '\0';
        destLen=destLen-siz;
        //-1 à cause de la troncature.
        if(siz==0)destLen--;
        
      }
      return destLen;
    }


    Comme indiqué dans les sources, c'est du code sous licence BSD et je l'ai repris tel quel, mais si tu as mieux, ça ne me dérange pas d'intégrer ta contribution :-)





    Si tu mets tous tes MENU_ENTRY_X dans une enum énuméré par défaut , alors ce serait plus simple à utiliser
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    enum MenuEntry
    {
     MENU_ENTRY_1,
     MENU_ENTRY_2,
     //...
     MENU_ENTRY_NB
    };
    //MENU_ENTRY_NB correspondra au nombre de MENU_ENTRY , si j'en ajoute , ça se changera tout seul !

    Oui, oui, c'est juste que je n'ai ai pas pensé sur le moment. J'avais aussi une autre solution, comme celle que j'ai utilisée dans OSS San Baguette (un projet d'élève, que j'ai pas mal suivi)





    L'utilisation d'enum permet de faire plus simple.
    Mais il y a encore mieux si on prévoit des ajouts dans le menu. On pourrait prévoir un tableau de "MenuItem" par exemple (et pointeurs de fonction pour éviter de hardcoder un gros switch par exemple).

    'HASH' tout en majuscule , est curieuse par rapport au reste de ton code.
    'Hash' ou bien 'hash' serait mieux.


    Oui, je vais changer, ce n'est pas très propre. Merci pour la remarque.






    Ensuite, ta hashTable ... est une liste , pourquoi ne pas la renommer hashList ?

    Le "singleton" est assez étrange, ne serait-il pas intéressant de permettre l'utilisation de plusieurs tables de hashage ?


    C'est parce que ce n'est qu'un exemple. En réalité, je ne l'aurais pas codé en C si j'en avais eu besoin, et j'aurais créé une vraie classe C++, et j'aurais créé une instance par table.





    Simplement InitHashTable(Hash* hashTable); par exemple ?
    d'ailleurs certaines fonctions n'utilisent pas ce fameux "singleton" comme push , pop , etc ...

    Question idiote ... il n'y a pas de fonction de hashage ?


    Pour parler de fonction de hachage, il aurait fallu que je définisse une relation entre la clé et la valeur. Ce n'était pas le but ici : la clé et la valeur sont simplement indépendantes. C'est plutôt un dictionnaire que j'ai présenté, dans l'esprit d'un TP de 2h pour être précis.






    Dans le cas où tu n'as pas de collision, une table de hashage doit te retourner/ajouter un élément en O(1) voir O(log(n)).
    Là on est en O(n)...


    Quand la clé est connue, c'est du 0(1)

    Si on cherche une clé, c'est bien du O(n) oui. Mais c'est une table basique, dont le but est de comprendre le principe, sans prétention.






    On ne profite pas des avantages que l'on attend d'une table de hashage (même naïve).
    On se retrouve avec une liste simplement chainée avec un identifiant pour chaque élément...


    La table, on la crée à la main (de façon dynamique). Et c'est même plutôt un dictionnaire.

    Le but, plutôt pédagogique, c'était de vérifier que les fonctions marchent bien et que le cahier des charges était respecté.






    https://jipe.developpez.com/articles.../?page=theorie

    Si tu souhaites un peu d'aide , ce serait avec plaisir

    Avec plaisir : j'apprendrai plein de choses, et le code ne s'en portera que mieux.

    Que préfères-tu : forker le dépôt complet et faire une PR, ou tu crées une issue, et tu attaches un diff (en précisant la licence), et je le commite en ton nom ?