Soit l’ensemble des éléments entiers strictement positifs Z = {11, 59, 32, 44, 31, 26, 19} et un tableau de taille 10. Nous allons donc ranger les éléments de Z dans un tableau dont l’index varie entre 0 et 9 (<10).
La fonction de hachage pour l’élément zi de l’ensemble Z est déterminée par :
h(zi) = zi modulo [10].
zi h(zi)
11 1
59 9
32 2
44 4
31 1
26 6
19 9
On constate dans cet exemple une duplication d’indices : 1 pour 11 et 31 ; 9 pour 59 et 19.
Plusieurs solutions sont possibles pour des éléments ayant le même indice :
soit utiliser un des indices libres disponible dans la table moyennant certaines regèles à définir ; sinon utiliser des listes (chaînées) d’objets (buckets) à cet indice.
Dans le cas de l’utilisation de buckets l’algorithme de recherche d’un élément dans la table se résume ainsi :
*****· Obtenir l’index i dans la table
**********¨ Calculer le hash code.
**********¨ Réduire le hash code modulo la taille de la table pour obtenir l’index i.
*****· Itérer dans le bucket à l’adresse i.
*****· Pour chaque élément dans le bucket vérifier s’il est égal à x, l’élément recherché.
*****· Si on trouve un élément égal à x alors x est dans l’ensemble.
*****· Autrement, x n’est pas dans l’ensemble.
Partager