Hașarea cucului

Cuckoo hashing  este un algoritm pentru rezolvarea coliziunilor de valori hash într-un tabel cu un timp de preluare constant în cel mai rău caz .

Propus în 2001 [1] . Denumirea se referă la comportamentul unor specii de cuc , când puiul împinge ouăle sau alți pui din cuib; în mod similar, algoritmul oferă posibilitatea de a împinge cheia veche atunci când se introduce una nouă.

Operațiuni

Hashingul cucului este un fel de adresare deschisă în care fiecare celulă negoală a tabelului hash conține o cheie sau o pereche cheie-valoare . O funcție hash este folosită pentru a determina locația fiecărei chei, iar prezența acesteia în tabel (sau valoarea asociată acesteia) poate fi găsită examinând acea celulă din tabel. Cu toate acestea, adresarea deschisă suferă de coliziuni , care se întâmplă atunci când mai multe chei ajung în aceeași celulă. Ideea de bază a hashingului cucului este de a rezolva coliziunile folosind două funcții hash în loc de una. Aceasta oferă două poziții posibile în tabelul hash pentru fiecare cheie. Într-una dintre variantele obișnuite ale algoritmului, tabelul hash este împărțit în două tabele mai mici de dimensiuni mai mici, iar fiecare funcție hash oferă un index într-unul dintre aceste două tabele. De asemenea, este posibil să vă asigurați că ambele funcții hash sunt indexate în același tabel.

Preluarea necesită analizarea a doar două locuri în tabelul hash, necesitând timp constant în cel mai rău caz ( vezi „o” mare și „o” mic ). Acest lucru este în contrast cu mulți alți algoritmi de tabel hash care nu oferă timpi de preluare constant în cel mai rău caz. Îndepărtarea se poate face și prin ștergerea celulei care conține cheia în timp constant în cel mai rău caz, ceea ce este mai ușor decât în ​​alte scheme, cum ar fi sondarea liniară .

Când se introduce o nouă cheie și una dintre cele două celule este goală, cheia poate fi plasată în acea celulă. În cazul în care ambele celule sunt ocupate, este necesar să mutați alte chei în alte locuri (sau, dimpotrivă, în locurile lor anterioare) pentru a face loc unei noi chei. Se folosește un algoritm lacom  - cheia este plasată într-una dintre pozițiile posibile, „împingând” orice cheie care se afla în această poziție. Cheia scoasă este apoi plasată în poziția sa alternativă, ejectând din nou orice cheie care ar fi putut fi acolo. Procesul continuă până când este găsită o poziție goală. Este posibil, totuși, ca procesul de inserare să eșueze, intrând într-o buclă infinită sau când lanțul este prea lung (mai lung decât un prag predeterminat care depinde logaritmic de lungimea tabelului). În acest caz, tabelul hash este reconstruit în locul cu noi funcții hash :

Nu este nevoie să configurați o nouă tabelă pentru rehashing - putem pur și simplu să trecem prin tabel pentru a șterge și a reintroduce toate cheile care nu sunt în poziția în care ar trebui să fie. [unu]Pagh și Rodler, „Cuckoo Hashing”

Complexitate computațională

Timpul de inserare așteptat este constant [1] , chiar și ținând cont de posibila necesitate de a reconstrui tabelul, atâta timp cât numărul de chei este mai mic de jumătate din capacitatea tabelului hash, adică factorul de încărcare este mai putin de 50%.

Pentru a asigura acest lucru, este utilizată teoria graficelor aleatoare  - puteți forma un grafic nedirecționat , numit „graf cuc”, în care vârfurile sunt celulele tabelului hash, iar marginile pentru fiecare hashable conectează două poziții posibile (celule ale tabel hash). Apoi algoritmul lacom pentru inserarea unui set de valori într-un tabel hash cuc reușește dacă și numai dacă graficul cuc pentru acest set de valori este o pseudopădure , un grafic cu cel mult un ciclu în fiecare componentă conectată . Orice subgraf generat de vârfuri cu mai multe muchii decât numărul de vârfuri corespunde unui set de chei pentru care nu există suficiente sloturi în tabelul hash. Dacă funcția hash este aleasă aleatoriu, graficul cucului va fi un grafic aleatoriu în modelul Erdős-Rényi . Cu un grad mare de probabilitate, pentru un grafic aleatoriu în care raportul dintre numărul de muchii și numărul de vârfuri este mărginit peste 1/2, graficul este o pseudopădure și algoritmul de hașare a cucului localizează cu succes toate cheile. Mai mult, aceeași teorie demonstrează că dimensiunea așteptată a componentelor conectate ale unui graf cuco este mică, ceea ce asigură un timp de inserție așteptat constant [2] .

Exemplu

Având în vedere următoarele două funcții hash:


k h(k) h'(k)
douăzeci 9 unu
cincizeci 6 patru
53 9 patru
75 9 6
100 unu 9
67 unu 6
105 6 9
3 3 0
36 3 3
39 6 3

Coloanele din următoarele două tabele arată starea tabelului hash după ce elementele au fost introduse.

