Dacă ați programat înainte, sunteți sigur că ați întâlnit tabele de hash și hash. Mulți dezvoltatori au folosit tabele hash într-o formă sau alta, iar dezvoltatorii începători trebuie să învețe această structură fundamentală de date. Există doar o problemă:

Toate tutorialele pe care le întâlniți vor discuta cu siguranță tabele de hash și hash în JavaScript, Python sau în alt limbaj de programare.

Ceea ce înseamnă acest lucru este că este posibil să înțelegeți puțin despre cum funcționează hashing și despre cum să utilizați un tabel de hash [insert language here], dar poate lipsi principiile modului în care funcționează.

Nu ar fi minunat dacă am putea învăța despre hashing fără să cunoaștem o anumită limbă? Dacă știți cum funcționează hashing și ce este un tabel hash, limba nu ar trebui să conteze.

Aceasta este abordarea fără cod și, în această postare, vă voi învăța totul despre tabelele hash și hash, indiferent de limbajul de programare pe care îl utilizați în prezent. Fie că sunteți un junior sau un senior dev, toată lumea va învăța ceva din această postare.

Deci, ce este o funcție Hash oricum?

Înainte de a intra în toate lucrurile de lux, permiteți-mi să vă spun ce este hashing. Pentru a ușura, să ne imaginăm că avem o cutie neagră:

Ghidul fara cod pentru Hashing si Hash Tables
Sunt o cutie neagră

Această cutie neagră este specială. Se numește casetă de funcții. O vom numi o casetă funcțională, deoarece această casetă va mapa o variabilă independentă de intrare la o variabilă dependentă de ieșire (sună mat, dar poartă cu mine).

Caseta noastră de funcții funcționează astfel: dacă punem o literă în casetă, vom scoate un număr. Deoarece caseta noastră este o casetă funcțională, nu poate exista decât o singură ieșire pentru fiecare intrare în casetă.

Caseta noastră de funcții va prelua o literă de la AJ pe intrare și va afișa un număr corespunzător de la 0 la 9 pe ieșire. Deci, dacă introducem C, vom obține 2 la ieșire.

1611260767 942 Ghidul fara cod pentru Hashing si Hash Tables
Caseta de funcții

Aceasta formează elementele de bază ale ceea ce este o funcție hash. Cu toate acestea, funcția hash face un pas mai departe. Vom mapa datele de intrare la o anumită valoare numerică de la ieșire, de obicei o secvență hexazecimală.

1611260767 167 Ghidul fara cod pentru Hashing si Hash Tables
Funcția Hash

Deci, în esență, tot ceea ce face hashing este că folosește o funcție pentru a mapa datele la o valoare numerică sau alfanumerică reprezentativă. Pentru funcția hash, indiferent de dimensiunea intrării, ieșirea va rămâne întotdeauna aceeași.

Dar mesele Hash?

Deci, în acest moment, vă puteți întreba ce este o masă de hash. Tabelele Hash utilizează hashing pentru a forma o structură de date.

Tabelele Hash utilizează o metodă asociativă pentru a stoca date utilizând ceea ce este cunoscut sub numele de sistem de căutare valoare-cheie. Tot ceea ce înseamnă este că, într-un tabel hash, tastele sunt mapate la valori unice.

Acest sistem de organizare a datelor are ca rezultat un mod foarte rapid de a găsi datele în mod eficient. Acest lucru se datorează faptului că, din moment ce fiecare cheie este mapată la o valoare unică – odată ce cunoaștem o cheie, putem găsi instantaneu valoarea asociată.

Tabelele Hash sunt extrem de rapide, având o complexitate de timp care este în ordinea lui O (1).

Confuz? Aruncați o privire la această diagramă, unde avem mai multe casete de funcții care generează valori hash.

1611260768 70 Ghidul fara cod pentru Hashing si Hash Tables
Cutii cu funcții multiple

În acest scenariu, fiecare caracter de pe intrare (fiecare este o cheie) are aplicată o funcție hash, iar funcția hash din caseta de funcții generează valoarea hash. Această valoare rezultată este apoi mapată la un index din lista sau matricea legată subiacentă utilizată pentru a implementa tabelul hash.

Structura rezultată va arăta astfel:

1611260768 887 Ghidul fara cod pentru Hashing si Hash Tables
Hash Table

Hash Collisions

Acesta este un moment bun pentru a vorbi despre coliziune în funcțiile hash și tabele hash.

O funcție în matematică este ideală prin aceea că un element din intrare este mapat la exact un element din ieșire.

