4. Les composants de l'architecture d'un système de bases de données
137
pouvons appliquer des transformations répétées à la clé en question.
Le traitement du débordement se complique lorsque le domaine des
valeurs d'une clé croît rapidement ou qu'il faut exécuter un grand
nombre de suppressions. Pour surmonter ces problèmes, des
méthodes de transformation de clés par hachage dynamique ont été
développées.
Figure 4-12
Hachage par la
création de classes
selon le reste de la
division
Hachage
dynamique
Dans les méthodes de hachage dynamique, nous cherchons à
rendre l'occupation de la mémoire indépendante de la croissance du
EMPLOYÉ
E19
E1
E7
E4
Savoy
Meier
Humbert
Brodard
E#
Nom
D6
D3
D5
D6
Affectation
Romont
Fribourg
Bulle
Fribourg
Ville
Fonction de hachage
k mod 5
Insérer : E19 E1 E7 E4
k mod 5 : 4
1
2
4
E19
E4
E7
E1
Page 0
Page 4
Page 3
Page 2
Page 1
Insérer : E3 E9 E18 E24 E2
k mod 5 : 3
4
3
4
2
E19
E4
E9
E24
E7
E2
E1
E3
E18
Page 0
Page 4
Page 3
Page 2
Page 1
Insérer : E26 E15 E14 E22 E20
k mod 5 : 1
0
4
2
0
E14
E15
E20
E19
E4
E9
E24
E3
E18
E7
E2
E22
E1
E26
Zone de débordement
Page 0
Page 4
Page 3
Page 2
Page 1