Gestion de Fichiers

Hachage (suite)

2

Plan du cours d’aujourd’hui Prédiction de la distribution des

enregistrements Réduction des collisions en augmentant

l’espace mémoire Résolution des collisions par débordement

progressif (“progressive overflow”)

3

Prédiction de la distribution des enregistrements

Pour rappel, il y a 3 sortes de distributions possibles d’adresses: uniforme, rien que des synonymes ainsi que au hasard.

Avec une distribution au hasard, on peut utiliser des outils mathématiques pour estimer le comportement de la fonction de hachage. Assumons 1 enreg. par adresse.

Soit N = nombre d’adresses disponibles; r = nombre d’enregistrements à stocker; p(x) = probabilité pour qu’une adresse donnée ait un nombre x d’enreg.s Pour N et r suffisament large: p(x) ~ (r/N)xe–(r/N)/x!

4

Prédiction de la distribution des enregistrements (suite)

Exemples: pour N = 1000 et r = 1000 nous avons: p(0) ~ 10e–1/0! = 0.368 p(1) ~ 11e–1/1! = 0.368 p(2) ~ 12e–1/2! = 0.184 p(3) ~ 13e–1/3! = 0.061 etc. En général, s’il y a N adresses, le nombre escompté

d’adresses avec x enregistrements est

Np(x) En fait, p(x) nous donne la proportion d’adresses pouvant

servir de domicile à x enregistrements logiques.

5

Prédiction de la distribution des enregistrements (suite)

Exemples: pour N = 1000 et r = 1000 nous avons: # escompté d’adresses avec 0 enreg.s ~ 1000*0.368

# escompté d’adresses avec 1 enreg.s ~ 1000*0.368

# escompté d’adresses avec 2 enreg.s ~ 1000*0.184

# escompté d’adresses avec 3 enreg.s ~ 1000*0.061

etc. Pour N = 10000 et r = 10000 (fichier plein): r/N = 1 et #

escompté d’adresses avec 1 enreg.s ~ 3679

# escompté d’adresses avec 2 enreg.s ~ 1839

# escompté d’adresses avec 3 enreg.s ~ 613

6

Prédiction de la distribution des enregistrements (suite)

Pour N = 10000 et r = 10000 (fichier plein): r/N = 1 et # escompté d’adresses avec 1 enreg.s ~ 3679

pas de synonymes # escompté d’adresses avec 2 enreg.s ~ 1839 il y aura débordement de 1 * 1839 enreg.s # escompté d’adresses avec 3 enreg.s ~ 613 il y aura débordement de 2 * 613 enregs.

En général: # escompté d’adresses avec x enreg.s ~ N * 1xe–1/x! il y aura débordement de (x-1) * (N * 1xe–1/x!) enregs.

7

Prédiction de la distribution des enregistrements (suite)

Nous venons de voir que, pour des valeurs donnés de N et r , le # escompté d’adresses avec x enreg.s ~ N * 1xe–

1/x! et ce # engendre un débordement d’enreg.s de l’ordre de

(x-1) * (N * 1xe–1/x!) Ces débordements constituent un grave problème don’t il

faut s’occuper. Solutions possibles: -- développer une bonne fonction de hachage (déjà vu) -- réduire le # de débordements -- développer une méthode de traitement des débordements

8

Augmentation d’espace mémoire

Une réduction de collisions peut être atteinte en utilisant de la mémoire additionelle.

La question à poser est la suivante: Quel montant de mémoire additionnelle doit on utiliser pour obtenir un taux de réduction de collision donnée?

Definition: la densite d’enregistrement (“Packing Density” -- PD) correspond à la proportion du # d’enreg.s à sauvegarder (r) par rapport au # d’espaces disponibles (N); i.e. c’est le rapport r/N.

La densité d'enregistrement nous donne une mesure du montant d’espace de fichier vraiment utilisé.

9

Augmentation d’espace mémoire (suite)

La distribution Poisson nous permet de prédire le nombre de collisions qui peuvent se produire étant donne une certaine densité d’enregistrement.

Supposez que r = 500 et N = 1000 PD = 50%. On peut ainsi répondre aux questions suivantes:

1. Combien d’adresses n’ont aucun enregistrement qui y soient affecté?

N * p(0) = 1000 * 0.607 = 607