1. tabel pentru h(k)
douăzeci cincizeci 53 75 100 67 105 3 36 39
0
unu 100 67 67 67 67 100
2
3 3 36 36
patru
5
6 cincizeci cincizeci cincizeci cincizeci cincizeci 105 105 105 cincizeci
7
opt
9 douăzeci douăzeci 53 75 75 75 53 53 53 75
zece
2. tabel pentru h'(k)
douăzeci cincizeci 53 75 100 67 105 3 36 39
0 3 3
unu douăzeci douăzeci douăzeci douăzeci douăzeci douăzeci douăzeci douăzeci
2
3 39
patru 53 53 53 cincizeci cincizeci cincizeci 53
5
6 75 75 75 67
7
opt
9 100 100 100 100 105
zece

Cicluri

Dacă doriți să introduceți elementul 6, veți obține o buclă infinită. În ultimul rând al tabelului găsim aceeași situație inițială ca la început.



cheie tabelul 1 masa 2

valoare veche		 noua
valoare
valoare veche		 noua
valoare
6 cincizeci 6 53 cincizeci
53 75 53 67 75
67 100 67 105 100
105 6 105 3 6
3 36 3 39 36
39 105 39 100 105
100 67 100 75 67
75 53 75 cincizeci 53
cincizeci 39 cincizeci 36 39
36 3 36 6 3
6 cincizeci 6 53 cincizeci

Variante

Au fost explorate unele variații ale hashingului cucului, în principal cu scopul de a îmbunătăți utilizarea spațiului prin creșterea factorului de încărcare . În aceste variante se poate atinge un prag de încărcare de peste 50%. Unele dintre aceste metode pot fi utilizate pentru a reduce semnificativ numărul de reconstrucții ale structurii de date necesare.

O generalizare a hashingului cucului folosind mai mult de două funcții hash poate fi de așteptat să folosească mai bine tabelul hash, sacrificând o anumită viteză de preluare și inserare. Utilizarea a trei funcții hash crește factorul de încărcare la 91% [3] . O altă generalizare a hashingului cucului, numită hashing cuc bloc , conține mai mult de o cheie per celulă. Utilizarea a două taste pe celulă vă permite să creșteți sarcina peste 80% [4] .

O altă opțiune care a fost studiată este hashingul cucului cu o marjă . „Stock” este o matrice de chei de lungime constantă care este folosită pentru a stoca cheile care nu pot fi inserate cu succes în tabelul hash principal. Această modificare reduce numărul de eșecuri la o funcție polinomială inversă cu un grad care poate fi arbitrar mare prin creșterea mărimii marjei. Cu toate acestea, o marjă mare înseamnă o căutare mai lentă pentru o cheie care nu se află în tabelul principal sau dacă se află în marjă. Stocul poate fi folosit în combinație cu mai mult de două funcții de hash sau blocați hașarea cucului pentru a obține atât o utilizare ridicată, cât și erori de inserare scăzute [5] . Analiza hash cu cuc s-a extins mai mult decât la funcțiile hash practice, nu doar la modelele hash aleatoare utilizate în analiza hash teoretică [6] .

Unii cercetători propun să utilizeze o generalizare simplificată a hashingului cuc în unele cache ale procesorului numită cache asociativă asimetrică . [7]

Comparație cu structuri similare

Există și alți algoritmi care folosesc mai multe funcții hash, în special filtrul Bloom  , o structură de date eficientă în memorie pentru seturi fuzzy. O structură de date alternativă pentru probleme cu aceleași seturi fuzzy, bazată pe hashing cuc, numită filtru cuc , folosește și mai puțină memorie și (spre deosebire de filtrele clasice Bloom) permite îndepărtarea elementelor, nu doar inserarea și verificarea existenței. Cu toate acestea, analiza teoretică a acestor metode este mult mai slabă decât analiza filtrelor Bloom [8] .

Studiile din 2006 [9] au arătat că hashingul cucului este semnificativ mai rapid decât metoda de înlănțuire pentru tabelele hash mici situate în memoria cache a procesoarelor moderne. În același an [10] , a fost dezvoltată o versiune bloc de hashing cuc (un bloc conține mai mult de o cheie), care este mai rapidă decât metodele convenționale pentru tabele hash mari în cazul unui factor de încărcare mare. Viteza versiunii bloc a tabelului hash cuc a fost investigată în 2009 [11] .

Vezi și

Note

  1. ↑ 1 2 3 Pagh, Rodler, 2001 , p. 121–133.
  2. ↑ Kutzelnigg, 2006 , p. 403–406.
  3. ↑ Mitzenmacher, 2009 .
  4. ↑ Dietzfelbinger și Weidling 2007 , p. 47–68.
  5. ↑ Kirsch, Mitzenmacher, Wieder, 2010 , p. 1543–1561
  6. ↑ Aumüller, Dietzfelbinger, Woelfel, 2014 , p. 428–456.
  7. ↑ „Micro-Arhitectură” .
  8. ↑ Fan, Kaminsky, Andersen, 2013 , p. 36–40.
  9. ↑ Zukowski, Heman, Boncz, 2006 .
  10. ↑ Ross, 2006 .
  11. ↑ Askitis, 2009 , p. 113–122.

Literatură

Link -uri

Exemple