Gestion des collisions par sondage (probing)

Rappelons que tout couple clef/valeur {(k(v),v)} du dictionnaire est placée dans une table de largeur {m,} à une position {i=h(k(v)),} où {h} est la fonction de hachage à valeurs dans {[\![ 0,m[\![ .}

Alors qu’à deux valeurs différentes correspondent deux clefs différentes, l’application {k\mapsto h(k)} n’est certainement pas injective (l’entier {m} est petit devant l’univers de clefs).

On doit donc gérer les « collisions » (valeurs différentes {v} ayant même clef de hachage {h(k(v)),} et augmenter dynamiquement la taille de la table si leur nombre est trop grand (car c’est lui qui ralentit les opérations de recherche/lecture/écriture).

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :