Julien Sopena

TD 02 – Fonctions de hachage : Résolutions de collisions

Exercice 1: Complexité de recherche dans un hachage avec chaînage

On considérera ici la fonction de hachage h(k) = k mod 9 et une résolution des collisions par chaînage.

Question 1.1 )

Quelle doit être la taille de la table de hachage ?

Question 1.2 )

On insère successivement les clés suivantes : { 5, 28, 19, 15, 20, 33, 12, 17 } . Représentez graphiquement l'état de la table après ces insertions.

Question 1.3 )

Calculez le coût moyen d'une recherche fructueuse.

Question 1.4 )

Rappelez les propriétés d'une fonction de hachage uniforme.

Question 1.5 )

On considère maintenant une fonction de hachage uniforme h: K ⊢→ [0,m−1] et l'insertion de n clés.

Quelle est la complexité dans le pire cas d'une recherche infructueuse ?

Quelle est la complexité dans le pire cas d'une recherche fructueuse ?

Question 1.6 )

Quelle est la complexité moyenne d'une recherche infructueuse ?

Quelle est la complexité moyenne d'une recherche fructueuse ?

Question 1.7 )

Déduire de la question précédente la complexité d'une recherche si l'on suppose n=O(m).

Exercice 2: Suppression d'une clé avec une résolution par coalescence

Dans cet exercice on se propose d'étudier la suppression dans une table de hachage avec résolution des collisions par coalescence (lien explicite).

On considérera la fonction de hachage h(k) = k mod 7 . Une structure Disponible de type FIFO contiendra l'ensemble des cases disponibles pour gérer les collisions (les cases vides).

Question 2.1 )

Donnez l'état de la table après l'insertion des clés suivantes { 11, 10, 4, 25, 18} si l'ensemble ordonné Disponible contient : { 4,3,2,6,5 }

Question 2.2 )

Rappelez la méthode de suppression d'un élément au milieu d'une liste chaînée.

Question 2.3 )

Donnez l'état de la table après la suppression de la clé 4 par cette technique.

Question 2.4 )

Recommençons l'insertion avec la séquence de clés suivante : {11, 4, 25, 18, 10}. On considérera une nouvelle fois que l'ensemble Disponible contient : {4,3,2,6,5}. Quel est maintenant l'état de la table ?

Question 2.5 )

Donnez l'état de cette nouvelle table après la suppression de la clé 4 par la technique précédemment décrite. Que remarquez-vous ?

Question 2.6 )

Peut-on toujours prendre la clé se trouvant à l'extrémité de la chaîne pour remplacer la clé à supprimer ? (Donnez un exemple)

Question 2.7 )

Quelles peuvent être les valeurs (h(k)) de hachage d'une clé k se trouvant dans la case i de la table de hachage ?

Question 2.8 )

Donnez l'idée d'un algorithme de suppression d'une clé dans une table de hachage avec résolution des collisions par coalescence (lien explicite).

Exercice 3: Résolution par double hachage

On veut insérer les clés suivantes : { 7, 16, 28, 40, 6, 49 } dans une table hachage.

La fonction de hachage utilisée sera h(k) = k mod 11

Question 3.1 )

Dans un premier temps on utilisera la méthode du sondage linéaire pour résoudre les collisions.

Que devient la formule de la fonction de hachage considérée après utilisation de cette méthode ?

S'agit-il alors d'un hachage ouvert ou d'un hachage fermé ? Donnez un exemple de hachage de l'autre famille.

Question 3.2 )

Donnez l'état de table après les insertions. Que remarquez vous ?

Question 3.3 )

On utilise maintenant une double fonction de hachage. Donnez la nouvelle fonction de hachage si : h2(k) = 1 + k mod (m−1) .

Quel est l'état de table après les insertions ?

Comparez le résultat avec le précédent.

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