Gestion des collisions par chaînage linéaire

Pour gérer les collisions, on va regrouper les valeurs {v} ay«ant une même clef hachée {i=h(k(v))} dans une liste en position {i} d’un tableau de longueur {m(}ces lignes sont appelées les buckets »). Plus précisément, un bucket est une liste de couples {(k(v),v),} et c’est en le parcourant qu’on peut retrouver (ou supprimer) une valeur de clef {k.} Pour ne pas perdre le bénéfice du hachage, ces listes doivent garder une taille raisonnable (les valeurs en conflit ne doivent pas être trop nombreuses).

On définit une « table de hachage » comme la donnée d’une fonction de hachage et d’un tableau de listes de couples (clef,valeur). Dans la case d’indice {i} de ce tableau, on placera la liste (éventuellement vide) des couples {(k(v),v)} du dictionnaire {\mathcal{D}} pour les {v} de la collection dont la clef hachée {h(k(v))} est égale à {i.}

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