C10 Tableau associatif, hachage ¶

"Warning a hash table is only as good as the hash function. A bad hash function will turn the table into a degenerate association list, with linear time lookup instead of constant time lookup."
ocaml.org
(Module Hashtbl)

Cours¶

Support de cours chapitre 10

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés¶

Fiche de TD10

Travaux pratiques¶

Exercice 1 : Implémentation en C d'une table de hachage¶

On reprend ici l'exemple vu en cours du calcul du nombre d'occurrence des mots dans un texte. On rappelle qu'unque les maillons des listes chainées utilisées sont définies par :

    struct node
    {
        char word[26];
        int occ;
        struct node *next;
    };
    typedef struct node node;
    typedef node* list;

Ecrire la fonction de prototype bool is_in_list(list l, char w[26]) qui renvoie true ou false selon que la chaine de caractère w figure ou non dans la liste l.

Aide

La fonction strcmp disponible après avoir inclus string.h compare deux chaines de caractères et renvoie 0 lorsqu'elles sont égales.
Ecrire les autres fonctions nécessaires :
1. Ajouter une nouvelle clé de prototype void insert(list *l, char w[26])
2. Récupérer la valeur associée à une clé : int value(list l, char w[26])
3. Modifier la valeur associée à une clé présente : void update(list *l, char w[26], int v)
La table de hachage est alors définie comme un tableau de liste chainées de taille SIZE (fixée en
```
           
```
Pour tester si une clé est présente dans la table de hachage il suffit alors de tester si elle est présente dans
```
    
```
Ecrire les autres fonctions nécessaires : début de programme). On prend comme fonction de hachage la somme des codes ascii contenu dans la chaine : href="#__codelineno-1-1"> unsigned hahsword(char word[26]) { unsigned hash = 0; char c; int i=0; while ((c=word[i])!='\0') { hash += c; i++; } return hash; } le seau correpondant à son hash : href="#__codelineno-2-1"> bool is_in_hashtable(list hashtable[SIZE], char w[26]) { int bucket_number = hahsword(w)%SIZE; return is_in_list(hashtable[bucket_number], w); }

a. void insert_in_hashtable(list ht[SIZE], char w[26]) pour insérer une nouvelle clé. b. update_hashtable(list ht[SIZE], char w[26], int n) pour mettre à jour la valeur associée à une clé.

c. int get_value_hashtable(list ht[SIZE], char w[26]) pour récupérer la valeur associée à une clé.
On donne ci-dessous une fonction permettant de lire une ligne d'un fichier sur un canal de lecture FILE * déjà ouvert:
```
    char* get_word(FILE * reader)
    {
        char *word = malloc(sizeof(char)*MAX_SIZE);
        if (fscanf(reader,"%s",word)==1)
            {return word;}
        else
            {
            free(word);
            return NULL;}
    }
```
Utiliser cette fonction pour lire le fichier de mots extraits de l'oeuvre de J. Verne 20000 lieues sous les mers disponible ci-dessous : Mots extraits Combien de fois le mot "nautilus" apparaît-il dans le livre ?
Tester votre réponse :

Exercice 2 : Implémentation en OCaml avec le type array¶

La table de hachage est un tableau de liste de couples string*int :

    type hashtable = (string * int) list array
    let size = 100000
    let ht = Array.make  size []
    let reader = open_in "mots.txt"

C'est la traduction en OCaml de l'implémentation en C vue dans l'exercice précédent. Reprendre les mêmes questions que ci-dessus.

Exercice 3 : Implémentation en OCaml avec le module Hashtbl¶

On doit utiliser le module Hashtbl et créer la table de hachage en lui donnant un taille de départ (elle sera automatiquement redimensionnée si nécessaire)

    open Hashtbl
    let my_ht = Hashtbl.create 10000
    let reader = open_in "mots.txt"

