Hashing este o structură fundamentală de date care stochează și preia eficient datele într-un mod care permite accesul rapid. Aceasta implică maparea datelor la un index specific într-un tabel hash folosind a funcția hash care permite recuperarea rapidă a informațiilor pe baza cheii acesteia. Această metodă este utilizată în mod obișnuit în bazele de date, c sisteme dureroase și diverse aplicații de programare pentru a optimiza operațiunile de căutare și regăsire.
Structuri de date – Hashing
Cuprins
modele de programare java
- Funcția Hash
- Ce este o coliziune Hash?
- Tehnici de rezolvare a coliziunilor
- Aplicații de hashing
- Problemă ușoară la hashing
- Problemă medie la hashing
- Problemă grea la hashing
Cum functioneaza:
- Funcția Hash: Vă furnizați elementele de date în funcția hash.
- Cod hash: Funcția hash analizează datele și oferă un cod hash unic.
- Tabel Hash: Codul hash vă indică apoi către o anumită locație din tabelul hash.
Funcția Hash
The funcția hash este o funcție care ia a cheie și returnează un index în masa hash . Scopul unei funcții hash este de a distribui cheile uniform pe tabelul hash, minimizând coliziunile (atunci când două chei se mapează la același index).
Funcțiile hash comune includ:
- Metoda de împărțire: Cheie % Dimensiunea tabelului Hash
- Metoda de înmulțire: (Cheie * Constant) % Dimensiunea tabelului Hash
- Hashing universal: O familie de funcții hash concepute pentru a minimiza coliziunile
Ce este o coliziune Hash?
O coliziune hash are loc atunci când două chei diferite se mapează la același index într-un tabel hash. Acest lucru se poate întâmpla chiar și cu o funcție hash bună, mai ales dacă tabelul hash este plin sau cheile sunt similare.
Cauzele coliziunilor Hash:
- Funcție Hash slabă: O funcție hash care nu distribuie cheile uniform pe tabelul hash poate duce la mai multe coliziuni.
- Factor de sarcină mare: Un factor de încărcare mare (raportul dintre chei și dimensiunea tabelului hash) crește probabilitatea de coliziuni.
- Chei similare: Cheile care sunt similare ca valoare sau structură sunt mai susceptibile de a se ciocni.
Tehnici de rezolvare a coliziunilor
Există două tipuri de tehnici de rezoluție a coliziunilor:
- Adresare deschisă:
- Sondare liniară: Căutați secvențial un slot gol
- Sondare cuadratică: Căutați un slot gol folosind o funcție pătratică
- Adresare închisă:
- Înlănțuire: Stocați cheile care se ciocnesc într-o listă conexă sau într-o arbore binar de căutare la fiecare index
- Hashing cu cuc: Utilizați mai multe funcții hash pentru a distribui cheile
Aplicații de hashing
Tabelele hash sunt utilizate într-o mare varietate de aplicații, inclusiv:
- Baze de date: Stocarea și preluarea datelor pe baza cheilor unice
- Memorarea în cache: Stocarea datelor accesate frecvent pentru o recuperare mai rapidă
- Tabelele cu simboluri: Maparea identificatorilor la valorile lor în limbaje de programare
- Rutare în rețea: Determinarea celei mai bune căi pentru pachetele de date
Ce este Hashing?
Problemă ușoară la hashing
- Aflați dacă o matrice este un subset al altei matrice
- Unirea și intersecția a două liste legate
- Având în vedere o matrice A[] și un număr x, verificați perechea în A[] cu suma ca x
- Distanța maximă dintre două apariții ale aceluiași element din matrice
- Numărați maximum de puncte pe aceeași linie
- Cel mai frecvent element dintr-o matrice
- Găsiți singurul element repetitiv între 1 și n-1
- Cum se verifică dacă două seturi date sunt disjunctive?
- Sumă fără suprapunere a două seturi
- Verificați dacă două matrice sunt egale sau nu
- Găsiți elementele lipsă dintr-un interval
- Număr minim de submulțimi cu elemente distincte
- Eliminați numărul minim de elemente astfel încât să nu existe niciun element comun în ambele matrice
- Găsiți perechi cu o sumă dată astfel încât elementele perechii să fie în rânduri diferite
- Numărați perechile cu suma dată
- Numărați cvadruple din patru tablouri sortate a căror sumă este egală cu o valoare dată x
- Sortați elementele după frecvență
- Găsiți toate perechile (a, b) dintr-o matrice astfel încât a % b = k
- Grupați cuvinte cu același set de caractere
- k-al-lea element distinct (sau nerepetabil) dintr-o matrice.
Problemă medie la hashing
- Găsiți Itinerar dintr-o listă dată de bilete
- Găsiți numărul de angajați sub fiecare angajat
- Cel mai lung subbary cu suma divizibilă cu k
- Găsiți cel mai mare subbary cu 0 sumă
- Cea mai lungă Subsecvență consecutivă în creștere
- Numărați elemente distincte în fiecare fereastră de dimensiune k
- Găsiți subbary cu suma dată | Setul 2 (tratează numerele negative)
- Implementarea propriei noastre tabele hash cu înlănțuire separată în Java
- Implementarea propriului tabel Hash cu Open Addressing Linear Probing în C++
- Inserții minime pentru a forma un palindrom cu permutări permise
- Diferența maximă posibilă a două subseturi ale unui tablou
- Sortare folosind funcția hash trivială
- Cel mai mic subbary cu k numere distincte
Problemă grea la hashing
- Clonează un arbore binar cu indicatori aleatoriu
- Cel mai mare subbary cu număr egal de 0 și 1
- Toate tripletele unice care însumează o valoare dată
- Interogări subșir de palindrom
- Interogări de interval pentru frecvențele elementelor matricei
- Elemente care trebuie adăugate astfel încât toate elementele unui interval să fie prezente în matrice
- Cuckoo Hashing – Cel mai rău caz O(1) Căutare!
- Numărați sub-tabele cu elemente totale distincte la fel ca și matricea originală
- Matrice maximă din două matrice date păstrând ordinea aceeași
- Găsiți Suma tuturor sumelor unice sub-matrice pentru o matrice dată.
- secvența lui Recaman
- Lungimea celei mai lungi subsecvențe bitonice stricte
- Găsiți toți subarborele duplicat
- Aflați dacă există un dreptunghi în matricea binară cu colțurile ca 1
Link-uri rapide:
- „Probleme de practică” la hashing
- Top 20 de întrebări de interviu bazate pe tehnica de hashing
- „Videoclipuri” pe Hashing
Recomandat:
- Aflați structura datelor și algoritmi | Tutorial DSA