Cu toate acestea, într-o funcție hash, nu este întotdeauna așa. Uneori diferite valori de hash în intrare pot produce aceeași valoare de hash în ieșire. Când se întâmplă acest lucru, veți obține ceea ce este cunoscut sub numele de coliziune hash.

Coliziunile hash nu sunt foarte frecvente în majoritatea cazurilor de utilizare, deoarece o mică modificare a intrării poate produce o ieșire diferită dramatic. Dar cu cât trebuie să introduceți mai multe date în funcția hash, cu atât este mai probabil să se producă o coliziune.

În exemplul de tabel hash pe care l-am furnizat mai devreme, am presupus că a fost utilizată o matrice pentru a implementa tabelul hash. Deși acest lucru este bun pentru tabelele hash simple, în practică acestea nu sunt foarte bune pentru gestionarea coliziunilor.

Ca atare, se folosește o metodă cunoscută sub numele de înlănțuire. În lanț, dacă tabelul hash returnează aceeași valoare hash pentru mai multe elemente, pur și simplu „înlănțuim” elementele împreună cu aceleași valori hash la același indice din tabelul hash.

În acest fel, în loc să fim implementați ca o matrice cu un index, implementăm tabelul hash folosind o listă legată în care fiecare element este o listă, mai degrabă decât având doar o singură valoare atribuită.

Dar pe măsură ce lungimea lanțului crește, complexitatea timpului tabelului hash se poate agrava. Este utilizată și o metodă cunoscută sub numele de adresare deschisă. În acesta, se găsesc locații alternative în structura de date subiacentă care implementează tabelul hash. Rețineți că această metodă va reduce eficiența tabelului hash și are o complexitate de timp mai slabă.

Hashing este la fel ca Criptarea sau Codificarea?

Mulți oameni au tendința de a asocia hash-ul cu criptarea sau codificarea. Deci este criptarea hashing? Este la fel ca codificarea?

Vedeți, în criptare confundăm datele, astfel încât doar cineva cu cheia necesară pentru a decripta datele va avea acces la acestea. Atunci când folosim un cifru de criptare, nu numai că facem datele criptate, dar dorim să le decriptăm la un moment dat. În criptare vrem să recuperăm datele originale.

Hashing, pe de altă parte, preia date și produce o ieșire în scopul confirmării integrității datelor. În hashing nu avem intenția de a recupera datele originale.

Codificarea diferă de criptare și hashing prin faptul că scopul codificării nu este de a ascunde datele în orice scop de securitate, ci doar de a converti datele într-un format pe care un alt sistem îl poate utiliza.

Ce pot face cu Hashing?

Hash și tabelele hash au numeroase utilizări! Acestea includ:

  1. Criptosisteme
  2. Verificări de redundanță ciclică
  3. Motoare de căutare
  4. Baze de date
  5. Compilatoare

Sau orice sistem care are un proces complex de căutare.

Încheierea

În această postare am abordat elementele de bază ale hashingului, totul fără a scrie o singură linie de cod! A fost ușor, nu? Abordarea fără cod este o modalitate mult mai ușoară de a învăța despre aceste subiecte fundamentale.

Am aflat că funcțiile hash pot fi utilizate pentru a converti obiecte într-o ieșire alfanumerică cu lungime fixă. De asemenea, am aflat că tabelele hash sunt sisteme de căutare valoare-cheie și, deși funcționează bine, nu sunt perfecte și uneori suferă de coliziuni.

Până la sfârșitul acestei postări ar trebui să știți diferența dintre hashing, criptare și codificare și, de asemenea, să aveți o idee despre unde pot fi utilizate hash-urile.

Ți-a plăcut abordarea fără cod? Vrei să mergi mai departe?

Aflați despre tabele hash și alte structuri de date și algoritmi în cartea „Structuri de date fără cod și algoritmi”. Veți obține o extindere a ceea ce a fost acoperit în această postare și veți afla despre multe alte subiecte, toate fără a scrie o singură linie de cod!

Structuri de date și algoritmi fără cod – Aflați DSA fără a scrie o singură linie de cod | Armstrong Subero | Apress
Această carte vă aduce o nouă perspectivă asupra algoritmilor și structurilor de date, complet fără cod. Aflați despre algoritmii de structură a datelor (DSA) fără a fi nevoie să vă deschideți editorul de coduri, să utilizați un compilator sau să priviți un mediu de dezvoltare integrat (IDE) ….
1611050589 887 Cum se invata structurarea datelor arborescente in mod fara cod