MASELE HASH
1. INTRODUCERE.
O abordare radical diferită a căutării față de cele anterioare constă în a continua, nu prin comparații între valorile cheie, ci prin găsirea unor funcții h (k) care ne oferă direct locația tastei k în tabel.
Prima întrebare pe care ne-o putem pune este dacă este ușor să găsim astfel de funcții h. Răspunsul este, în principiu, destul de pesimist, deoarece dacă luăm ca situație ideală o astfel de funcție oferă întotdeauna locații diferite tastelor diferite și ne gândim, de exemplu, la un tabel de dimensiunea 40 în care dorim să adresăm 30 de taste, descoperim că există 40 30 = 1,15 * 10 48 funcții posibile ale setului de taste în tabel și doar 40 * 39 * 11 = 40!/10! = 2,25 * 10 41 dintre ele nu generează locații duplicat. Cu alte cuvinte, doar 2 din 10 milioane de astfel de funcții ar fi „perfecte” pentru scopurile noastre. Această sarcină este fezabilă numai în cazul în care valorile care vor aparține tabelului hash sunt cunoscute a priori. Există algoritmi pentru a crea funcții hash perfecte care sunt folosite pentru a organiza cuvinte cheie într-un compilator, astfel încât căutarea oricăruia dintre aceste cuvinte cheie să fie efectuată în timp constant.
Funcțiile care evită valori duplicate sunt surprinzător de greu de găsit, chiar și pentru tabelele mici. De exemplu, celebrul „paradox al zilei de naștere” asigură faptul că dacă 23 și mai mulți oameni sunt prezenți la o întâlnire, există șanse mari ca doi dintre ei să se fi născut în aceeași zi a aceleiași luni. Cu alte cuvinte, dacă selectăm o funcție aleatorie care aplică 23 de taste la un tabel cu dimensiunea 365, probabilitatea ca două taste să nu cadă în aceeași locație este de doar 0,4927.
În consecință, aplicațiile h (k), pe care de acum înainte le vom numi funcții hash, au particularitatea că ne putem aștepta ca h (k i) = h (k j) pentru câteva perechi diferite (k i, k j). Prin urmare, obiectivul va fi găsirea unei funcții hash care să provoace cel mai mic număr posibil de coliziuni (apariții de sinonime), deși acesta este doar un aspect al problemei, celălalt va fi să proiectăm metode de rezoluție a coliziunilor atunci când apar.
2. FUNCȚII HASH.
Prima problemă pe care trebuie să o abordăm este calculul funcției hash care transformă tastele în locații de tabel. Mai precis, avem nevoie de o funcție care transformă cheile (de obicei numere întregi sau șiruri de caractere) în numere întregi într-un interval [0.M-1], unde M este numărul de registre pe care le putem gestiona cu memoria disponibilă. luând în considerare alegerea funcției h (k) Acestea sunt concepute pentru a minimiza coliziunile și pentru a fi relativ rapide și ușor de calculat, deși situația ideală ar fi găsirea unei funcții h care va genera valori aleatorii uniform pe intervalul [0.M-1]. Cele două abordări pe care le vom vedea sunt îndreptate către acest obiectiv și ambele se bazează pe generatoare de numere aleatorii.
Multiplicative Hasing.
Această tehnică funcționează prin înmulțirea cheii k prin el însuși sau printr-o constantă, apoi folosind o parte din biții produsului ca locație de tabel hash.
Când alegerea este să se înmulțească k Prin ea însăși și păstrând o parte din biții din mijloc, metoda se numește pătrat mediu. Această metodă este încă simplă și poate îndeplini criteriul conform căruia biții aleși pentru a marca locația sunt o funcție a tuturor biților originali ai k, Principalele sale dezavantaje sunt că tastele cu multe zerouri vor fi reflectate în valori hash, de asemenea, cu multe zerouri și că dimensiunea tabelului este limitată la o putere de 2.
O altă metodă multiplicativă, care evită restricțiile anterioare, este de a calcula h (k) = Int [M * Frac (C * k)] unde M este dimensiunea tabelului și 0
Hasing pe divizie.
În acest caz, funcția este calculată pur și simplu ca h (k) = k mod M folosind 0 ca prim index al tabelului hash de dimensiunea M.
Deși formula este aplicabilă tabelelor de orice dimensiune, este important să alegeți cu atenție valoarea lui M. De exemplu, dacă M ar fi par, toate tastele pare (resp. Impare) s-ar aplica la locații pare (resp. Impare), ceea ce ar constitui o părtinire foarte puternică. O regulă simplă pentru alegerea lui M este să o luați ca număr prim. În orice caz, există reguli mai sofisticate pentru alegerea lui M (vezi Knuth), toate bazate pe studii teoretice ale funcționării metodelor congruențiale de generare a numerelor aleatorii.
3. REZOLVAREA COLIZIILOR.
Al doilea aspect important de studiat în hasing este rezolvarea coliziunilor dintre sinonime. Vom studia trei metode de bază de rezoluție a coliziunilor, una dintre ele depinde de ideea de a păstra liste legate de sinonime, iar celelalte două de calculul unei secvențe de locații în tabelul hash până când se găsește una goală. Analiza comparativă a metodelor se va face pe baza studiului numărului de locații care urmează să fie examinate până la stabilirea locului unde se plasează fiecare nouă cheie în tabel.
Pentru toate exemplele, dimensiunea tabelului va fi M = 13, iar funcția hash h 1 (k) pe care o vom folosi va fi:
HASH = Tasta Mod M
și valorile cheii k pe care le vom lua în considerare sunt cele prezentate în tabelul următor:
Presupunând că k = 0 nu apare în mod natural, putem marca toate locațiile din tabel, inițial goale, dându-le valoarea 0. În sfârșit, și deoarece operațiunile de căutare și inserare sunt strâns legate, vor fi prezentați algoritmi pentru a căuta o dacă este necesar (cu excepția cazului în care această operațiune provoacă un overflow de tabel) returnând locația elementului sau un -1 (NULL) în caz de overflow.
Înlănțuire separată sau deschidere deschisă.
Cel mai simplu mod de a rezolva o coliziune este de a construi, pentru fiecare locație din tabel, o listă legată de înregistrări ale căror chei cad în acea direcție. Această metodă este cunoscută sub numele de înlănțuire separată și, evident, timpul necesar unei căutări va depinde de lungimea listelor și de pozițiile relative ale tastelor din ele. Există variante în funcție de menținerea listelor sinonime (FIFO, LIFO, după valoarea cheii etc.), deși în majoritatea cazurilor și având în vedere că listele individuale nu trebuie să fie prea mari, de obicei optăm pentru cea mai simplă alternativă, LIFO.
În orice caz, dacă listele sunt păstrate în ordine, aceasta poate fi văzută ca o generalizare a metodei de căutare secvențială în liste. Diferența este că, în loc să mențină o singură listă cu un singur nod de antet, listele M cu noduri de antet M sunt menținute în așa fel încât numărul de comparații ale căutării secvențiale este redus cu un factor de M (în medie) folosind suplimentar spațiu pentru M indicatori. Pentru exemplul nostru și cu alternativa LIFO, tabelul ar fi așa cum se arată în figura următoare:
Uneori și când numărul de intrări în tabel este relativ moderat, nu este convenabil să le dați intrărilor tabelului hash rolul antetelor listelor, ceea ce ne-ar conduce la o altă metodă de înlănțuire, cunoscută ca înlănțuirea internă. În acest caz, uniunea dintre sinonime se află în cadrul tabelului hash însuși, prin intermediul câmpurilor cursorului (indicatori) care sunt inițializate la -1 (NULL) și care vor indica sinonimele lor respective.