[PDF] Hachage du coucou Jan 26 2009 satellites qui

View - Download Hachage du coucou

Previous PDF

Next PDF

Hachage du coucou

StéphaneCaron

26 janvier 2009

1 Introduction

Ledictionnaireest un modèle de structure de données fondamental en informa- tique. On l"utilise pour maintenir un ensembleEformé d"éléments (appelésclefs) issus d"un universU. Sur cet ensembleE, on doit pouvoir répondre de manière efficace à la requête d"appartenance2:UE! f0;1g. De plus, dans le cas où la clefx2E, on souhaite également stocker et récupérer des données dites " satellites »s(x)avecx. Un dictionnaire de la langue française est, à juste titre, un exemple de dic- tionnaire. L"universUest alors l"ensemble des chaînes de caractères latins, tandis que les clefs deEsont les mots français. Chaque clef est accompagnée de données satellites qui correspondent à la définition du mot concerné. La nécessité de manipuler des structures de type dictionnaire en informatique a entraîné la conception des structures de données que sont lestables de hachage. Celles-ci implémentent les opérations primitives d"insertion, de recherche et de suppression dans un ensembleE. Toutefois, les performances respectives de ces différentes opérations dépendent généralement de la technique de hachage utilisée. Nous nous intéresserons ici à l"implémentation d"une méthode de hachage simple et efficace : lehachage cuculidé(Cuckoo Hashingen anglais). Il s"agit d"une approche gloutonne qui garantit des opérations de recherche et de suppres- sion enO(1), ainsi qu"une insertion en temps amortiO(1). Notations.On notera?la cellule vide et$l"échange de deux éléments. 1

2 Description de la méthode

2.1 Recherche

On se donne deux tables de hachageT1etT2munies de deux fonctions de hachage h

1eth2. Une clefxsera enregistrée soit enT1[h1(x)], soit enT2[h2(x)]. Ainsi, la

fonction de recherche est particulièrement simple :Algorithm 1Rechercher(x)retournerT1[h1(x)] =x_T2[h2(x)] =x2.2 Suppression

De même que la recherche, la suppression d"une clefxest, dans ce cadre, une

opération triviale : il suffit de vider la cellule adéquate parmiT1[h1(x)]etT2[h2(x)].Algorithm 2Supprimer(x)siT1[h1(x)] =xalors

T

1[h1(x)] ?

sinon siT2[h2(x)] =xalors T

2[h2(x)] ?

fin si2.3 Insertion On l"aura compris, le coeur de l"algorithme de hachage réside dans la procédure d"insertion. Le hachage du coucou suit alors une approche gloutonne : si l"un des deux emplacements possibles pour la clefxest libre, on l"y insère; sinon, on " déloge » la clefystockée enT1[h1(x)]pour y insérerx. Notre clefyse retrouvant alors " sans domicile », on l"insère dans l"autre table en délogeant une autre clefz éventuelle, et on itère le processus jusqu"à trouver un emplacement libre. Il est toutefois possible que ce processus engendre une boucle infinie, p. ex. dans le cas où une clef insérée au cours du traitement se trouve délogée par la suite (voir le cas (b) de la figure 1). Pour cette raison, on se fixe une borneM sur le nombre maximum de permutations à effectuer : si aprèsMitérations on dispose toujours d"une clef non-insérée, un ré-hachage est nécessaire, c.-à.-d. qu"il 2 faut choisir une nouvelle fonction de hachage et/ou modifier la taille des tables avant de tenter une nouvelle insertion.8PAGHANDRODLER y z v x T2T1 v z y x T2T1 x y z u v st T1T2 (a)(b) FIG.1.ExamplesofCuckooHashinginsertion.Arrowsshowpossibili tiesfor movingkeys.(a)Key xissucc essfullyinsertedbymovingkeysyandzfromonetabl e totheo ther.(b) Keyxcannotbeaccommodat edanda rehashisnecessary.

Thiske yistheninsert edin T

