Hashing în DBMS: tehnici de hashing statice și dinamice
Fiona Brown
⚡ Rezumat inteligent
Hashing-ul în DBMS este o tehnică ce calculează locația pe disc a unei înregistrări direct din cheia sa, fără a parcurge un index. O funcție hash mapează cheile de căutare la compartimentele de date, iar hashing-ul static sau dinamic gestionează modul în care aceste compartimente cresc.
Ce este hashing în DBMS?
În SGBD, hashing-ul este o tehnică de căutare directă a locației datelor dorite pe disc, fără a utiliza o structură de index. Metoda de hashing este utilizată pentru a indexa și a recupera elemente dintr-o bază de date, deoarece este mai rapid să căutați un anumit element folosind cheia hash mai scurtă în loc de valoarea sa originală. Datele sunt stocate sub formă de blocuri de date a căror adresă este generată prin aplicarea unei funcții hash; locația de memorie unde sunt stocate aceste înregistrări este cunoscută sub numele de bloc de date sau compartiment de date.
De ce avem nevoie de hashing?
Iată situațiile dintr-un SGBD în care trebuie să aplicați metoda de hashing:
- Pentru o structură de bază de date imensă, este dificil să cauți toate valorile indexului prin toate nivelurile lor și apoi să ajungi la blocul de date destinație pentru a obține datele dorite.
- Hashing-ul este utilizat pentru indexarea și regăsirea elementelor dintr-o bază de date, deoarece este mai rapid să căutați un anumit element folosind cheia hash mai scurtă decât valoarea originală.
- Hashing-ul este o metodă ideală pentru a calcula locația directă a unei înregistrări de date pe disc fără a utiliza o structură de index.
- Este, de asemenea, o tehnică utilă pentru implementarea dicționarelor.
Terminologii importante în hashing
Iată terminologiile importante utilizate în hashing:
- Grupaj de date: „Gălețile de date” sunt locații de memorie unde sunt stocate înregistrările. Sunt cunoscute și sub denumirea de unitate de stocare.
- Cheie: a cheie DBMS este un atribut sau un set de atribute care vă ajută să identificați un rând (tuplu) într-o relație (tabel).
- Funcția hash: o hartăping funcție care mapează tot setul de chei de căutare la adresa unde sunt plasate înregistrările efective.
- Palpare liniară: un interval fix între sonde. În această metodă, următorul bloc de date disponibil este utilizat pentru a introduce noua înregistrare, în loc să suprascrie înregistrarea mai veche.
- Palpare pătratică: ajută la determinarea noii adrese a bucket-ului prin adunarea rezultatului consecutiv al unui polinom pătratic la valoarea inițială dată de calculul inițial.
- Indicele hash: adresa blocului de date. O funcție hash poate fi o funcție matematică simplă sau una complexă.
- Double Hashing: o metodă utilizată în tabelele hash pentru a rezolva coliziunile prin aplicarea unei a doua funcții hash.
- Depășire găleată: Condiția de depășire a bucketului se numește coliziune. Aceasta este o etapă fatală pentru orice funcție hash statică.
Tipuri de tehnici de hashing
Există în principal două tipuri de tehnici de hashing în DBMS:
- Hashing static
- Hashing dinamic
Cele două diferă în principal prin faptul că numărul de găleți este fix, așa cum se explică în următoarele două secțiuni.
Hashing static
În hashing-ul static, adresa rezultată a bucket-ului de date va rămâne întotdeauna aceeași.
Prin urmare, dacă generați o adresă pentru, să zicem, Student_ID = 10 folosind funcția de hashing mod (3), adresa compartimentului rezultată va fi întotdeauna 1Deci nu veți vedea nicio modificare a adresei bucket-ului.
Prin urmare, în metoda de hashing statică, numărul de compartimente de date din memorie rămâne întotdeauna constant.
Funcții hash statice
- Inserarea unei înregistrări: Când o nouă înregistrare trebuie inserată în tabel, generați o adresă pentru aceasta folosind cheia hash. Odată ce adresa este generată, înregistrarea este stocată în locația respectivă.
- In cautarea: Când trebuie să recuperați înregistrarea, aceeași funcție hash este utilizată pentru a recupera adresa bucket-ului în care sunt stocate datele.
- Ștergeți o înregistrare: Folosind funcția hash, mai întâi preluați înregistrarea pe care doriți să o ștergeți, apoi eliminați înregistrarea de la acea adresă din memorie.
Hashing-ul static este împărțit în continuare în:
- Deschide hashing
- Hashing închis
Deschide Hashing
În metoda de hashing deschisă, în loc să se suprascrie înregistrarea mai veche, se folosește următorul bloc de date disponibil pentru a introduce noua înregistrare. Această metodă este cunoscută și sub denumirea de sondare liniară.
De exemplu, A2 este o înregistrare nouă pe care doriți să o inserați. Funcția hash generează adresa 222, dar aceasta este deja ocupată de o altă valoare. De aceea, sistemul caută următoarea categorie de date, 501, și îi atribuie A2.
Hashing închis
În metoda de hashing închis, când gălețile sunt pline, se alocă un nou găleat pentru același hash, iar rezultatul este legat după cel precedent.
Hashing dinamic
Hashing-ul dinamic oferă un mecanism prin care compartimentele de date sunt adăugate și eliminate dinamic și la cerere. În această metodă de hashing, funcția de hashing vă ajută să creați un număr mare de valori, iar structura crește sau se micșorează odată cu datele. Acest lucru o face o alegere excelentă pentru tabelele a căror dimensiune nu poate fi prezisă în avans, unde hashing-ul static ar fie irosi spațiu, fie ar depăși limitele.
Diferența dintre indexarea ordonată și hashing
Mai jos sunt principalele diferențe dintre indexare și hashing:
| parametrii | Indexare ordonată | hashing |
|---|---|---|
| Stocarea adresei | Adresele din memorie sunt sortate în funcție de o valoare a cheii numită cheie primară. | Adresele sunt întotdeauna generate folosind o funcție hash pe valoarea cheii. |
| Performanţă | Poate scădea pe măsură ce datele cresc, deoarece datele sunt stocate sortate și fiecare inserare, ștergere sau actualizare le reordonează. | Performanța este cea mai bună prin adăugarea și ștergerea constantă de date. Pentru o bază de date imensă, întreținerea fișierelor hash devine mai costisitoare. |
| Utilizați pentru | Preferat pentru regăsirea intervalelor, unde datele sunt regăsite pentru un anumit interval. | Ideal pentru regăsirea unei anumite înregistrări pe baza cheii de căutare și funcționează bine doar atunci când funcția hash este pe cheia de căutare. |
| Managementul memoriei | Multe blocuri de date neutilizate provin din operațiuni de ștergere și actualizare și nu pot fi eliberate pentru reutilizare, așa că este necesară o întreținere regulată. | În hashing-ul static și dinamic, memoria este întotdeauna gestionată, iar depășirea bucket-ului este gestionată pentru a extinde hashing-ul static. |
Pe scurt, alegeți ordonat indexare pentru interogări de interval și hashing pentru căutări exacte pe cheie.
Ce este coliziunea?
O coliziune hash este o stare în care hash-urile rezultate din două sau mai multe elemente din setul de date se mapează eronat în același loc în masa de hash.
Cum să gestionezi o coliziune de tip hashing
Există două tehnici pe care le puteți utiliza pentru a evita o coliziune hash:
- Repetare: Această metodă invocă o funcție hash secundară, care se aplică continuu până când se găsește un slot gol unde poate fi plasată o înregistrare.
- Înlănțuire: Metoda de înlănțuire construiește o listă înlănțuită de elemente ale căror chei au aceeași valoare prin hashing. Această metodă necesită un câmp de legătură suplimentar la fiecare poziție din tabel.