La fonction de hachage est Hashtbl.hash est fonctionne sur des données de n'importe quel type. Utiliser cette nouvelle implémentation dans le problème du calcul du nombre d'occurrence des mots d'un texte.

Aide

Hashtbl.mem permet de tester l'appartenance
Hashtbl.add permet d'ajouter un nouveau couple (clé, valeur)
Hashtbl.find permet de récupérer la valeur associée à une clé
Hashtbl.replace permet de modifier la valeur associée à une clé

Exercice 4 : Somme de deux éléments d'un tableau¶

Etant donné un tableau d'entiers T et un entier s, le problème est de déterminer s'ils existent deux éléments de ce tableau dont la somme est s. Par exemple, si T = [5, 6, 1, -4, 3] et s=9 alors la solution est (6,3).

Ecrire une version naïve de complexité quadratique permettant de résoudre le problème à l'aide d'une double boucle.
En utilisant une table de hachage (et dans le langage de votre choix) écrire une solution plus efficace.
Tester ces deux implémentations en mesurant leur performance sur les nombres téléchargeables ci-dessous en recherchant deux nombres de somme 42 Liste de nombres Vous pouvez tester votre réponse : (donner le plus grand des deux nombres)

Exercice 5 : Recherche de cycle dans un jeu de la vie à une dimension¶

On considère une variante du jeu de la vie se déroulant dans un tableau à une dimension. L'évolution de la case d'indice \(i\) de ce tableau ne dépend que de l'état de la case d'indice \(i\) et de ses voisins immédiats (donc les cases d'indices \(i-1\) et \(i+1\).). On donne ci-dessous l'évolution de la case centrale en fonction de l'état de ces 3 cases en notant "#" une case vivante et "." une case morte

... \(\rightarrow\) . (si les 3 cases sont vides, la case centrale reste vide)
..# \(\rightarrow\) #
.#. \(\rightarrow\) .
.## \(\rightarrow\) #
#.. \(\rightarrow\) #
#.# \(\rightarrow\) .
##. \(\rightarrow\) #
### \(\rightarrow\) .

Note

Ces évolutions correspondent à la rule90

D'autre part on considère ici un tableau fini de \(N\) cases et on considère que la voisine de gauche de la case d'indice 0 ainsi que la voisine de droite de la case d'indice \(N-1\) sont toujours des cellules mortes. On donne ci-dessous un exemple d'évolution avec \(N=10\)

🟐

evolue en

🟐

Ecrire une implémentation (dans le langage de votre choix) d'une fonction prenant en entrée un tableau de \(N\) cases et renvoyant le tableau représentant l'évolution du tableau après une itération des règles de transformation.

Pour \(N=30\) et pour le tableau initial représenté par "...............#.............." (toutes les cases sont mortes sauf la case d'indice 15) faire afficher les 100 premières évolutions successives.

Aide

Les premières lignes sont :

...............#..............
..............#.#.............
.............#...#............
............#.#.#.#...........
...........#.......#..........
..........#.#.....#.#.........
.........#...#...#...#........
........#.#.#.#.#.#.#.#.......
.......#...............#......
......#.#.............#.#.....
.....#...#...........#...#....
....#.#.#.#.........#.#.#.#...

Justifier rapidement que les évolutions successives contiennent un cycle, c'est-à-dire qu'on retombe sur un contenu de tableau déjà obtenu lors d'une évolution précédente.
Proposer une solution utilisant une table de hachage et permettant de déterminer le nombre d'itérations nécessaires avant de rencontrer un motif déjà parcouru.
Testez votre réponse (pour le motif de départ de la question 2)
L'algorithme du lièvre et de la tortue de Floyd est un algorithme de détection de cycle. Le principe est de parcourir la liste des états avec une tortue (qui avance de 1 en 1) et un lièvre (qui avance par pas de 2). Si la tortue et le lièvre se rencontrent cela signifie qu'un cycle existe. Proposer une implémentation de ce nouvel algorithme.

Humour d'informaticien¶

semicolon