Tables de hachage
Contents
1. Fabrice Rossi 1997 2001 Conditions de distribution et de copie Cet ouvrage peut tre distribu et copi uniquement selon les conditions qui suivent 1 toute distribution commerciale de l ouvrage est interdite sans l accord pr alable explicite de l auteur Par distribution commerciale on entend une distribution de l ouvrage sous quelque forme que ce soit en change d une contribution financi re directe ou indirecte Il est par exemple interdit de distribuer cet ouvrage dans le cadre d une formation payante sans autorisation pr alable de l auteur 2 la redistribution gratuite de copies exactes de l ouvrage sous quelque forme que ce soit est autoris e selon les conditions qui suivent a toute copie de l ouvrage doit imp rativement indiquer clairement le nom de l auteur de l ouvrage b toute copie de l ouvrage doit imp rativement comporter les conditions de distribution et de copie c toute copie de Pouvrage doit pouvoir tre distribu e et copi e selon les conditions de distribution et de copie 3 la redistribution de versions modifi es de l ouvrage sous quelque forme que ce soit est interdite sans l accord pr alable explicite de l auteur La redistribution d une partie de l ouvrage est possible du moment que les conditions du point 2 sont v rifi es 4 l acceptation des conditions de distribution et de copie n est pas obligatoire En cas de non acceptation de ces conditions2. de cours 3 le programme devra comporter une classe de d monstration des autres classes permettant la manipulation de dictionnaires d j initialis s et comportant au moins une trentaine d enregistrement Il devra tre possible de modifier les dictionnaires ajout et suppression et de les interroger recherche d une d finition sans recompiler le programme Le projet devra tre rendu le 6 avril avant 17h Chaque jour de retard sera p nalis par le retrait de 4 points la note du projet Aucune excuse ne sera accept e sauf grave probl me m dical d ment attest par un certificat F Rossi 5 d cembre 2000 p 3
3. f s lt ts 1Ce n est bien s r pas la meilleure fa on de proc der Il vaudrait mieux cr er une classe Dictionnaire mais ce n est pas le but de ce projet F Rossi 5 d cembre 2000 p 2 DEUG MASS 1 re ann e Universit Paris IX Dauphine MD 3 3 Principe l mentaire des tables de hachage On suppose donc donn e une fonction de hachage f de taille ts Soit maintenant un enregistrement e constitu d une cl c et d une d finition d Normalement si on dispose d un dictionnaire T on va crire quelque chose de la forme T i e pour stocker l enregistrement dans la premi re case libre de T Gr ce la fonction de hachage on peut faire mieux On peut en effet crire TL c e Le principal int r t de cette technique est le suivant si on veut maintenant obtenir d la d finition associ e la cl c il suffit de calculer f c pour savoir dans quelle case du dictionnaire l enregistrement est rang Dans l approche de la section pr c dente il fallait regarder tous les enregistrements un par un afin de trouver le bon 3 4 Difficult Le principal probl me li cette approche est que deux cl s diff rentes peuvent avoir la m me image par la fonction de hachage ce qui veut dire qu on ne peut pas stocker directement un enregistrement dans la case T f c car sinon on ne pourra plus stocker aucun autre enregistrement dont la cl est d image gale f c Pour rem dier ce probl me
4. les r gles du droit d auteur s appliquent pleinement l ouvrage Toute reproduction ou repr sentation int grale ou partielle doit tre faite avec l autorisation de l auteur Seules sont autori s es d une part les reproductions strictement r serv es l usage priv et non destin es une utilisation collective et d autre part les courtes citations justifi es par le caract re scientifique ou d information de l oeuvre dans laquelle elles sont incorpor es loi du 11 mars 1957 et Code p nal art 425 DEUG MASS 1 re ann e Universit Paris IX Dauphine MD Tables de hachage 1 Introduction Le but de ce projet est la programmation d une structure de donn es appel e table de hachage Cette structure permet un stockage efficace d information sous une forme proche d un dictionnaire Dans un tableau Java on stocke les informations en les rep rant par un num ro leur indice dans le tableau Au contraire une table de hachage permet un rep rage plus intuitif th oriquement par n importe quelle cl Dans la pratique on s int resse surtout au stockage d informations rep r es par une cl alphanum rique le prototype tant le stockage d une d finition associ e un mot le dictionnaire 2 Un dictionnaire simple 2 1 Les donn es En vous inspirant de votre cours vous commencerez par d finir une classe Enregistrement donc chaque instance permet de stocker une d finition et une cl repr
5. sent es par des Strings Ainsi doit on pouvoir cr er un enregistrement gr ce la ligne suivante Enregistrement e new Enregistrement Voiture Engin de mort cher et polluant 2 2 Le dictionnaire Pour stocker un dictionnaire il suffit en fait de stocker des Enregistrements ce qui peut se faire sans probl me gr ce un tableau Le dictionnaire sera donc un Enregistrement 1 Vous crirez alors des m thodes de classe regroup es au sein de la classe Dictionnaire et permettant la manipulation du dictionnaire On proposera en autre des m thodes permettant d ajouter et de supprimer un Enregistrement un dictionnaire en produisant un nouveau tableau c est dire un nouveau dictionnaire de chercher une d finition en ne connaissant que la cl etc 3 Principe du hachage 3 1 Motivation Le principal d faut de la structure pr c dente est sa lenteur Pour chercher une d finition partir de sa cl il faut tudier tout le tableau Le but des techniques de hachage est de rem dier simplement ce probl me 3 2 Fonction de hachage Dans la suite de ce texte nous allons utiliser une fonction de hachage Dans le contexte des dictionnaires une fonction de hachage est une fonction qui une cl c est dire une String associe un entier positif ou nul On notera f une telle fonction On suppose qu chaque fonction de hachage f est associ e une taille t un entier tel que pour toute cl s O lt
6. on stocke dans le tableau T des dictionnaires simples Ceci signifie que le type de T est Enregistrement Si on appelle n la taille de f on peut m me dire que T va tre cr par Enregistrement T new Enregistrement n Quand on souhaite ajouter un enregistrement e de cl c on calcule donc f c et on ajoute e au diction naire T f c De m me pour recherche une d finition de cl u il suffit de rechercher cette d finition dans le dictionnaire T f u ce qui doit aller plus vite que dans un dictionnaire complet 4 Programmation 4 1 Fonction de hachage Pour une taille n donn e on obtient une fonction de hachage relativement efficace en associant une cha ne de caract res le reste de la division par n de la somme des codes Unicode de ses caract res 4 2 La table Vous programmerez une nouvelle classe Table fonctionnant de fa on similaire Dictionnaire mais utilisant la technique d crite dans la section pr c dente Vous pourrez bien s r utiliser la classe Dictionnaire que vous aurez d j programm e 5 Consignes g n rales En cas de non respect d une des r gles suivantes la note de projet sera divis e par deux 1 le projet sera rendu sous la forme d une disquette contenant les fichiers java de votre programme accompagn e d une impression de ses fichiers et d un mode d emploi 2 toutes les m thodes devront tre document es selon la m thode d crite au chapitre 11 du polycopi
Download Pdf Manuals
Related Search