Tabel hash în structura datelor: Python Exemplu
Sarah Chen
Ce este Hashing?
Un hash este o valoare care are o lungime fixă și este generată folosind o formulă matematică. Valorile hash sunt utilizate în compresia datelor, criptologie etc. În indexarea datelor, valorile hash sunt folosite deoarece au lungime fixă, indiferent de valorile care au fost folosite pentru a le genera. Face ca valorile hash să ocupe spațiu minim în comparație cu alte valori de lungimi diferite.
O funcție hash folosește un algoritm matematic pentru a converti cheia într-un hash. O coliziune are loc atunci când o funcție hash produce aceeași valoare hash pentru mai multe chei.
Ce este un tabel Hash?
A HASH TABLE este o structură de date care stochează valori folosind o pereche de chei și valori. Fiecărei valori i se atribuie o cheie unică care este generată folosind o funcție hash.
Numele cheii este folosit pentru a accesa valoarea asociată acesteia. Acest lucru face căutarea valorilor într-un tabel hash foarte rapidă, indiferent de numărul de elemente din tabelul hash.
Funcții Hash
De exemplu, dacă dorim să stocăm înregistrările angajaților, iar fiecare angajat este identificat în mod unic folosind un număr de angajat.
Putem folosi numărul angajatului ca cheie și putem atribui datele angajatului ca valoare.
Abordarea de mai sus va necesita spațiu liber suplimentar de ordinul a (m*n2) unde variabila m este dimensiunea lui mulțime, iar variabila n este numărul de cifre pentru numărul angajatului. Această abordare introduce o problemă de spațiu de stocare.
O funcție hash rezolvă problema de mai sus obținând numărul angajatului și utilizându-l pentru a genera o valoare întreagă hash, cifre fixe și optimizarea spațiului de stocare. Scopul unei funcții hash este de a crea o cheie care va fi folosită pentru a face referire la valoarea pe care dorim să o stocăm. Funcția acceptă valoarea de salvat, apoi folosește un algoritm pentru a calcula valoarea cheii.
Următorul este un exemplu de funcție hash simplă
h(k) = k1 % m
AICI,
- h(k) este funcția hash care acceptă un parametru k. Parametrul k este valoarea pentru care dorim să calculăm cheia.
- k1 % m este algoritmul pentru funcția noastră hash, unde k1 este valoarea pe care dorim să o stocăm și m este dimensiunea listei. Folosim operatorul modul pentru a calcula cheia.
Exemplu
Să presupunem că avem o listă cu o dimensiune fixă de 3 și următoarele valori
[1,2,3]
Putem folosi formula de mai sus pentru a calcula pozițiile pe care ar trebui să le ocupe fiecare valoare.
Următoarea imagine arată indecșii disponibili în tabelul nostru hash.
Pas 1) Calculați astfel poziția care va fi ocupată de prima valoare
h(1) = 1 % 3
= 1
Valoarea 1 va ocupa spatiul pe index 1
Pas 2) Calculați poziția care va fi ocupată de a doua valoare
h(2) = 2 % 3
= 2
Valoarea 2 va ocupa spatiul pe index 2
Pas 3) Calculați poziția care va fi ocupată de a treia valoare.
h(3) = 3 % 3
= 0
Valoarea 3 va ocupa spatiul pe index 0
Rezultat final
Tabelul nostru hash completat va fi acum după cum urmează.
Calitățile unei bune funcții hash
O funcție hash bună ar trebui să aibă următoarele calități.
- Formula pentru generarea hash-ului ar trebui să utilizeze valoarea datelor care urmează să fie stocată în algoritm.
- Funcția hash ar trebui să genereze valori hash unice chiar și pentru datele de intrare care au aceeași cantitate.
- Funcția ar trebui să minimizeze numărul de coliziuni. Coliziunile apar atunci când aceeași valoare este generată pentru mai multe valori.
- Valorile trebuie să fie distribuite în mod consecvent pe întregul hash posibil.
Coliziune
O coliziune are loc atunci când algoritmul generează același hash pentru mai multe valori.
Să vedem un exemplu.
Să presupunem că avem următoarea listă de valori
[3,2,9,11,7]
Să presupunem că dimensiunea tabelului hash este 7 și vom folosi formula (k1 % m) unde m este dimensiunea tabelului hash.
Următorul tabel arată valorile hash care vor fi generate.
| Cheie | Algoritmul hash (k1 % m) | Valoarea hash |
|---|---|---|
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
După cum putem vedea din rezultatele de mai sus, valorile 2 și 9 au aceeași valoare hash și nu putem stoca mai mult de o valoare la fiecare poziție.
Problema dată poate fi rezolvată fie prin înlănțuire, fie prin sondare. Următoarele secțiuni discută înlănțuirea și sondarea în detaliu.
Înlănțuirea
Înlănțuirea este o tehnică care este utilizată pentru a rezolva problema coliziunii prin utilizarea listelor legate, fiecare având indici unici.
Următoarea imagine arată cum arată o listă înlănțuită
Atât 2, cât și 9 ocupă același index, dar sunt stocate ca liste legate. Fiecare listă are un identificator unic.
Beneficiile listelor înlănțuite
Următoarele sunt beneficiile listelor înlănțuite:
- Listele înlănțuite au performanțe mai bune la inserarea datelor deoarece ordinea inserării este O(1).
- Nu este necesar să redimensionați un tabel hash care utilizează o listă înlănțuită.
- Poate găzdui cu ușurință un număr mare de valori atâta timp cât este disponibil spațiu liber.
Sondaj
Cealaltă tehnică care este utilizată pentru a rezolva coliziunea este sondarea. Când folosim metoda de sondare, dacă are loc o coliziune, putem pur și simplu să mergem mai departe și să găsim un slot gol pentru a ne stoca valoarea.
Următoarele sunt metodele de sondare:
| Metodă | Descriere |
|---|---|
| Sondare liniară | Așa cum sugerează și numele, această metodă caută sloturi goale liniar, pornind de la poziția în care a avut loc coliziunea și mergând înainte. Dacă se ajunge la sfârșitul listei și nu este găsit niciun slot gol. Sondarea începe la începutul listei. |
| Sondarea cuadratică | Această metodă utilizează expresii polinomiale pătratice pentru a găsi următorul slot liber disponibil. |
| Double hashing | Această tehnică folosește un algoritm de funcție hash secundar pentru a găsi următorul slot liber disponibil. |
Folosind exemplul nostru de mai sus, tabelul hash după utilizarea probei ar apărea după cum urmează:
Operații cu tabelul hash
Aici sunt Operațiuni suportate de tabelele Hash:
- inserare - acest Operaeste folosit pentru a adăuga un element la tabelul hash
- Căutare - acest Operaeste folosit pentru a căuta elemente în tabelul hash folosind cheia
- Ștergerea - acest Operaeste folosit pentru a șterge elemente din tabelul hash
Operație de inserare a datelor
Operația de inserare este utilizată pentru a stoca valori în tabelul hash. Când o nouă valoare este stocată în tabelul hash, i se atribuie un număr de index. Numărul de index este calculat folosind funcția hash. Funcția hash rezolvă orice coliziuni care apar la calcularea numărului de index.
Căutați operația de date
Operația de căutare este utilizată pentru a căuta valori în tabelul hash folosind numărul de index. Operația de căutare returnează valoarea care este legată de numărul de index de căutare. De exemplu, dacă stocăm valoarea 6 la indexul 2, operația de căutare cu numărul de index 2 va returna valoarea 6.
Operația de ștergere a datelor
Operația de ștergere este utilizată pentru a elimina o valoare dintr-un tabel hash. Pentru a șterge Operase face folosind numărul de index. Odată ce o valoare a fost ștearsă, numărul de index este eliberat. Poate fi folosit pentru a stoca alte valori folosind operația de inserare.
Implementarea tabelului hash cu Python Exemplu
Să ne uităm la un exemplu simplu care calculează valoarea hash a unei chei
def hash_key( key, m):
return key % m
m = 7
print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')
Explicația codului tabelului hash
AICI,
- Definește o funcție hash_key care acceptă parametrii key și m.
- Utilizează o operație simplă de modul pentru a determina valoarea hash
- Definește o variabilă m care este inițializată la valoarea 7. Aceasta este dimensiunea tabelului nostru hash
- Calculează și imprimă valoarea hash de 3
- Calculează și imprimă valoarea hash de 2
- Calculează și imprimă valoarea hash de 9
- Calculează și imprimă valoarea hash de 11
- Calculează și imprimă valoarea hash de 7
Executarea codului de mai sus produce următoarele rezultate.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Dicţionar Exemplu
Python vine cu un tip de date încorporat numit Dicționar. Un dicționar este un exemplu de tabel hash. Stochează valori folosind o pereche de chei și valori. Valorile hash sunt generate automat pentru noi, iar eventualele coliziuni sunt rezolvate pentru noi în fundal.
Următorul exemplu arată cum puteți utiliza un tip de date din dicționar piton 3
employee = {
'name': 'John Doe',
'age': 36,
'position': 'Business Manager.'
}
print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()
print (employee)
AICI,
- Definește o variabilă de dicționar angajat. Numele cheii este folosit pentru a stoca valoarea John Doe, vârsta depozitează 36 de ani, iar poziția stochează valoarea Business Manager.
- Preia valoarea numelui cheii și o tipărește în terminal
- Actualizează valoarea poziției cheie la valoarea Software Engineer
- Imprimă valorile numelui și poziției tastelor
- Șterge toate valorile care sunt stocate în variabila de dicționar angajat
- Tipărește valoarea angajatului
Rularea codului de mai sus produce următoarele rezultate.
The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}
Analiza complexității
Tabelele hash au o complexitate de timp medie de O (1) în cel mai bun scenariu. Complexitatea timpului în cel mai rău caz este O(n). Scenariul cel mai rău apare atunci când multe valori generează aceeași cheie hash și trebuie să rezolvăm coliziunea prin sondare.
Aplicații din lumea reală
În lumea reală, tabelele hash sunt folosite pentru a stoca date pentru
- Baze de date
- tablouri asociative
- Seturi
- Cache memorie
Avantajele tabelelor hash
Iată avantajele/beneficiile utilizării tabelelor hash:
- Tabelele hash au performanțe ridicate la căutarea datelor, inserarea și ștergerea valorilor existente.
- Complexitatea timpului pentru tabelele hash este constantă, indiferent de numărul de elemente din tabel.
- Acestea funcționează foarte bine chiar și atunci când lucrează cu seturi de date mari.
Dezavantajele tabelelor hash
Iată dezavantajele utilizării tabelelor hash:
- Nu puteți utiliza o valoare nulă ca cheie.
- Coliziunile nu pot fi evitate atunci când se generează chei folosind. funcții hash. Coliziunile apar atunci când este generată o cheie care este deja în uz.
- Dacă funcția de hashing are multe coliziuni, acest lucru poate duce la scăderea performanței.
Rezumat
- Tabelele hash sunt folosite pentru a stoca date folosind o pereche de chei și valori.
- O funcție hash folosește un algoritm matematic pentru a calcula valoarea hash.
- O coliziune are loc atunci când aceeași valoare hash este generată pentru mai multe valori.
- Înlănțuirea rezolvă coliziunea prin crearea de liste legate.
- Sondarea rezolvă coliziunea prin găsirea de sloturi goale în tabelul hash.
- Sondarea liniară caută următorul slot liber pentru a stoca valoarea pornind de la slotul în care a avut loc coliziunea.
- Sondarea pătratică folosește expresii polinomiale pentru a găsi următorul slot liber atunci când are loc o coliziune.
- Double hashingul folosește un algoritm de funcție hash secundar pentru a găsi următorul slot liber atunci când are loc o coliziune.
- Tabelele hash au performanțe mai bune în comparație cu alte structuri de date.
- Complexitatea timpului mediu a tabelelor hash este O (1)
- Un tip de date dicționar în python este un exemplu de tabel hash.
- Tabelele hash acceptă operațiuni de inserare, căutare și ștergere.
- O valoare nulă nu poate fi utilizată ca valoare de index.
- Coliziunile nu pot fi evitate în funcțiile hash. O funcție hash bună minimizează numărul de coliziuni care apar pentru a îmbunătăți performanța.
