136
Introduction pratique aux bases de données relationnelles
„ les adresses réservées doivent être uniformément distribuées
dans l’espace d'adressage ;
„ la probabilité d'associer des mêmes adresses à plusieurs clés doit
être uniforme pour toutes les valeurs de clé.
Il existe une grande variété de fonctions de hachage avec leurs
avantages et leurs inconvénients. La méthode la plus connue et la plus
simple est le hachage utilisant le reste d'une division.
Hachage par la méthode de la division
Fonction de
hachage par la
méthode de la
division
Chaque clé est interprétée comme un nombre naturel. Étant
donné une clé k et un nombre premier p, la fonction de hachage H qui
transforme la clé s'exprime par la formule suivante :
H(k) := k mod p.
La division de la valeur de clé k par le nombre premier p donne
un reste entier «k mod p» qui désigne une adresse relative ou un
numéro de page relatif. Avec cette méthode, le choix du nombre
premier p détermine l'occupation de la mémoire et le degré
d'uniformité de la distribution des adresses à l'intérieur de l’espace
d'adressage.
Exemple de
création des
classes par le reste
de la division
Dans la figure 4-12, les valeurs de la clé E# dans la table
EMPLOYÉ sont insérées dans les différentes pages par la méthode de
la division. Pour cet exemple simple, nous supposons que chaque
page peut recevoir quatre valeurs de clé. Nous choisissons le nombre
premier 5. Chaque valeur de clé est ensuite divisée par 5, donnant un
reste entier qui détermine le numéro de page.
Au moment d'insérer la valeur de clé E14, une collision a lieu car
l'adresse calculée pointe vers une page qui est déjà saturée. C'est
pourquoi nous plaçons E14 dans une zone de débordement. Le
chaînage de la page 4 à la zone de débordement garantit
l'appartenance de la valeur de clé E14 à la classe 4 (reste de la division
de 14 par 5).
Traitement des
débordements
Il existe plusieurs techniques pour traiter le problème de
débordement. Au lieu de créer une zone de débordement, nous