🕒 : 3 h maximum

Prérequis:

• Cours sur les chaines de caractères (string)
• Les TP de C précédents
• utilisation de gdb permet de comprendre l’intérieur du code !
• cours sur hash en C

But:

• Compréhension d’un hash
• Manipulation de chaîne sans utiliser la notion de tableau avec des []
• Collision sur les hashs, utilisation d’un nombre premier élevé !

Code de hash simple

le hash permet de sécuriser un mot de passe par exemple ! dans la conclusion vous expliquerez cela à la fin du TP

Compiler ce code et avec le GDB comprendre l’algorithme de ce HASH

#include<stdlib.h>
#include<stdio.h>

/* Fonction du hash_simple       */
/* Entrée: chaine de caractères  */
/* Sortie: un long int (64 bits) */

unsigned long int hash_simple(const char *str)
{
    unsigned long int hash = 0;
    const unsigned long int prime = 1; /* 31 ou un nombre premier plus élevé est préférable */
    const char *p;
    
    if (str == NULL)   /* cas ou pas de chaine */
    {
        return 0;
    }
    
    p = str;
    while (*p != '\0')
    {
        hash = (hash * prime) + (unsigned long int)(*p);
        p++;
    }
    return hash;
}
/**************************************************************************************************/
int main (int argc, char **argv)
{
if (argc!=2) 
	{
		fprintf(stderr, "Aucune chaine fournie.\n");
		fprintf(stderr, "syntaxe: ./hash_simple \"chaine de caractère\"\n");
		return EXIT_FAILURE;
	}
/* ici argv[1] contient une chaine a hacher */
printf ("Le hash simple de %s en décimal   est %ld \n",argv[1],hash_simple(argv[1])); 
printf ("Le hash simple de %s en héxadémal est %lx \n",argv[1],hash_simple(argv[1])); 

return EXIT_SUCCESS;
}

bruno@elliott:~/Works/langage_C/hash$/hash "Bonjour"
Le hash simple de Bonjour en décimal   est 735 
Le hash simple de Bonjour en héxadémal est 2df 

On va étudier la fonction main(int argc, char **argv)

Si argc est diffèrent de 2

expliquer pourquoi argc peut être diffèrent de 2 et comment ?

fprintf et stderr

bruno@elliott:/dev$ ls /dev/std*
stderr  stdin  stdout
bruno@elliott:/dev$ ls -l /dev/std*
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stderr -> /proc/self/fd/2
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stdin -> /proc/self/fd/0
lrwxrwxrwx 1 root root 15  9 févr. 10:39 stdout -> /proc/self/fd/1
bruno@elliott:/dev$ 

A l’aide du man fprintf et du man stderr déterminer ce que représente stderr

bruno@elliott:~$ echo "Erreur !" > /dev/stderr 
Erreur !
bruno@elliott:~$ 

l’idée de diriger les erreurs sur stderr est d’éviter de mélanger les stdout et les erreurs

                  +----------------+
                  |    Programme   |
                  |                |
     stdin  <-----| 0              |-----> 1  stdout
   (entrée)       |                |     (sortie)
                  |                |-----> 2  stderr
                  +----------------+     (erreurs)

La fonction unsigned long int hash_simple(const char *str)

le mot clé const va imposer de ne pas modifier ici str (constante)

on utilise ici un format d’entier particulier , unsigned long int

unsigned , donc que positif et énorme !! sur 64 bits !

Pourquoi avoir choisi ce type pour faire un hash ?

Donner le role de %ld et %lx dans notre code

le code du hash est essentiellement ici !

    p = str;
    while (*p != '\0')
    {
        hash = (hash * prime) + (unsigned long int)(*p);
        p++;
    }

(*p != ‘\0’) , sert à déterminer quoi ? (aidez vous de gdb)

L’algorithme du hash = (hash * prime) + (unsigned long int)(*p);

ici on découvre peut être le cast (un moule en francais) qui force un char ici *p en format unsigned long int

comment évolue le hash ?

la constante prime ici va nous servir à faire « un mélange » on y mettra un nombre premier pour augmenter le mélange …ici on a mis 1 vous pouvez utiliser d’autres prime et constater.

si prime vaut 1

si prime vaut 31

On va utiliser des nombres premiers pour prime , pour éviter les collisions

// Avec un nombre NON premier (ex: 4)
hash = (hash * 4) + char
// 4 = 2 × 2 → beaucoup de motifs répétitifs

// Avec un nombre premier (ex: 5)
hash = (hash * 5) + char
// 5 est premier → mélange meilleur

Conclure sur le hash