Algorithmique - Programmation Objet - Python
Corrigé du TD 10

1) Résolution de collisions par chaînage

1.1)

Table de hachage :
valeur de hachage    0  1  2  3  4  5  6  7  8  9
indice débordement   8  0  1  7  0  3  0  5  4  0

Table de débordement :
indice    1    2    3    4    5    6    7    8
clé      22   12    5    8   17    2    3   10
élément  e1   e2   e3   e4   e5   e6   e7   e8
suivant   2    6    0    0    0    0    0    0

1.2)

a) clé 2 : hash(2) = 2, donc on regarde l'alvéole de la table de hachage
correspondant à la valeur 2, qui contient 1 comme indice de débordement ;
dans la case 1 de la table de débordement, il y a l'élément e1 avec clé 22,
donc il faut voir le suivant, dont l'indice est 2 ; dans la case 2 il y a
l'élément e2 avec clé 12, donc il faut voir le suivant, dont l'indice est 6.
Finalement, dans la case 6 on trouve e6, qui a clé 2.
Pour

b) clé 1 : hash(1) = 1, donc on considère l'alvéole 1 de la table de hachage,
qui contient l'indice de débordement 0, signe qu'un élément avec clé 1 n'est
pas présent.

1.3)

On va appeler H la table de hachage et D la table de débordement,
n le nombre d'éléments déjà présents.

insère(élt, clé) :
  i <- hash(clé)
  si H[i] = 0
    n <- n + 1
    D[n].clé <- clé
    D[n].élément <- élt
    D[n].suivant <- 0
    H[i] <- n
  sinon
    j <- H[i]
    tant que D[j].suivant != 0 et D[j].clé != clé
      j <- D[j].suivant
    si D[j].clé != clé
      n <- n + 1
      D[n].clé <- clé
      D[n].élément <- élt
      D[n].suivant <- 0
      D[j].suivant <- n

recherche(clé) :
  i <- hash(clé)
  si H[i] > 0
    j <- H[i]
    tant que D[j].suivant != 0 et D[j].clé != clé
      j <- D[j].suivant
    si D[j].clé = clé
      renvoyer D[j].élément
  renvoyer nil
   
appartient(clé) :
  renvoyer recherche(clé) != nil

2) Résolution de collisions par adressage ouvert

2.1)

Table de hachage :
valeur de hachage    0    1    2    3    4    5    6    7    8    9
clé                 10    0   22   12    2    5    3   17    8    0
élément             e8  nil   e1   e2   e6   e3   e7   e5   e4  nil

2.2)

Table de hachage :
valeur de hachage    0    1    2    3    4    5    6    7    8    9
clé                  0    0   22    0   12    5    0   17    8    0
élément            nil  nil   e1  nil   e2   e3  nil   e5   e4  nil

Remarque : en essayant d'insérer l'élément (e6, 2), le sondage quadratique
entre dans une boucle infinie, puisque i + i² (mod 10) donne la séquence
périodique : 2, 6, 2, 0, 0, 2, 6, 2, 0, 0, ..., qui touche toujours des
alvéoles déjà occupés.

2.3)

On a déjà observé le problème qui peut dériver du sondage quadratique.
Une solution évidante pour éviter un comportement périodique consiste à
choisir un nombre premier pour m. Dans le cas de l'exemple, une table
de hachage avec 11 alvéoles resoudrait le problème.

insère(élt, clé) :
  n <- 0
  répéter
    i <- next(clé, n)
  tant que H[i].clé > 0
  H[i].clé <- clé
  H[i].élément <- élt

recherche(clé) :
  n <- 0
  répéter
    i <- next(clé, n)
  tant que H[i].clé > 0 et H[i].clé != clé
  renvoyer H[i].élément
   
appartient(clé) :
  renvoyer recherche(clé) != nil

Il s'agira tout simplément de redéfinir la fonction next(clé, n)
selon les trois méthodes de sondage ; les trois méthodes ne changent pas.

3) Suppression dans une table à adressage ouvert

[à faire]