2. Combien d’adresses n’ont qu’un enregistrement qui y soit affecté (pas de synonymes)?

N * p(1) = 1000 * 0.303 = 303

10

Augmentation d’espace mémoire (suite)

3. Combien d’adresses ont deux ou plusieurs synonymes?

N * (p(2) + p(3) + p(4) + …) = N * (1 – (p(0) + p(1)) = 1000 * 0.09 = 90

4. En supposant qu’un seul enregistrement peut être affecté à chaque adresse, à combien d’enregistrements debordants peut-on s’attendre? # enreg.s débordants attendus = # enreg.s - # attendu d’enreg.s nondébordants = r – (N * p(1) + N * p(2) + N * p(3) + …) = r – N * (1 – p(0)) (Raison: somme des probabilité =

1) = r – N + N * p(0) = N * p(0) + [- - (r-N)] = N * p(0) – (N-r) = # d’adresses sans enreg.s + # enreg.s du hachage parfait ~ 107

11

Augmentation d’espace mémoire (suite)

4. En supposant qu’un seul enregistrement peut être affecté à chaque adresse, à combien

d’enregistrements debordants peut-on s’attendre? – 2ème formule (du

livre) Utiliser la formule en bas du transparent 6:

1 * N * p(2) + 2 * N * p(3) + 3 * N * p(4) + …. = N * [p(2) + 2 * p(3) + 3 * p(4) + …]

Dans notre exemple avec PD = 50% nous avons ~107

12

Augmentation d’espace mémoire (suite)

5. Quel est le pourcentage attendu d’enregistrements débordant?

[N * p(0) – (N-r)]/r = 1 – 1/PD * (1 – p(0))

Dans notre exemple, c’est 107/500 = 0.214 = 21.4%

Note importante: ce pourcentage ne dépend que de PD et non des valeurs individuelles de N et r. Bien plus, la fonction p() ne dépend elle aussi que de PD. Ainsi donc, la conclusion majeure ici est que si PD=50%,

le hachage donnera toujours un taux de 21.4% d’enreg.s débordants.

13

Augmentation d’espace mémoire (suite)

Etant donné PD, nous pouvons donc calculer ce pourcentage et l’afficher sur un tableau:

Densité d’enregistrement Débordement

10% 4.8% 20% 9.4% 40% 17.6% 60% 24.8% 80% 31.2% 100% 36.8%

14

Résolution de collision par débordement progressif

Quelque soit la perfection d’une fonction de hachage, des enregistrements peuvent toujours entrer en collision. Certains manqueront donc de la place à leur adresse.

Une approche simple est la suivante pour résoudre ce cas est le débordement progressif.

Pour inserer une clé k: - Aller à l’adresse domiciliaire h(k) - Si h(k) est libre, inserer k à cet endroit - Sinon, chercher la première adresse disponible qui suit h(k) et y placer k. Si on atteint la fin de l’espace adresse avant de trouver une adresse disponible alors, on retourne au début de cet espace adresse et on y continue la recherche.

15

Résolution de collision par débordement progressif (suite)

Pour chercher une clé k: - Aller à l’adresse domiciliaire h(k) - Si k s’y trouve, arrêter la recherche - Sinon, chercher les adresses occupées suivant h(k) jusqu’à ce qu’on trouve k. Si l’on atteint soit une adresse inoccupée ou l’adresse domiciliaire h(k) à nouveau, alors k ne se trouve pas dans le fichier d’indexes. Dans ce dernier cas, on dira que la recherche retourné à son point de départ. Avantage: simplicité d’usage Désavantage: formation de regroupements d’enreg.s

16

Longueur d’un recherche dans l’utilisation du débordement progressif

Le débordement progressif cause des recherches additionelles et, donc, des seeks additionnels.

S’il y a beaucoup de collisions, alors beaucoup d’enregistrements seront loin de leur adresse domiciliaire.

La longueur de recherche correspond au nombre d’accès requis pour récuperer un enregistrement de la mémoire secondaire. La longueur moyenne est le montant de temps moyen auquel on peut s’attendre pour récuperer un enregistrement du disque.

longueur de recherche moyenne = (longueur de recherche totale)/(# total d’enreg.s) Voir Figure 11.6 dans le livre pour un exemple.