Les tables de dispersions Flashcards
Les tables de dispersions servent notamment à implémenter des …
dictionnaires
Déf : Dictionnaire
- Conteneur d’éléments, non ordonné
- Insertion, suppression, trouver presque toujours en O(1)
Que fait une fonction de hachage ?
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
Déf : Collision
Le même index est calculé pour 2 clé distinctes
Déf : Bonne fonction de hachage
doit disperser ses valeurs d’index le plus uniformément possible dans {0, 1, …, N-1}
De quoi dépend le temps d’exécution d’une fonction de hachage
- dépend seulement de la taille de la clé
- Ne dépend PAS de la taille du tableau
Bon choix de taille d’une table dispersion
Généralement un nombre premier supérieur à l’espace requis par le programme.
Une fonction de hachage est composée
- 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
Pourquoi le hachage polynomial est-il pertinent ?
Obtenir une meilleure dispersion en tenant compte de la position des caractères de la clé dans le calcul du hachage.
Avantages et Désavantages du chaînage externe
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
Principe du chaînage externe
- On utilise un tableau de listes
- Chaque liste contient les clés qui hachent
à la même valeur d’index
(Voir schéma P18)
Comment calcule-t-on le taux d’occupation de la table de dispersion (λ)
λ = n / N
N : taille de la table
n : nombre d’éléments
Dans le cas du hachage externe pourquoi re-hacher dès que taux d’occupation devient plus grand que 1
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.
Le coût général du re-hachage (cas chaînage externe)
Θ(n+N) = Θ(n)
Car n = N+1
Le coût PAR ÉLÉMENT du re-hachage (cas chaînage externe)
O(1)
Adressage Ouvert : Structure de données
- 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
Adressage Ouvert : Calcul de l’index d’une valeur
- 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”
Adressage Ouvert : comment fonctionne trouverPosition(x)
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).
Adressage Ouvert : taux d’occupation λ maximum
λ = 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
Principe du sondage linéaire
f(i) = i
Alors hi(x) = (h(x) + i) Mod N
Problème du sondage linéaire
- Formation de regroupements primaires
- ceux ci provoquent de très longe séquences de sondages
Principe du Sondage Quadratique
f(i) = i²
Alors hi(x) = (h(x) + i²) Mod N
Théorème Sondage Quadratique
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.
Le sondage quadratique : Onest assuré de pouvoir insérer une clé si
- Table à moitier vide
- Taille est un nombre premier
Preuve du Théorème du Sondage Quadratique
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
Principe du double hachage
f(i) = i * h’(x)
hi(x) = ( h(x) + f(i) ) mod N
h’(x) ne doit jamais être = 0
Double hachage : fonction fréquente h’(x) =
h’(x) = R - c(x) mod R
Où R est un nombre premier plus petit que N
Double hachage vs sondage quadratique
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.
Une bonne fonction de hachage, en pratique..
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.
Déf : Une famille H de fonctions est dite universelle,,
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.
La probabilité d’avoir une collision entre deux clés distinctes données est …
..au plus de (|H|/N)/|H| = 1/N
Avec une distribution uniforme sur H
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) :
- est ≤ λ lorsque x n’est pas parmi les n clés,
* est ≤ 1 + λ lorsque x est parmi les n clés.
THM (inégalité de Markov):
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.
Quand sommes nous en situation de hachage parfait ?
On est en situation de hachage parfait lorsque les recherches de clés
s’effectuent en O(1) en pire cas.
Quand le hachage parfait est il réalisable ?
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
Principe du hachage parfait à 2 niveaux
- 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)
Hachage parfait à 2 niveaux : THM de la somme des tailles des tables secondaires
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
Hachage parfait : Probabilité d’obtenir une fonction de hachage h (tirage d’une classe universelle) lorsque la taille de la table = n^2
1/2
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
n(n-1)/(2N)
Exemple d’une famille universelle
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.
E Ch(x,y)
<= 1/N
