18
Chapitre 2 Structures lin´ eaires Les donn´ ees que doivent traiter les programmes informatiques sont sou- vent li´ ees par des relations qui leur conf` erent une certaine structure : dans certains jeux de cartes, on peut ˆ etre oblig´ e de d´ eposer des cartes au som- met d’un tas et n’avoir acc` es qu’` a la derni` ere carte d´ epos´ ee : on parle de structure de pile ; les processus envoy´ es ` a une imprimante doivent ˆ etre g´ er´ es de mani` ere que le premier processus envoy´ e soit le premier trait´ e : on parle de file d’attente ; les positions sur un ´ echiquier peuvent ˆ etre repr´ esent´ es par les noeuds d’un arbre dont les successeurs sont toutes les positions attei- gnables en un coup ; les noeuds d’un r´ eseau de communication peuvent ˆ etre repr´ esent´ es par les sommets d’un graphe,... Un nombre limit´ e de structures de donn´ ees reviennent dans la tr` es grande majorit´ e des traitements informatique. Les structures de donn´ ees en infor- matique jouent un peu le rˆ ole des structures abstraites en math´ ematiques, groupes, anneaux, corps, espaces vectoriels, . . . : elles sont susamment g´ e- erales pour qu’il y ait avantage ` a les ´ etudier ind´ ependamment de toute application sp´ ecifique. On peut par exemple ´ etudier la question du tri d’un tableau ou de la recherche d’un chemin dans un graphe sur des structures abstraites : les algorithmes qui r´ esolvent ces probl` emes dans le cas g´ en´ eral pourront alors ˆ etre utilis´ es dans n’importe quelle situation sp´ ecifique. Les langages de programmation proposent g´ en´ eralement des types simples, quelques types plus complexes (tableaux, listes, etc) et des contructeurs de types permettant d’impl´ ementer toutes les structures de donn´ ees. On parle de structure lin´ eaire lorsque les donn´ ees sont repr´ esent´ ees s´ equen- tiellement : chaque ´ el´ ement, sauf le dernier, poss` ede un successeur. On ´ etu- diera en particulier les tableaux ` a une dimension, les listes, les piles, les files et les tables de hachage. Les matrices, les arbres et les graphes sont des 21

Structures lin´eaires - pageperso.lif.univ-mrs.frpageperso.lif.univ-mrs.fr/~francois.denis/algoL2/chap2.pdf · n´erales pour qu’il y ait avantage a les ´etudier ind´ependamment

Embed Size (px)

Citation preview

Chapitre 2

Structures lineaires

Les donnees que doivent traiter les programmes informatiques sont sou-vent liees par des relations qui leur conferent une certaine structure : danscertains jeux de cartes, on peut etre oblige de deposer des cartes au som-met d’un tas et n’avoir acces qu’a la derniere carte deposee : on parle destructure de pile ; les processus envoyes a une imprimante doivent etre geresde maniere que le premier processus envoye soit le premier traite : on parlede file d’attente ; les positions sur un echiquier peuvent etre representes parles noeuds d’un arbre dont les successeurs sont toutes les positions attei-gnables en un coup ; les noeuds d’un reseau de communication peuvent etrerepresentes par les sommets d’un graphe, . . .

Un nombre limite de structures de donnees reviennent dans la tres grandemajorite des traitements informatique. Les structures de donnees en infor-matique jouent un peu le role des structures abstraites en mathematiques,groupes, anneaux, corps, espaces vectoriels, . . . : elles sont su�samment ge-nerales pour qu’il y ait avantage a les etudier independamment de touteapplication specifique. On peut par exemple etudier la question du tri d’untableau ou de la recherche d’un chemin dans un graphe sur des structuresabstraites : les algorithmes qui resolvent ces problemes dans le cas generalpourront alors etre utilises dans n’importe quelle situation specifique.

Les langages de programmation proposent generalement des types simples,quelques types plus complexes (tableaux, listes, etc) et des contructeurs detypes permettant d’implementer toutes les structures de donnees.

On parle de structure lineaire lorsque les donnees sont representees sequen-tiellement : chaque element, sauf le dernier, possede un successeur. On etu-diera en particulier les tableaux a une dimension, les listes, les piles, les fileset les tables de hachage. Les matrices, les arbres et les graphes sont des

21

22 CHAPITRE 2. STRUCTURES LINEAIRES

v1 v2 v3 vn

v1 v2 vn

vi vi +1 vi +2 vn

Insertion après les autres éléments

Insertion dans un tableau trié

x

n+1

n

n+1

n−i recopies

x

Figure 2.1 – Insertion d’un element en fin de tableau ou a un indice donne.

structures non lineaires.

2.1 Tableaux

Un tableau (array) T est un ensemble d’elements accessibles par un indicei 2 [1 . . . n]. On suppose que l’acces au i-eme element T [i] peut etre realiseen temps constant (O(1)). En revanche, l’insertion d’un nouvel element aun indice i donne necessite de deplacer tous les elements suivants (tempslineaire dans le pire des cas). De meme la recherche d’un element dans untableau non trie se fait en temps lineaire dans le pire des cas. Nous avons vuprecedemment que la recherche d’un element dans un tableau trie pouvaitetre e↵ectuee en temps logarithmique.

Implementation des tableaux en C

/* Definition */

#define NBMAX 1000 /* nombre maximum d’elements */

typedef int ELEMENT; /* les elements du tableau */

typedef ELEMENT TABLEAU[NBMAX];

/* Declaration */

TABLEAU t;

2.2. LISTES CHAINEES 23

ou avec allocation dynamique de la memoire,

/* Definition */

typedef ELEMENT* TABLEAU;

/* Declaration */

TABLEAU t;

int nb_elts=50; /* nombre d’elements du tableau */

/* Allocation */

t=malloc(nb_elts*sizeof(ELEMENT));

2.2 Listes chaınees

Une liste chaınee (linked list) est une structure lineaire, composee demaillons, chaque maillon comprenant un champ valeur qui permet de stockerun element et un champ suivant qui pointe vers le maillon suivant ou estegal a NIL, s’il s’agit du dernier maillon de la liste. Une liste chainee L estun objet qui est egal a NIL si la liste est vide ou qui pointe vers un maillon,le premier de la liste, si elle est non vide.

Implementation des listes chaınees en C

/* Definition */

typedef int ELEMENT; /* par exemple */

typedef struct maillon *LISTE;

typedef struct maillon{

ELEMENT val;

LISTE suiv;

}MAILLON;

/* Declaration */

LISTE l;

/* Insertion d’un element en tete d’une liste */

24 CHAPITRE 2. STRUCTURES LINEAIRES

i+2i+1ii−1 VVVV

prec p

prec −> suiv = CreerMaillon (x, prec −> suiv);

Création et insertion d’un nouveau maillon avec la valeur x

x

Figure 2.2 – Insertion d’un element dans une liste a une place donnee.

LISTE CreerMaillon(ELEMENT elt, LISTE liste_initiale){

LISTE l;

l=malloc(sizeof(MAILLON)); /* allocation memoire pour un maillon */

l->val=elt;

l->suiv=liste_initiale;

return l;

}

On voit que l’insertion d’un element en tete de liste se fait en tempsconstant.

Le traitement des listes chaınees requiert de pouvoir :— inserer un element en queue de liste,— rechercher si un element est present dans la liste,— supprimer la premiere occurrence d’un element,— inserer un element dans une liste ordonnee,— trier une liste,— vider une liste de ses elements.

Exercice 1

1. Quelle est la complexite dans le pire des cas des algorithmes prece-dents ?

2. Programmez-les en C.

2.2. LISTES CHAINEES 25

Ameliorations de la structure de liste chaınee Il n’est pas possibled’acceder directement au maillon precedent le maillon courant d’une listechaınee. Cela complique notamment l’ecriture de l’algorithme de suppres-sion d’un maillon. Pour remedier a ce defaut, on considere des listes double-ment chaınees dans lesquels les maillons comprennent egalement un champprecedent qui pointe vers le maillon precedent ou est egal a NIL, s’il s’agitdu premier maillon de la liste.

Par ailleurs, les algorithmes de traitement des listes chaınees sont alourdispar le fait qu’il faut traiter di↵eremment le premier maillon, qui n’a pas demaillon precedent, des maillons suivants. Pour remedier a cela, on introduitun maillon vide, dont le champ val prend une valeur quelconque, et quiconstituera le premier maillon de la liste chaınee.

Mais le meme probleme se pose alors pour le dernier maillon, qui n’admetpas de maillon suivant. On suppose alors que le champ suivant du derniermaillon pointe circulairement sur le maillon vide et que le champ precedentdu maillon vide pointe vers le dernier maillon. A l’initialisation (liste vide),les champs suivant et precedent du maillon vide pointent vers lui-meme.

On obtient ainsi la notion de liste doublement chaınee circulaire avecmaillon vide (circular, doubly linked list, with a sentinel).

Implementation en C

typedef int ELEMENT; /* pour une liste d’entiers */

typedef struct maillon *LISTE;

typedef struct maillon{

ELEMENT val;

LISTE suiv;

LISTE prec;

}MAILLON;

Le tableau 2.4 compare la complexite de quelques operations elementairessur des tableaux et des listes chaınees.

Exercice 2 Ecrire les algorithmes de traitement des listes doublement chaı-nees circulaires avec maillon vide.

Exercice 3 On represente un polynome a coe�cients entiers par une listechainee dont les maillons possedent un champ coefficient et un champexposant ; on suppose de plus que les listes sont ordonnees par valeurs

26 CHAPITRE 2. STRUCTURES LINEAIRES

liste

v1 v2 v3bidon

Figure 2.3 – Liste doublement chaınee circulaire avec maillon vide.

Operation Tableau Tableau Liste Liste Liste Listetrie ordonnee doublement ordonnee

chaınee doublementchaınee

acces i-eme element ⇥(1) ⇥(1) ⇥(n) ⇥(n) ⇥(n) ⇥(n)insertion a une ⇥(n) ⇥(n) ⇥(1) ⇥(1) ⇥(1) ⇥(1)place donnee

recherche element ⇥(n) ⇥(log2

n) ⇥(n) ⇥(n) ⇥(n) ⇥(n)recherche succ. ⇥(1) ⇥(1) ⇥(1) ⇥(1) ⇥(1) ⇥(1)

recherche pred. ⇥(1) ⇥(1) ⇥(n) ⇥(n) ⇥(1) ⇥(1)

recherche maximum ⇥(n) ⇥(1) ⇥(n) ⇥(n) ⇥(n) ⇥(1)

recherche minimum ⇥(n) ⇥(1) ⇥(n) ⇥(1) ⇥(n) ⇥(1)

Figure 2.4 – Comparatif tableaux / listes chaınees.

2.3. PILES ET FILES 27

croissantes d’exposant. Implementez cette structure de donnees en C et pro-grammez les fonctions suivantes :

— int degre(POLYNOME p)

— void affiche(POLYNOME p)

— POLYNOME somme(POLYNOME p1, POLYNOME p2)

— POLYNOME multiplication_scalaire(POLYNOME p, int a)

— POLYNOME multiplication(POLYNOME p1, POLYNOME p2)

— POLYNOME derivee(POLYNOME p)

— float eval(POLYNOME p, float x)

2.3 Piles et files

Les piles (stack) et les files (queues) sont des structures lineaires quidi↵erent par la maniere dont les elements sont inseres et supprimes : dansune pile, le dernier element entre est le premier sorti (Last In First Out :LIFO) ; dans une file, le premier element entre est le premier sorti (First InFirst Out : FIFO).

Trois fonctions (ou operations) su�sent a faire fonctionner une pile :— la fonction booleenne pileVide ?(P) (StackEmpty(P)) qui retourne

VRAI si la pile P est vide et FAUX sinon,— la fonction empiler(P,x) (Push(P,x)) qui insere un element x dans la

pile P ,— la fonction depiler(P) (Pop(P)) qui retourne le dernier element insere

ou un message d’erreur si la pile est vide.

De meme, trois fonctions (ou operations) su�sent a faire fonctionner unefile :

— la fonction booleenne fileVide ?(F) (QueueEmpty(F)) qui retourneVRAI si la file F est vide et FAUX sinon,

— la fonction enfiler(F,x) (EnQueue(F,x)) qui insere un element x dansla file F ,

— la fonction defiler(F) (DeQueue(F)) qui retourne le premier elementinsere ou un message d’erreur si la file est vide.

Toute implementation d’une pile ou d’une file necessite l’implementationdes fonctions correspondantes.

Implementation d’une pile par un tableau. Une pile peut etre re-presentee par les premiers elements d’un tableau de taille fixe et par unentier indiquant l’indice du dernier element insere. La dimension du tableau

28 CHAPITRE 2. STRUCTURES LINEAIRES

etant fixee, il est necessaire d’implementer aussi une fonction booleenne Pi-lePleine ? qui indiquera si la pile est pleine ou non. En C, cela peut seprogrammer de la facon suivante :

/* Declarations */

#define TAILLE_MAX 1000 // Nombre maximal d’elements dans la pile

typedef int ELEMENT; /* pour une pile d’entiers */

typedef struct {

ELEMENT elts[TAILLE_MAX];

int nbElts;} // nombre d’elements de la pile

PILE;

PILE p;

/* Initialisation */

void initPile(PILE *p){

p->nbElts=0;

}

/* retourne 1 si la pile p est vide, 0 sinon */

char pileVide(PILE p){

return (p.nbElts==0);

}

/* retourne 1 si la pile p est pleine, 0 sinon */

char pilePleine(PILE p){

return (p.nbElts==TAILLE_MAX);

}

/* empile l’element x sur la pile p, si celle-ci n’est pas pleine */

void empiler(PILE *p, ELEMENT x){

assert(!pilePleine(*p));

p->elts[p->nbElts++]=x;

}

/* retourne l’element x au sommet de la pile p, si celle-ci n’est pas vide */

ELEMENT depiler(PILE *p){

2.3. PILES ET FILES 29

assert(!pileVide(*p));

return p->elts[--p->nbElts];

}

Implementation d’une file par un tableau. Une file peut etre repre-sentee par les elements d’un tableau de taille fixe N et par deux entiersindiquant l’indice du premier element insere et le nombre total d’elementsinseres. Pour que la file puisse toujours contenir jusqu’a N elements, il esthabituel de supposer que le tableau est circulaire, c’est-a-dire que la premierecase suit la derniere.

/* Declarations */

#define TAILLE_MAX 1000 // Nombre maximal d’elements dans la file

typedef int ELEMENT; /* pour une file d’entiers */

typedef struct {

ELEMENT elts[TAILLE_MAX];

int indPremierElt; // indice du premier element

int nbElts; // nombre d’elements

} FILE;

FILE f;

La dimension du tableau etant fixee, il est necessaire d’implementer unefonction booleenne FilePleine ? qui indiquera si la file est pleine ou non. Poursavoir ou un nouvel element doit etre insere, il est necessaire d’e↵ectuer uncalcul, modulo le nombre de cases du tableau : pour un tableau indexe de0 a N � 1, si le premier element a pour indice N � 2 et si la file contient 5elements, le prochain element insere occupera la case 3 = N � 2 + 5modN(voir TD).

Exercice 4 Codez la structure de file en utilisant un tableau de taillefixe et deux entiers indiquant l’indice du premier element et le nombre totald’elements de la file (comme ci-dessus).

Vous coderez les primitives : fileVide, filePleine, defiler, et enfiler.

30 CHAPITRE 2. STRUCTURES LINEAIRES

Exercice 5 Utilisez une structure de liste doublement chaınee avec maillonvide pour coder les structures pile et de file.

Exercice 6 La notation post-fixee des expressions arithmetiques, appeleeencore notation polonaise inversee, consiste a ecrire les operandes avant lesoperateurs. L’expression ((3+(5⇥4)⇥2) s’ecrira par exemple 3 5 4 ⇥ + 2 ⇥.Aucune parenthese n’est necessaire et l’evaluation d’une telle expression sefait simplement au moyen de l’algorithme suivant :

— les termes sont parcourus de gauche a droite ;— si le terme courant est un nombre, il est empile ;— si le terme courant est un operateur, les deux derniers nombres empi-

les sont depiles, l’operateur leur est applique et le resultat est empile ;— lorsque l’expression est totalement parcourue, la pile ne contient plus

qu’un seul element : le resultat de l’evaluation.

Ecrivez un programme qui evalue une expression a partir de sa notationpost-fixee (on supposera, pour simplifier, que les operandes sont comprisentre 0 et 9).

Exercice 7 Etant donne un tableau T de n elements, on veut savoirs’il existe un element majoritaire, c’est-a-dire un element dont le nombred’occurrences k est strictement superieur a n/2, et dans ce cas, le determiner.

L’algorithme naıf qui consiste a verifier pour chaque element du tableaus’il est majoritaire a une complexite quadratique dans le nombre n d’ele-ments. L’algorithme recursif etudie au TD1 et base sur le principe diviserpour regner a une complexite en n log n. Nous etudions ici un troisieme al-gorithme.

2.3. PILES ET FILES 31

Algorithme 10: rechEltMajoritaire

entree : T [1, n] est un tableau d’entiers positifs ou nuls et n � 1.sortie : x, si x est majoritaire dans T et -1 sinon.debut

# on utilise 2 autres tableaux T1 et T2

T1[1] := T [1], i := 1 # indice de l’element courant dans T1

j := 0 # indice de l’element courant dans T2

pour k := 2 a n faire# l’objectif est de remplir T1 en alternant les valeurssi T [k] 6= T1[i] alors

T1[i+ 1] := T [k], i := i+ 1 # insertion dans T1

sinonsi j = 0 alors

T2[j + 1] := T [k], j := j + 1 # T2 est vide - on y inserel’element courant

sinonsi T2[j] 6= T [k] alors

T1[i+ 1] := T2[j], T1[i+ 2] := T [k], i := i+ 2, j := j � 1# on peut inserer deux elements dans T1

sinonT2[j + 1] := T [k], j := j + 1 # insertion de l’elementcourant dans T2

si j � 1 alorsx := T2[1] # premier element de T2

sinonx := T1[1] # premier element de T1

si x est majoritaire dans T alorsretourner x

sinonretourner -1

1. Montrez qu’au cours de l’execution de l’algorithme, si T2

n’est pasvide, il ne contient que des elements ayant la meme valeur.

2. Montrez que T1

ne contient pas deux elements consecutifs de memevaleur.

3. Montrez que T1

ne peut contenir au maximum que dn/2e elementsidentiques.

4. Supposons que T a un element majoritaire x.

(a) Montrez que si T2

est non vide a la fin de l’algorithme, alors tousles elements de T

2

ont pour valeur x.

(b) Montrez que si T2

est vide a la fin de l’algorithme, alors n estimpair et T

1

[1] = T1

[n] = x.

32 CHAPITRE 2. STRUCTURES LINEAIRES

5. Montrez la correction de l’algorithme.

6. Quel est sa complexite ? Trouvez un majorant du nombre de compa-raisons e↵ectuees dans le pire des cas.

2.4 Tables de hachage

Les dictionnaires ou tableaux associatifs sont des structures de donneescomposees d’elements de la forme (cle,valeur) ou chaque cle determine auplus une valeur.

On peut par exemple considerer le dictionnaire compose du numero d’unetudiant inscrit a l’universite d’Aix-Marseille et de son dossier, le diction-naire compose d’un numero de securite sociale et de l’assure correspondantou du dictionnaire compose des mots du francais et de leur definition.

Les operations de base associees a un dictionnaire sont : l’insertion d’unnouvel element, la recherche d’un element et la suppression d’un element.Lorsque les cles sont des entiers appartenant a l’intervalle [0 . . . n � 1] (onpeut toujours se ramener a ce cas) et lorsque n n’est pas trop grand, lesdictionnaires peuvent etre implementes par des tableaux T a adressage di-rect dans lesquels les cles ne correspondant a aucune valeur sont associeesconventionnellement a une valeur NIL : en e↵et, inserer un element (c, x),rechercher si element x de cle c est present ou supprimer l’element (c, x) sefait en temps constant. Mais le cas le plus frequent est celui ou le nombrede valeurs renseignees est tres petit par rapport a n : voir les exemples citesprecedemment.

Si l’on represente les n elements par une liste chaınee, chaque opera-tion de base s’e↵ectue en temps lineaire (par rapport a n) : on souhaiteraitpouvoir les realiser en temps constant.

Les tables de hachage (hash tables) sont des structures de donnees quigeneralisent les tableaux au cas ou l’ensemble U des cles possibles est gigan-tesque par rapport au nombre de valeurs a stocker. L’idee de base consistea introduire une fonction de hachage

h : U 7! [0 . . .m� 1]

telle que m soit de l’ordre du nombre de valeurs a stocker et telle qu’en pra-tique, le nombre de collisions, c’est-a-dire le nombre de cas ou deux elementsdistincts du dictionnaire (c, x) et (c0, x0) verifient h(c) = h(c0) soit le pluspetit possible. Si l’on pouvait assurer qu’il n’y a pas de collisions, on pourrait

2.4. TABLES DE HACHAGE 33

0

1

2

3

4

5

table

e3 e7 e2

h(clé(e3)) = h(clé(e7)) = h(clé(2))

liste des objets

Figure 2.5 – Gestion des collisions par chaınage externe.

implementer le dictionnaire par un tableau T , chaque element (c, x) etantrepresente par l’element T (h(c)). Mais il est en general impossible d’evitertoute collision.

Deux questions doivent etre donc resolues :

1. comment gerer les collisions ?

2. comment definir une fonction de hachage minimisant le nombre decollisions ?

2.4.1 Gestion des collisions par chaınage externe

On appelle h(c) la position de l’element (c, x). Une collision corresponddonc a deux elements du dictionnaire possedant la meme position. On choisitde representer les elements ayant la meme position par une liste (simplementou doublement) chaınee : T [i] pointe alors vers les elements dont la positionest i. Inserer, supprimer ou rechercher un element (c, x) est realise par lesoperations correspondantes dans la liste chaınee T (h(c)).

Le pire des cas est celui ou tous les elements du dictionnaire occupent lameme position ! Dans ce cas, on est ramene au cas du stockage du diction-naire dans une liste chaınee et les operations de base s’e↵ectuent en tempslineaire. Mais si les cles se repartissent a peu pres equitablement entre lesdi↵erentes positions et si le nombre de positions est de l’ordre du nombred’elements a stocker, le nombre d’elements de chaque liste chaınee est bornepar une constante et les operations de base peuvent donc etre realisees en

34 CHAPITRE 2. STRUCTURES LINEAIRES

temps constant. Voir ci-dessous les algorithmes d’insertion et de recherched’un element.

Algorithme 11: insertionTableHachageentree : Table de Hachage T , element e de cle cresultat : e est insere dans Tdebut

Inserer e en tete de la liste chainee T (h(c)).fin

Fonction rechercheTableHachage(T ,c)

entree : Table de Hachage T , cle csortie : un pointeur vers l’element de cle c ou NIL si l’element est

absentdebut

p = T [h(c)]tant que p 6= NIL ET p ne pointe pas vers l’element de cle cfaire

p p.suivfintqretourner p

fin

2.4.2 Gestion des collisions par adressage ouvert

La gestion des collisions par adressage ouvert consiste a utiliser la tablede hachage elle-meme pour stocker les elements. Pour cela, on utilise unefonction de hachage modifiee

h : U ⇥ [0 . . .m� 1] 7! [0 . . .m� 1]

telle que pour toute cle c, h(c, 0), . . . , h(c,m� 1) realise une permutation de[0 . . .m� 1].

Pour inserer un nouvel un element e de cle c, on cherche le premier indicei tel que T [h(c, i)] soit libre et on insere e dans T [h(c, i)] : toutes les casesdu tableau peuvent donc potentiellement recevoir tous les elements.

Pour savoir si un element de cle c est present dans T , on parcourt leselements de la liste T [h(c, 0)], . . . , T [h(c,m�1)] jusqu’a le trouver ou tombersur une case libre ou avoir parcouru toutes les cases du tableau.

En revanche, la suppression d’un element est plus complexe car il nesu�t pas de vider la case qui le contient. En e↵et, supposons

2.4. TABLES DE HACHAGE 35

— que l’element de cle c soit stocke dans la case d’indice h(c, i),— que l’element de cle c0 ait ete stocke posterieurement a l’element de

cle c dans la case d’indice h(c0, i0),— qu’il existe un indice j < i0 tel que h(c0, j) = h(c, i).Si on libere simplement la case T (h(c, i)), l’element de cle c0 ne sera plus

trouve. Une solution consiste a distinguer les cases libres des cases suppri-mees, dans lesquelles de nouvelles valeurs pourront etre inserees mais qui nedevront pas etre considerees comme libres lors d’une recherche d’element.D’apres l’ouvrage de reference, la gestion des collisions par chaınage externeest plus souvent utilisee lorsqu’il doit y avoir des suppressions.

2.4.3 Fonctions de hachage

Une bonne fonction de hachage doit satisfaire la condition suivante : lescles des elements du dictionnaire doivent se repartir (a peu pres) uniforme-ment entre les di↵erentes positions.

Des informations sur la distribution des cles peuvent permettre de definirune fonction de hachage optimale. C’est par exemple le cas lorsqu’on sait queles cles sont des nombres reels independamment et uniformement distribuesdans l’intervalle [0, 1[, on peut utiliser la fonction h(c) = bmcc.

En l’absence d’information, on cherche a definir des fonctions de ha-chage dependant le moins possible des donnees. On decrit ci-dessous deuxmethodes courantes lorsque les cles sont des entiers, cas auquel on peuttoujours se ramener.

Methode par division On definit

h(c) = c mod m.

La position de la cle c est son reste dans la division parm. C’est une methodesimple qui peut donner des resultats peu satisfaisants pour certaines valeursde m. Par exemple, si m = 2p est une puissance de 2, la position d’une clene depend que de ses p derniers bits ; si ceux-ci ne sont pas uniformementrepartis, la fonction de hachage correspondante ne sera pas uniforme nonplus.

En pratique, on recommande de choisir pour m un nombre premier pastrop proche d’une puissance de 2.

Methode par multiplication On definit

h(c) = bm{cA}c

36 CHAPITRE 2. STRUCTURES LINEAIRES

ou A est un nombre reel tel que 0 < A < 1 et ou {x} designe la partiefractionnaire de x, c’est-a-dire x� bxc.

Cette methode est plus robuste que la precedente au choix des valeurs deA et m. On choisit souvent m egal a une puissance de 2 et Donald Knuth 1

suggere de prendre A = (p5� 1)/2 (cite dans l’ouvrage de reference).

On peut toujours trouver des exemples qui mettent en defaut n’importequelle fonction de hachage, c’est-a-dire tels que presque toutes les cles seretrouvent assignees une position unique. On peut remedier a ce problemeen introduisant des fonctions de hachage randomisees, mais ces techniquesdepassent le niveau de ce cours.

Les techniques precedentes ne concernent que les methodes de hachagepar chaınage externe. Si l’on souhaite gerer les collisions par adressage ou-vert, on doit definir des fonctions de hachage a deux arguments. Les me-thodes le plus couramment utilisees sont :

le sondage lineaire (linear probing) : a partir d’une fonction de ha-chage simple h : U 7! [0 . . .m�1], on definit la fonction h0 : U⇥[0 . . .m�1] 7![0 . . .m� 1] par

h0(c, i) = h(c) + i mod m.

On verifie aisement que pour c fixee, h0(c, i) parcourt toutes les valeurs de[0 . . .m� 1] lors que i decrit [0 . . .m� 1].

L’inconvenient principal de cette fonction est qu’elle a tendance a creerde longues suites consecutives de positions occupees, ce qui a pour e↵et deralentir le temps moyen de recherche d’un element. Un moyen de remediera cela est de considerer des increments qui ne soient pas constants.

le sondage quadratique (quadratic probing) : a partir d’une fonctionde hachage simple h : U 7! [0 . . .m � 1], on definit la fonction h0 : U ⇥[0 . . .m� 1] 7! [0 . . .m� 1] par

h0(c, i) = h(c) + ai+ bi2 mod m

ou a et b sont des constantes auxiliaires. Voir dans un exercice ci-dessous unexemple de choix de ces constantes lorsque m est une puissance de 2.

1. Donald Knuth est l’un des principaux pionniers en algorithmique et son livre The

art of computer programming reste une reference majeure.

2.4. TABLES DE HACHAGE 37

double hachage (double probing) : a partir de deux fonctions dehachage simples h

1

, h2

: U 7! [0 . . .m � 1], on definit la fonction h0 :U ⇥ [0 . . .m� 1] 7! [0 . . .m� 1] par

h0(c, i) = h1

(c) + ih2

(c) mod m.

Pour que h0(c, i) realise une permutation de [0 . . .m� 1] pour toute positionh(c), il est necessaire que h

2

(c) soit premier avec m. C’est toujours le cas sim est une puissance de 2 et si h

2

ne prend que des valeurs impaires, ou sim est premier et si h

2

ne prend que des valeurs < m. On peut prendre parexemple

h1

(c) = c mod m et h2

(c) = 1 + (c mod m� 1)

ou m est premier.La methode de double hachage est consideree comme l’une des meilleures.

Exercice 8 On considere l’ensemble des mots construits sur l’alphabetlatin (26 lettres) et l’on definit la fonction de hachage suivante :

h(c0

c1

. . . ck

) = (c0

+ 26c1

+ . . .+ 26kck

) mod m

ou les lettres ci

sont identifiees a leur numero 2 {0 . . . 25} et ou m est unentier bien choisi.

1. Que se passe t-il si l’on prend m = 26 ?

2. Montrez que si m = 25, tous les anagrammes ont la meme position.

3. Proposez une methode algorithmique pour calculer pratiquement laposition d’un mot quelconque et programmez-la. Indication : pour0 i k, on pose R

i

= ci

+ 26ci+1

+ · · · + 26k�ick

. On a Ri

=ci

+ 26Ri+1

et Rk

= ck

. Montrez que si a, b, c sont des entiers, a+ bcmod m = a+b(c mod m) mod m. En deduire que l’on peut calculerh(c

0

c1

. . . ck

) sans avoir a calculer de trop grands nombres.

Exercice 9 Sondage quadratique. Montrez que si m = 2p, et si a = b = 1/2,h(c) + ai + bi2 mod m realise une permutation de [0 . . .m � 1] quelle quesoit la valeur de h(c).

Exercice 10 Etudiez les valeurs prise par la fonction de double hachageproposee ci-dessus pour m = 11.

38 CHAPITRE 2. STRUCTURES LINEAIRES