Les tables de dispersions

Question 1

Les tables de dispersions servent notamment à implémenter des …

Answer 1

dictionnaires

Question 2

Déf : Dictionnaire

Answer 2

• Conteneur d’éléments, non ordonné

- Insertion, suppression, trouver presque toujours en O(1)

Question 3

Que fait une fonction de hachage ?

Answer 3

Transforme la clé x, identifiant chaque élément, en un index d’un tableau que l’on appelle de dispersion.
L’index doit être entre 0 et la taille N du tableau - 1

Question 4

Déf : Collision

Answer 4

Le même index est calculé pour 2 clé distinctes

Question 5

Déf : Bonne fonction de hachage

Answer 5

doit disperser ses valeurs d’index le plus uniformément possible dans {0, 1, …, N-1}

Question 6

De quoi dépend le temps d’exécution d’une fonction de hachage

Answer 6

• dépend seulement de la taille de la clé

- Ne dépend PAS de la taille du tableau

Question 7

Bon choix de taille d’une table dispersion

Answer 7

Généralement un nombre premier supérieur à l’espace requis par le programme.

Question 8

Une fonction de hachage est composée

Answer 8

• d’un “code de hachage” qui transforme la clé en entier non-signé e
• d’une “fonction de compression” qui transforme e en index de la table de dispersion

Question 9

Pourquoi le hachage polynomial est-il pertinent ?

Answer 9

Obtenir une meilleure dispersion en tenant compte de la position des caractères de la clé dans le calcul du hachage.

Question 10

Avantages et Désavantages du chaînage externe

Answer 10

Avantages :

• simplicité de gestion de la table
• collisions n’ont pas d’effet Domino

Désavantages :
- 1 ptr par clé Þ ajout d’espace
- Nécessité d’allouer dynamiquement la mémoire à chaque
insertion

Question 11

Principe du chaînage externe

Answer 11

• On utilise un tableau de listes
• Chaque liste contient les clés qui hachent
  à la même valeur d’index

(Voir schéma P18)

Question 12

Comment calcule-t-on le taux d’occupation de la table de dispersion (λ)

Answer 12

λ = n / N

N : taille de la table
n : nombre d’éléments

Question 13

Dans le cas du hachage externe pourquoi re-hacher dès que taux d’occupation devient plus grand que 1

Answer 13

Les recherches/suppressions/insertions pour une clé x nécessitent
d’examiner la liste h(x) pour s’avoir si x est dans cette liste.
- Cela nécessite un temps O(λ) pour tout x. (en meilleur cas)

Donc si λ > 1 on est plus en temps constant.

Question 14

Le coût général du re-hachage (cas chaînage externe)

Answer 14

Θ(n+N) = Θ(n)

Car n = N+1

Question 15

Le coût PAR ÉLÉMENT du re-hachage (cas chaînage externe)

Answer 15

O(1)

Question 16

Adressage Ouvert : Structure de données

Answer 16

• Utiliser directement la table de dispersion pour stocker la valeur.
  -> Pas d’allocation nécessaire à chaque valeur.
• ## Champ état (Active, Deleted, Empty) en plus de la valeur

Question 17

Adressage Ouvert : Calcul de l’index d’une valeur

Answer 17

• hi(x) = ( h(x) + f(i) ) mod N

- f(i) définissant ce que l’on fait après la ième collision. C’est le “sondage”

Question 18

Adressage Ouvert : comment fonctionne trouverPosition(x)

Answer 18

effectue la séquence de sondages h0(x), h1(x), h2(x), …
et retourne l’index hi(x) de la première case qui est dans l’état EMPTY ou qui
contient x (dans l’état ACTIVE ou DELETED).

Question 19

Adressage Ouvert : taux d’occupation λ maximum

Answer 19

λ = 1/2

Puisque toutes les données doivent être stockées dans la table, celle-ci
devra être plus grande que celle utilisée pour le chaînage externe

Question 20

Principe du sondage linéaire

Answer 20

f(i) = i

Alors hi(x) = (h(x) + i) Mod N

Question 21

Problème du sondage linéaire

Answer 21

• Formation de regroupements primaires

- ceux ci provoquent de très longe séquences de sondages

Question 22

Principe du Sondage Quadratique

Answer 22

f(i) = i²

Alors hi(x) = (h(x) + i²) Mod N

Question 23

Théorème Sondage Quadratique

Answer 23

Si la taille N de la table est un nombre premier, il sera
toujours possible de pouvoir insérer un élément avec le sondage quadratique
lorsqu’il y a ⎡𝑵/𝟐⎤ cases vides ou plus.

Question 24

Le sondage quadratique : Onest assuré de pouvoir insérer une clé si

Answer 24

• Table à moitier vide

- Taille est un nombre premier

Question 25

Preuve du Théorème du Sondage Quadratique

Answer 25

Stratégie : Nous allons démontrer que les ⎡𝑵/𝟐⎤ premières positions sondées sont
toutes distinctes.
⇒ (Si c’est le cas, un des sondages trouvera nécessairement une case vide
puisqu’il y a en au moins ⎡𝑵/𝟐⎤ qui sont vides parmi N)

