Tabel hash în structura datelor: Python Exemplu

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*n²) 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 prin obținerea numărului de angajat și utilizarea acestuia 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 utilizată pentru a face referire la valoarea pe care dorim să o stocăm. Funcția acceptă valoarea care urmează să fie 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.
• k₁ % 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 (k₁ % m) unde m este dimensiunea tabelului hash.

Următorul tabel arată valorile hash care vor fi generate.

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:

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)}')

Tabel Hash Code Explicație

AICI,

1. Definește o funcție hash_key care acceptă parametrii key și m.
2. Utilizează o operație simplă de modul pentru a determina valoarea hash
3. Definește o variabilă m care este inițializată la valoarea 7. Aceasta este dimensiunea tabelului nostru hash
4. Calculează și imprimă valoarea hash de 3
5. Calculează și imprimă valoarea hash de 2
6. Calculează și imprimă valoarea hash de 9
7. Calculează și imprimă valoarea hash de 11
8. 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,

1. 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.
2. Preia valoarea numelui cheii și o tipărește în terminal
3. Actualizează valoarea poziției cheie la valoarea Software Engineer
4. Imprimă valorile numelui și poziției tastelor
5. Șterge toate valorile care sunt stocate în variabila de dicționar angajat
6. 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.

Întrebări frecvente