2 int hesamewa y,andsofor thiteratively,s ee Figure1(a). Itmayhappenthatthisproc ess loops,a sshowninFigur e1(b). Thereforethenumberofitera tionsisbo undedbyavalue"MaxLoop"tobe specifiedinSection4.1.Ift hisnum berofiterationsisr eached,ever ythingis rehashedwithnewhashfunctions ,andwet ryonce againtoacc ommodate thenestle sskey. Usingthenotat ionx↔ytoexpre ssthatthevaluesofvaria blesxandy areswappe d,thefollowingcodesummarizesthe insertion procedure. procedureinsert(x) iflookup(x)thenretur n loopMaxLooptimes ifT 1 [h 1 (x)]=?then{T 1 [h 1 (x)]←x;return} x↔T 1 [h 1 (x)] ifT 2 [h 2 (x)]=?then{T 2 [h 2 (x)]←x;return} x↔T 2 [h 2 (x)] endloop rehash();insert(x) end Thea boveprocedureassumes thateachtableremainslarg erthan(1+ ?)ncells.Whennosuch boundisknown,at est mustbedoneto find outwhenar ehashto larg ertablesisneeded.Resiz ingoftabl escanb e doneinamor tize dexpectedconstanttimepe rupdatebytheusualdou- bling/halvingtechnique(see, e.g.,[10]).Thehashfunct ionsusedwill be

(O(1),MaxLoop)-universal,whichmeansthattheywillactalmostlikeFigure1: deux cas de figure : le processus d"insertion termine (a) ou boucle (b).

Remarque.Cette pratique consistant à déloger une clef déjà présente pour in- sérer la nouvelle venue donne son nom à notre algorithme de hachage, dit " du coucou », car de nombreux oiseaux de la famille des cuculidés - tel lecoucou

gris- pondent leurs oeufs dans les nids d"autres espèces.Figure2: implémentation biologique de notre procédure d"insertion.

3

Algorithm 3Insérer(x)si:Rechercher(x)alors

pouri2J1;MKfaire x$T1[h1(x)] six=?alors retourner fin si x$T2[h2(x)] six=?alors retourner fin si fin pour

Ré-hacher()

Insérer(x)

fin si2.4 Ré-hachage Le phénomène de boucle infinie lors d"une insertion peut être dû à une fonction de hachage inadaptée et/ou à un remplissage trop important des tablesT1etT2. En effet, le facteur de remplissage du hachage du coucou à deux tables est limité à49%, d"où l"importance de l"opération de ré-hachage après une insertion infructueuse. Le ré-hachage consiste à choisir deux nouvelles fonctions de hachage et à re- construire tout le dictionnaire avec ces nouvelles fonctions. Cette opération peut

sembler très coûteuse, toutefois il a été montré en [?] que, malgré le ré-hachage

éventuel, l"insertion est de complexité amortieO(1).Algorithm 4Ré-hacher(x)Soienth01eth02deux nouvelles fonctions de hachage.

On noteT0=fT01;T02gla nouvelle table associée à ces fonctions. pourchaque clefxdeTfaire

Insérer(x)dansT0

fin pour4

3 Implémentation

Nous avons implémenté le hachage du coucou enC++dans le cas particulier où l"universUest l"ensemble des entiers non-signés sur 32 bits. La simplicité de la méthode est illustrée par la concision du code obtenu (joint en annexe). De plus, nos dictionnaires étant de taille variable et compte-tenu des causes de boucles infinies précédemment évoquées, nous avons choisi de doubler la taille des tables

à chaque ré-hachage.

Nous avons ensuite procédé à quelques tests de performances sur une machine munie d"un processorIntel Core 2 Duocadencé à 2,16 Ghz. Les résultats suivants, obtenus avec des clefs pseudo-aléatoires, suggèrent que cette méthode de hachage présente d"excellentes performances pour des dictionnaires de taille raisonnable.

çanombrende clefs10

110
210
310
410
510
610

7temps d"exécution (s)0.0040.0050.0060.0120.0620.74111.321

Dans notre implémentation de l"algorithme, les fonctions de hachage sont ins- pirées de celles proposées sur la page [?]. Nous avons par ailleurs comparé notre code à une implémentationJavadue à Lynn Monson. Enfin, nous ne saurions nier que nous avons également consulté l"article " Cuckoo hashing » de l"encyclopédie libreWikipédia. 5quotesdbs_dbs32.pdfusesText_38

[PDF] coucou salut

[PDF] coucou avion

[PDF] un coucou d'amour

[PDF] coucou chat

[PDF] patron t shirt homme gratuit

[PDF] patron couture homme pdf

[PDF] patron t shirt femme

[PDF] objet jaune éclairé lumière verte

[PDF] couleur d'un objet animation

[PDF] objet vert éclairé par lumière magenta

[PDF] objet bleu eclairé lumiere rouge

[PDF] décomposition de la lumière blanche par un prisme

[PDF] couleur spectrale

[PDF] formule semi développée indigo

[PDF] formule brute squalène