1) Poser 2 sondages le i-ème et j-ième
- avec i < j sans perte de généralité
- et 0 ≤ i,j ≤ ⎡𝑵/𝟐⎤ - 1 = ⎣𝑵/𝟐⎦ (car N est impair)

2) Si les 2 sondages pouvaient être identiques alors
( h(x) + i² ) mod N = ( h(x) + j² ) mod N
⇒ i² mod N = j² mod N
⇒ (j² - i²) mod N = 0
⇒ (j – i) (j + i) mod N = 0
⇒ (j – i) (j + i) doit être un multiple de N

Impossible car N est premier et i,j ≤ ⎣𝑵/𝟐⎦. CQFD

Question 26

Principe du double hachage

Answer 26

f(i) = i * h’(x)

hi(x) = ( h(x) + f(i) ) mod N

h’(x) ne doit jamais être = 0

Question 27

Double hachage : fonction fréquente h’(x) =

Answer 27

h’(x) = R - c(x) mod R

Où R est un nombre premier plus petit que N

Question 28

Double hachage vs sondage quadratique

Answer 28

Pour 2 valeurs hachant au même index, le double hachage ne produit généralement pas la même séquence de sondage subséquente.
⇒ il produit moins de sondage que le sondage quadratique.

Mais cela se fait au prix d’un temps d’exécution plus lent (dû au calcul de h’(x)) par sondage.
⇒ En pratique, il n’y a pas toujours un gain de performance.

Question 29

Une bonne fonction de hachage, en pratique..

Answer 29

En fait, il existe toujours plusieurs séquences de clés qui ont la propriété de hacher toutes vers le même index.

• Donc, toute fonction h possède ce cas le plus défavorable qui produira un temps d’exécution en Θ(n) pour les recherches, insertions et suppressions.
• Peu importe la méthode utilisée pour résoudre les collisions.

Question 30

Déf : Une famille H de fonctions est dite universelle,,

Answer 30

Une famille H de fonctions hachant ses clés dans une table de N indexes est dite universelle si pour toute paire (x,y) de clés distinctes, le NOMBRE de fonctions h de H telle que h(x) = h(y) est au plus |H|/N.

Question 31

La probabilité d’avoir une collision entre deux clés distinctes données est …

Answer 31

..au plus de (|H|/N)/|H| = 1/N

Avec une distribution uniforme sur H

Question 32

Pour toute séquence de n clés hachées dans une table de N indexes et pour toute clé test x, la longueur attendue de la liste à l’entrée h(x) :

Answer 32

• est ≤ λ lorsque x n’est pas parmi les n clés,

* est ≤ 1 + λ lorsque x est parmi les n clés.

Question 33

THM (inégalité de Markov):

Answer 33

Pour toute variable aléatoire X non négative dont l’espérance E X = μ, et pour tout entier t > 0, on a: Pr(X ≥ t) ≤ μ/t.

Question 34

Quand sommes nous en situation de hachage parfait ?

Answer 34

On est en situation de hachage parfait lorsque les recherches de clés
s’effectuent en O(1) en pire cas.

Question 35

Quand le hachage parfait est il réalisable ?

Answer 35

1- lorsque la distribution des clés stockées dans la table est statique.

2- en choisissant aléatoirement notre fonction de hachage dans une famille universelle de fonctions de hachage

Question 36

Principe du hachage parfait à 2 niveaux

Answer 36

• Pour n éléments èa stocker.
• Une table primaire de n alvéoles.
• Chaque alvéoles pointent sur une table secondaire distincte de nj^2 alvéoles (nj = nombres de clés hachant en j sur la primaire)

Question 37

Hachage parfait à 2 niveaux : THM de la somme des tailles des tables secondaires

Answer 37

Si on stocke n clés dans une table de hachage primaire de taille n via une fonction de hachage tirée aléatoirement dans une classe universelle, alors l’espérance de la somme des tailles des tables secondaires sera < 2n

Question 38

Hachage parfait : Probabilité d’obtenir une fonction de hachage h (tirage d’une classe universelle) lorsque la taille de la table = n^2

Answer 38

1/2

Question 39

Hachage parfait : Si l’on stocke n clés (distinctes) dans une table de dispersion comprenant N alvéoles via une fonction de hachage choisie aléatoirement dans une classe universelle, le nombre attendu de collisions sera au plus de

Answer 39

n(n-1)/(2N)

Question 40

Exemple d’une famille universelle

Answer 40

Considérons d’abord que les clés sont des entiers non signés.
- Soit N la taille de la table (pas nécessairement un nombre premier ici).
- Soit P (avec P > N) un nombre premier assez grand, pour que toutes les
clés possibles aient une valeur comprise dans {0, 1, …, P-1}.
- Pour tout nombre a dans {1, …, P-1} et b dans {0,1, …, P-1}, soit ha,b défini
tel que pour toute clé x, on a:
- ha,b(x) = ( (a x + b) mod P ) mod N
- Comme il y a P-1 valeurs possibles pour a et P valeurs possibles pour b,
cette famille H(P,N) possède P(P-1) fonctions de hachage.

Question 41

E Ch(x,y)

Answer 41

<= 1/N