Hachage pour les Fichiers PDF

Hachage pour les Fichiers Utilisation de méthodes de hachage pour l’accès aux fichiers PLAN Définition et Rappels Fichier avec hachage statique...

Hachage pour les Fichiers Utilisation de méthodes de hachage pour l’accès aux fichiers PLAN Définition et Rappels Fichier avec hachage statique Fichier avec hachage dynamique Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 1  Données La fonction h doit retourner des Table de à stocker valeurs entre 0 et N-1 Hachage T 0 Collision sur x3 x8 1 x2 la case 2 x5 Rangement x2 par calcul 2 x4 x7 x1 x7 d'adresse 3 x8 x4 h(x) 4 x6 5 x6 6 Stocker des données ( x ) dans une.. table ( T ) en utilisant une fonction ( h ).. x1 pour la localisation rapide (calcul d'adresse).. x3 On essaye de stocker x dans la case N-1 x7 d'indice h(x) (adresse primaire) Si la case est déjà occupée (collision), h(x4) = h(x7) = 2 on insère x à un autre emplacement x4 et x7 sont des synonymes l'adr primaire de x4 et x7 est 2 (adr secondaire) déterminé par un x7 est inséré en débordement algorithme donné (Méthode de l'adr secondaire de x7 est N-1 résolution de collisions) Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 2  Méthodes de hachage Combiner : une fonction de hachage avec une méthode de résolution de collisions – Ex. de fonction de hachage: h(x) = x MOD N L’espace adressable par la fonction est : [ 0 , N-1 ] – Bonne propriété d’une fonction de hachage : ⇒ minimise les collisions tout en minimisant l’étendue de l’espace adressable. – Une méthode de résolution de collision permet de gérer (rechercher, insérer et supprimer) les données ayant provoqués des collisions Ex. Essai-Linéaire, Chaînage externe, Double Hachage … Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 3  Fichier avec hachage 0 L'adresse primaire de l'enregistrement de 1 clé x est le bloc numéro h(x) h(x) Si le bloc est plein, on utilise l'une des... méthodes de résolution de i collisions. x La capacité d'un bloc... est de b enregistrements N-1 Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 4  Utilisation d’une méthode de hachage comme structure de fichiers 1. Utiliser une table de hachage comme un index, en MC, pour accélérer les accès aux fichiers de données. Table de hachage Fichier de données en MC en MS clé | adr 0 h(x). x ,... i N-1 j x,aaa,bbb... Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 5  Utilisation d’une méthode de hachage comme structure de fichiers 2. Utiliser un index en MS, géré par une méthode de hachage. Fichier index Fichier de données en MS en MS 0.... h(x) x,... i... j x,aaa,bbb N-1... Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 6  Utilisation d’une méthode de hachage comme structure de fichiers 3. Gérer le fichier de données par une méthode de hachage. Fichier de données 0 en MS 1 h(x)... i x,aaa,bbb... N-1 Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 7  Méthodes de résolution de collisions - Essai Linéaire Séquence de tests : les blocs n° h(x) , h(x)-1 , h(x)-2 , … 0 , N-1 , … - Double Hachage Séquence de tests : les blocs n° h1(x) , h1(x)-h2(x) , h1(x)-2h2(x) , … - Chaînage Externe Séquence de tests : le bloc n° h(x) et ceux de sa liste de débordement qui se situent en dehors de la zone adressable par la fonction h - Chaînage Interne Séquence de tests : le bloc n° h(x) et ceux de sa liste de débordement qui se situent à l’intérieur de la zone adressable par la fonction h Hidouci W. K. / Hachage en MS/ Structures de fichiers (SFSD) / E.S.I 8  Essai Linéaire 0 Il doit toujours exister au moins un bloc non plein bloc_non_plein --