Phenquestions
Să presupunem că sunteți proprietarul unui mare magazin de aprovizionare din județul în care locuiți. Să presupunem că locuiți într-o zonă mare, care nu este o zonă comercială. Nu sunteți singurul cu un magazin de aprovizionare în zonă; ai câțiva concurenți. Și apoi vi se pare că ar trebui să înregistrați numerele de telefon ale clienților dvs. într-un carnet de exerciții. Desigur, caietul de exerciții este mic și nu puteți înregistra toate numerele de telefon pentru toți clienții dvs.
Deci, decideți să înregistrați numai numerele de telefon ale clienților obișnuiți. Și astfel aveți un tabel cu două coloane. Coloana din stânga are numele clienților, iar coloana din dreapta are numerele de telefon corespunzătoare. În acest fel, există o mapare între numele clienților și numerele de telefon. Coloana din dreapta a tabelului poate fi considerată ca tabelul hash de bază. Numele clienților sunt acum numite taste, iar numerele de telefon sunt numite valori. Rețineți că, atunci când un client intră în transfer, va trebui să-i anulați rândul, permițând rândul să fie gol sau să fie înlocuit cu cel al unui nou client obișnuit. De asemenea, rețineți că, cu timpul, numărul clienților obișnuiți poate crește sau scădea, astfel încât masa poate crește sau se poate micșora.
Ca un alt exemplu de cartografiere, presupuneți că există un club de fermieri într-un județ. Desigur, nu toți fermierii vor fi membri ai clubului. Unii membri ai clubului nu vor fi membri obișnuiți (prezență și contribuție). Bar-barul poate decide să înregistreze numele membrilor și alegerea băuturii lor. El dezvoltă un tabel de două coloane. În coloana din stânga, scrie numele membrilor clubului. În coloana din dreapta, el scrie alegerea corespunzătoare a băuturii.
Există o problemă aici: există duplicate în coloana din dreapta. Adică, același nume de băutură se găsește de mai multe ori. Cu alte cuvinte, membrii diferiți beau aceeași băutură dulce sau aceeași băutură alcoolică, în timp ce alți membri beau o băutură dulce sau alcoolică diferită. Bar-barul decide să rezolve această problemă prin inserarea unei coloane înguste între cele două coloane. În această coloană din mijloc, începând de sus, el numerotează rândurile care încep de la zero (i.e. 0, 1, 2, 3, 4 etc.), coborând, un index pe rând. Cu aceasta, problema sa este rezolvată, deoarece un nume de membru se mapează acum la un index și nu la numele unei băuturi. Deci, întrucât o băutură este identificată printr-un index, numele unui client este mapat la indexul corespunzător.
Coloana valorilor (băuturi) singură formează tabelul hash de bază. În tabelul modificat, coloana indicilor și valorile asociate acestora (cu sau fără duplicate) formează un tabel hash normal - definiția completă a unui tabel hash este dată mai jos. Cheile (prima coloană) nu fac neapărat parte din tabelul de hash.
Ca un alt exemplu din nou, luați în considerare un server de rețea în care un utilizator de pe computerul său client poate adăuga unele informații, șterge unele informații sau modifica unele informații. Există mulți utilizatori pentru server. Fiecare nume de utilizator corespunde unei parole stocate pe server. Cei care întrețin serverul pot vedea numele de utilizator și parola corespunzătoare, astfel încât să poată corupe activitatea utilizatorilor.
Deci, proprietarul serverului decide să producă o funcție care criptează o parolă înainte de a fi stocată. Un utilizator se conectează la server, cu parola sa normală înțeleasă. Cu toate acestea, acum, fiecare parolă este stocată într-o formă criptată. Dacă cineva vede o parolă criptată și încearcă să se conecteze folosind aceasta, aceasta nu va funcționa, deoarece conectarea primește o parolă înțeleasă de către server și nu o parolă criptată.
În acest caz, parola înțeleasă este cheia, iar parola criptată este valoarea. Dacă parola criptată se află într-o coloană de parole criptate, atunci acea coloană este un tabel hash de bază. Dacă acea coloană este precedată de o altă coloană cu indici care încep de la zero, astfel încât fiecare parolă criptată este asociată cu un index, atunci atât coloana de indici, cât și coloana de parolă criptată, formează un tabel hash normal. Cheile nu fac parte neapărat din tabelul hash.
Rețineți, în acest caz, că fiecare cheie, care este o parolă înțeleasă, corespunde unui nume de utilizator. Deci, există un nume de utilizator care corespunde unei chei care este mapată la un index, care este asociată cu o valoare care este o cheie criptată.
Definiția unei funcții hash, definiția completă a unui tabel hash, semnificația unei matrice și alte detalii sunt date mai jos. Trebuie să aveți cunoștințe despre indicii (referințe) și liste legate, pentru a aprecia restul acestui tutorial.
Înțelesul funcției Hash și al tabelului Hash
Matrice
O matrice este un set de locații consecutive de memorie. Toate locațiile sunt de aceeași dimensiune. Valoarea din prima locație este accesată cu indexul, 0; valoarea din a doua locație este accesată cu indexul, 1; a treia valoare este accesată cu indexul, 2; al patrulea cu index, 3; și așa mai departe. O matrice nu poate crește sau micșora în mod normal. Pentru a schimba dimensiunea (lungimea) unui tablou, trebuie creat un nou tablou, iar valorile corespunzătoare trebuie copiate în noul tablou. Valorile unui tablou sunt întotdeauna de același tip.
Funcția Hash
În software, o funcție hash este o funcție care ia o cheie și produce un index corespunzător pentru o celulă matrice. Matricea are o dimensiune fixă (lungime fixă). Numărul de chei este de dimensiuni arbitrare, de obicei mai mare decât dimensiunea matricei. Indicele rezultat din funcția hash se numește valoare hash sau rezumat sau cod hash sau pur și simplu hash.
Hash Table
Un tabel hash este o matrice cu valori, la ai căror indici, cheile sunt mapate. Cheile sunt mapate indirect la valori. De fapt, se spune că tastele sunt mapate la valori, deoarece fiecare index este asociat cu o valoare (cu sau fără duplicate). Cu toate acestea, funcția care face mapare (i.e. hashing) relaționează cheile cu indicii matricei și nu cu valorile, deoarece ar putea exista duplicate în valori. Următoarea diagramă ilustrează un tabel hash pentru numele persoanelor și numerele lor de telefon. Celulele matrice (sloturi) se numesc găleți.
Observați că unele găleți sunt goale. Un tabel hash nu trebuie să aibă neapărat valori în toate gălețile sale. Valorile din cupe nu trebuie neapărat să fie în ordine crescătoare. Cu toate acestea, indicii cu care sunt asociați sunt în ordine crescătoare. Săgețile indică maparea. Observați că tastele nu se află într-o matrice. Nu trebuie să fie în nicio structură. O funcție hash ia orice tastă și elimină un index pentru o matrice. Dacă nu există nicio valoare în bucket asociată cu indexul hash, o nouă valoare poate fi pusă în acel bucket. Relația logică este între cheie și index și nu între cheie și valoarea asociată indexului.
Valorile unui tablou, precum cele din acest tabel hash, sunt întotdeauna de același tip de date. Un tabel hash (găleți) poate conecta cheile la valorile diferitelor tipuri de date. În acest caz, valorile matricei sunt toate indicatori, indicând diferite tipuri de valori.
Un tabel hash este o matrice cu funcție hash. Funcția preia o tastă și hashează un index corespunzător și astfel conectează cheile la valori, în matrice. Cheile nu trebuie să facă parte din tabelul hash.
De ce Array și nu Listă legată pentru Hash Table
Matricea pentru un tabel hash poate fi înlocuită cu o structură de date de listă legată, dar ar exista o problemă. Primul element al unei liste legate este în mod natural la index, 0; al doilea element este în mod natural la index, 1; al treilea este în mod natural la index, 2; și așa mai departe. Problema cu lista legată este că, pentru a extrage o valoare, lista trebuie să fie iterată și aceasta necesită timp. Accesarea unei valori dintr-o matrice se face prin acces aleatoriu. Odată ce indicele este cunoscut, valoarea se obține fără iterație; acest acces este mai rapid.
Coliziune
Funcția hash preia o cheie și hashează indexul corespunzător, pentru a citi valoarea asociată sau pentru a insera o nouă valoare. Dacă scopul este de a citi o valoare, nu există nicio problemă (nici o problemă), până acum. Cu toate acestea, dacă scopul este de a insera o valoare, indicele hash poate avea deja o valoare asociată și aceasta este o coliziune; noua valoare nu poate fi pusă acolo unde există deja o valoare. Există modalități de rezolvare a coliziunii - vezi mai jos.
De ce apare coliziunea
În exemplul magazinului de aprovizionare de mai sus, numele clienților sunt cheile, iar numele băuturilor sunt valorile. Observați că clienții sunt prea mulți, în timp ce matricea are o dimensiune limitată și nu poate lua toți clienții. Deci, numai băuturile clienților obișnuiți sunt stocate în matrice. Coliziunea ar avea loc atunci când un client neobișnuit devine obișnuit. Clienții pentru magazin formează un set mare, în timp ce numărul de găleți pentru clienții din matrice este limitat.
Cu tabelele hash, valorile pentru chei sunt foarte probabil, care sunt înregistrate. Atunci când o cheie care nu era probabilă devine probabilă, ar exista probabil o coliziune. De fapt, coliziunea are loc întotdeauna cu tabele hash.
Noțiuni de bază privind rezolvarea coliziunilor
Două abordări ale rezoluției coliziunilor se numesc înlănțuire separată și adresare deschisă. În teorie, cheile nu ar trebui să fie în structura datelor sau nu ar trebui să facă parte din tabelul hash. Cu toate acestea, ambele abordări necesită ca coloana cheie să preceadă tabelul hash și să devină parte a structurii generale. În loc ca tastele să se afle în coloana tastelor, indicatoarele către taste pot fi în coloana tastelor.
Un tabel hash practic include o coloană chei, dar această coloană cheie nu face parte oficial din tabelul hash.
Oricare dintre abordări pentru rezoluție poate avea găleți goale, nu neapărat la sfârșitul matricei.
Înlănțuire separată
În lanțuri separate, atunci când are loc o coliziune, noua valoare este adăugată la dreapta (nu deasupra sau dedesubt) valorii ciocnite. Deci, două sau trei valori ajung să aibă același indice. Rareori mai mult de trei ar trebui să aibă același indice.
Mai multe valori pot avea într-adevăr același indice într-o matrice? - Nu. Deci, în multe cazuri, prima valoare pentru index este un pointer către o structură de date a listei legate, care deține valorile unu, două sau trei colisionate. Următoarea diagramă este un exemplu de tabel hash pentru înlănțuirea separată a clienților și a numerelor de telefon ale acestora:
Găleatele goale sunt marcate cu litera x. Restul sloturilor au indicii către liste legate. Fiecare element al listei conectate are două câmpuri de date: unul pentru numele clientului și celălalt pentru numărul de telefon. Conflictul apare pentru chei: Peter Jones și Suzan Lee. Valorile corespunzătoare constau din două elemente dintr-o listă legată.
Pentru cheile aflate în conflict, criteriul de inserare a valorii este același criteriu utilizat pentru localizarea (și citirea) valorii.
Deschideți adresarea
Cu adresarea deschisă, toate valorile sunt stocate în matricea bucket. Când apare conflictul, noua valoare este inserată într-o găleată goală nouă, valoarea corespunzătoare pentru conflict, urmând un anumit criteriu. Criteriul utilizat pentru a insera o valoare la conflict este același criteriu utilizat pentru localizarea (căutarea și citirea) valorii.
Următoarea diagramă ilustrează rezolvarea conflictelor cu adresare deschisă:
Funcția hash preia cheia, Peter Jones și hashează indexul, 152, și își stochează numărul de telefon în cupa asociată. După ceva timp, funcția hash are același indice, 152 din tasta, Suzan Lee, care se ciocnește cu indicele pentru Peter Jones. Pentru a rezolva acest lucru, valoarea pentru Suzan Lee este stocată în cupa următorului index, 153, care era gol. Funcția hash hash index, 153 pentru cheie, Robin Hood, dar acest index a fost deja folosit pentru a rezolva conflictul pentru o cheie anterioară. Deci valoarea pentru Robin Hood este plasată în următoarea găleată goală, care este cea a indicelui 154.
Metode de rezolvare a conflictelor pentru înlănțuirea separată și adresarea deschisă
Înlănțuirea separată are metodele sale de rezolvare a conflictelor, iar adresarea deschisă are, de asemenea, propriile sale metode de rezolvare a conflictelor.
Metode de rezolvare a conflictelor de lanțuri separate
Metodele pentru înlănțuirea tabelelor hash separate sunt explicate pe scurt acum:
Înlănțuirea separată cu listele legate
Această metodă este așa cum s-a explicat mai sus. Cu toate acestea, fiecare element al listei legate nu trebuie să aibă neapărat câmpul cheie (e.g. câmpul cu numele clientului de mai sus).
Separați înlănțuirea cu celulele capului listei
În această metodă, primul element al listei legate este stocat într-o găleată a matricei. Acest lucru este posibil, dacă tipul de date pentru matrice, este elementul listei conectate.
Separați înlănțuirea de alte structuri
Orice altă structură de date, cum ar fi Arborele de căutare binară de auto-echilibrare care acceptă operațiile necesare, poate fi utilizată în locul listei conectate - vezi mai târziu.
Metode de rezolvare a conflictelor de adresare deschisă
O metodă de rezolvare a conflictelor în adresarea deschisă se numește secvență sondă. Trei secvențe de sondă bine cunoscute sunt explicate pe scurt acum:
Sondare liniară
Cu sondarea liniară, atunci când apare un conflict, se caută cea mai apropiată găleată goală de sub găleată la conflict. De asemenea, cu sondare liniară, atât cheia, cât și valoarea acesteia sunt stocate în același compartiment.
Sondare quadratică
Să presupunem că conflictul apare la indicele H. Următorul spațiu gol (cupă) la indexul H + 12 este folosit; dacă aceasta este deja ocupată, atunci următoarea goală la H + 22 este utilizat, dacă acesta este deja ocupat, atunci următorul gol la H + 32 este folosit și așa mai departe. Există variante în acest sens.
Hashing dublu
Cu hash dublu, există două funcții hash. Primul calculează (hashează) indexul. Dacă apare un conflict, al doilea folosește aceeași cheie pentru a determina cât de jos trebuie inserată valoarea. Există mai multe la acest lucru - vezi mai târziu.
Funcția Hash perfectă
O funcție hash perfectă este o funcție hash care nu poate duce la nicio coliziune. Acest lucru se poate întâmpla atunci când setul de chei este relativ mic și fiecare cheie se mapează la un anumit număr întreg din tabelul hash.
În setul de caractere ASCII, caracterele majuscule pot fi mapate la literele lor minuscule corespunzătoare utilizând o funcție hash. Literele sunt reprezentate în memoria computerului ca numere. În setul de caractere ASCII, A este 65, B este 66, C este 67 etc. iar a este 97, b este 98, c este 99 etc. Pentru a mapa de la A la a, adăugați 32 la 65; pentru a mapa de la B la b, adăugați 32 la 66; pentru a mapa de la C la c, adăugați 32 la 67; și așa mai departe. Aici, literele mari sunt tastele, iar literele mici sunt valorile. Tabelul hash pentru aceasta poate fi un tablou ale cărui valori sunt indicii asociați. Amintiți-vă, gălețile din matrice pot fi goale. Deci, gălețile din matrice de la 64 la 0 pot fi goale. Funcția hash adaugă pur și simplu 32 la numărul de cod majuscul pentru a obține indexul și, prin urmare, litera minusculă. O astfel de funcție este o funcție hash perfectă.
Hashing de la Indici întregi la Indici întregi
Există diferite metode pentru hashing întreg. Una dintre ele se numește Metoda de divizare Modulo (funcție).
Funcția de divizare Modulo Division
O funcție din software-ul computerului nu este o funcție matematică. În calcul (software), o funcție constă dintr-un set de enunțuri precedate de argumente. Pentru funcția Modulo Division, tastele sunt numere întregi și sunt mapate la indici ai matricei de găleți. Setul de chei este mare, deci numai cheile care sunt foarte susceptibile să apară în activitate ar fi mapate. Deci coliziunile apar atunci când cheile improbabile trebuie mapate.
În declarație,
20/6 = 3R2
20 este dividendul, 6 este divizorul și 3 restul 2 este coeficientul. Restul 2 se mai numește modulul. Notă: este posibil să aveți un modul de 0.
Pentru acest hashing, dimensiunea mesei este de obicei o putere de 2, e.g. 64 = 26 sau 256 = 28, etc. Divizorul pentru această funcție de hash este un număr prim apropiat de dimensiunea matricei. Această funcție împarte cheia la divizor și returnează modulul. Modulo este indicele matricei de găleți. Valoarea asociată din bucket este o valoare la alegere (valoare pentru cheie).
Hashing taste de lungime variabilă
Aici, tastele setului de taste sunt texte de diferite lungimi. Diferite numere întregi pot fi stocate în memorie folosind același număr de octeți (dimensiunea unui caracter englez este un octet). Când diferite taste sunt de dimensiuni de octeți diferite, se spune că au o lungime variabilă. Una dintre metodele de hashing de lungimi variabile se numește Radix Conversion Hashing.
Radix Conversion Hashing
Într-un șir, fiecare caracter din computer este un număr. În această metodă,
Cod Hash (index) = x0Ak − 1+X1Ak − 2+… + Xk − 2A1+Xk − 1A0
Unde (x0, x1,…, xk − 1) sunt caracterele șirului de intrare și a este o rază, e.g. 29 (vezi mai târziu). k este numărul de caractere din șir. Există mai multe la acest lucru - vezi mai târziu.
Chei și valori
Într-o pereche cheie / valoare, o valoare nu poate fi neapărat un număr sau un text. Poate fi și un record. O înregistrare este o listă scrisă orizontal. Într-o pereche cheie / valoare, fiecare cheie se poate referi la alt text sau număr sau înregistrare.
Aranjament asociativ
O listă este o structură de date, în care elementele listei sunt legate și există un set de operații care operează pe listă. Fiecare articol din listă poate consta dintr-o pereche de articole. Tabelul general hash cu cheile sale poate fi considerat o structură de date, dar este mai mult un sistem decât o structură de date. Cheile și valorile lor corespunzătoare nu sunt foarte dependente una de cealaltă. Nu sunt foarte legați între ei.
Pe de altă parte, o matrice asociativă este un lucru similar, dar cheile și valorile lor sunt foarte dependente una de cealaltă; sunt foarte înrudite între ele. De exemplu, puteți avea o gamă asociativă de fructe și culorile lor. Fiecare fruct are în mod natural culoarea sa. Numele fructului este cheia; culoarea este valoarea. În timpul inserării, fiecare cheie este inserată cu valoarea sa. La ștergere, fiecare cheie este ștearsă cu valoarea sa.
O matrice asociativă este o structură de date a tabelului hash compusă din perechi cheie / valoare, unde nu există duplicate pentru chei. Valorile pot avea duplicate. În această situație, cheile fac parte din structură. Adică, cheile trebuie să fie stocate, în timp ce, cu tabelul general hast, cheile nu trebuie să fie stocate. Problema valorilor duplicate este rezolvată în mod natural de indicii matricei de găleți. Nu confundați între valori duplicate și coliziune la un index.
Deoarece un tablou asociativ este o structură de date, are cel puțin următoarele operații:
Operațiuni de matrice asociativă
introduceți sau adăugați
Aceasta introduce o nouă pereche cheie / valoare în colecție, mapând cheia la valoarea sa.
reatribuiți
Această operație înlocuiește valoarea unei anumite chei cu o nouă valoare.
ștergeți sau eliminați
Aceasta elimină o cheie plus valoarea corespunzătoare.
privește în sus
Această operație caută valoarea unei anumite chei și returnează valoarea (fără a o elimina).
Concluzie
O structură de date de tabel hash constă dintr-o matrice și o funcție. Funcția se numește funcție hash. Funcția mapează tastele cu valorile din matrice prin indicii matricei. Cheile nu trebuie să facă neapărat parte din structura datelor. Setul de taste este de obicei mai mare decât valorile stocate. Când apare o coliziune, aceasta este rezolvată fie prin abordarea separată în lanț, fie prin abordarea deschisă. O matrice asociativă este un caz special al structurii de date a tabelului hash.
