Julien Sopena

Algorithmique avancée : Tables de hachage

Université :

Université Paris Descartes - Paris V

Année :

3ème année de licence d'informatique

Le cours.

Cours 01 :

Les tables de hachage. (1 par page / 8 par page).

Résumé :

Ce cours a pour but d'étudier les fonctions de hachages. Après avoir montré l'intérêt de telles fonctions, on étudiera les différentes fonctions de codage et d'adressage ainsi que les méthodes de résolution de collisions. Enfin, on finira par comparer ce nouvel outil, à ceux déjà étudiés par les étudiants les années précédentes (Recherche dichotomique, Arbre binaire, ABR...).

TD 01 : Les fonctions de hachage

Contenus :

Une fonction de hachage est le résultat de la composition d'une fonction de codage et d'une fonction d'adressage. Cette feuille de travaux dirigés a pour but de montrer aux étudiants que le choix de ces deux fonctions ne peut se faire indépendamment.

Ennoncé :

en ligne / pdf

TD 02 : La gestion de collisions

Contenus :

Comme on le montre dans le cours, la probabilité qu'une fonction uniforme soit injective tend rapidement vers zéro. Les collisions dans une table de hachage sont alors inévitables. Cette feuille de travaux dirigés a pour but d'étudier certaines des méthodes de résolution des collisions vues dans le cours.

Ennoncé :

en ligne / pdf

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License