Définition 9.1. Soit K un ensemble de valeurs et m un entier naturel, une fonction de hachage hm est une fonction définie de K dans {0,...,m-1}.Les éléments de K sont appelées clés. Si k est une clé, h(k) est dite valeur de hachage de k.
Définition 9.2. Soit m un entier naturel et hm une fonction de hachage, une table de hachage est un containeur tel queRemarques
- le nombre d'éléments de la table (dimension ou taille) est fixe,
- l'accès aux éléments s'effectue indirectement par la valeur de hachage de la clé.
fonction chercher(ref T:tableHash de clés,
val v:clé):curseur;
fonction créerTableHachage(ref T: tableHash de clé,
ref h:fonction):vide;
fonction ajouter(ref T:tableHash de clé,val x:clé):booleen;
fonction supprimer((ref T:tableHash de clé,val x:clé):vide;




Definition 9.3. Soit H un ensemble de fonction de hachage de U dans [0..m[. On dit que la famille H est universelle si pour toutes clés k1, k2 dans U, le nombre de fonctions h de H telles que h(k1)=h(k2) est égal à card(H)/m.Soit m un entier naturel. Soit p un nombre premier grand tel que




Theorem 9.4. La famille de fonctionDe ce fait, On peut montrer que l'exécution de n primitives a une complexité moyenne en O(n).est universelle.
Definition 9.5. L'adressage d'une table de hashage est dit chainé si l'élements i du tableau donne accès à une structure de données permettant de stocker les clés k telles que hm(k)=i.Les valeurs sont donc stockées à l'extérieur de la table qui est un tableau de pointeurs. Par suite, si il n'existe pas de clé k telle que hm (k)=i alors T[i]=NIL.
tableHash de clé=structure
table:tableau[0..m-1] de listeDC de clé;
h:fonction(val v:clé):entier
finstructure
fonction chercher(ref T:tableHash de clé,
val e:entier):curseur;
début
retourner(chercher(T.table[T.h(e)],e))
fin
fonction créerTableHach(ref T: tableHash de clé,
ref h:fonction):vide;
var i:entier;
début
pour i allant de 0 à m-1 faire
creerListe(T.table[i])
finpour
T.h=h;
fin
fonction ajouter(ref T:tableHash de clé,val e:entier):booleen;
début
insererEnTete(T.table[T.h(e)],e);
retourner(vrai):
fin
fonction supprimer(ref T:tableHash de clé,val e:entier):vide;
début
supprimer(T.table[T.h(e)],e))
fin
Théorème 9.6. Dans une table de hashage à adressage chainé, une recherche fructueuse ou infructueuse prend en moyenne O(1+n/m) si chaque élément à les mêmes chances d'être haché vers l'une quelconque des cases indépendamment des autres éléments (hachage uniforme).
Definition 9.7. L'adressage d'une table de hashage est dit ouvert si les élements du tableau sont les clés elles mêmes.Les éléments de la table sont donc initialisés à NULL. La gestion de la collision se fait en trouvant une place libre dans la table. Pour cela on utilise une seconde fonction s(x,i) à valeur dans [0..m] que l'on compose avec hm(k). Cette seconde fonction dite de sondage doit vérifier les propriétés suivantes :
est une permutation de la séquence (i)i=0..m-1.

tableHash de clé=structure
table:tableau[0..m-1] de clé;
h:fonction(val v:clé):entier
s:fonction(val v:clé):entier
finstructure
fonction chercher(ref T:tableHash de clé,
val e:entier):curseur;
var i:entier;
début
i=0;
tant que T.table[T.s(T.h(e),i)]!=e et i<m faire
i=i+1
fintantque
si i==m alors
retourner(NULL)
sinon
retourner(T.s(T.h(e),i))
finsi
fin
fonction créerTableHachage(ref T: tableHash de clé,
ref h:fonction(var x:entier):entier)
ref s:fonction(var x:entier):entier):vide;
var i:entier;
début
pour i allant de 0 à m-1 faire
T.table[i]=NULL;
finpour
T.h=h;
T.s=s;
fin
fonction ajouter(ref T:tableHash de clé,val e:entier):booleen;
var i:entier;
début
i=0;
tant que T.table[T.s(T.h(e),i)]!=NULL et i<m faire
i=i+1
fintantque
si i==m alors
retourner(faux)
sinon
T.table[T.s(T.h(e),i)]=e;
retourner(vrai)
finsi
fin
fonction supprimer(ref T:tableHash de clé,val e:entier):vide;
var p:curseur;
début
p=chercher(T,e);
si p!=NULL
T[p]=NULL
finsi
fin
Théorème 9.8. Etant donné une table de hachage de facteur de remplissage r, une recherche infructueuse ou l'insertion d'une clé se fait en moyenne en 1/(1-r), si chaque élément à les mêmes chances d'être haché vers l'une quelconque des cases indépendamment des autres éléments (hachage uniforme ).
Théorème 9.10. Etant donné une table de hachage de facteur de remplissage r, une recherche fructueuse se fait en moyenne en (1/r)*ln(1/(1-r)), si chaque élément à les mêmes chances d'être haché vers l'une quelconque des cases indépendamment des autres éléments (hachage uniforme ).