Hash Table în structura datelor: Exemplu Python

Cuprins:

Anonim

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 utilizate deoarece au dimensiuni fixe de lungime, indiferent de valorile care au fost utilizate pentru a le genera. Face valori hash pentru a ocupa 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 apare atunci când o funcție hash produce aceeași valoare hash pentru mai multe taste.

În acest tutorial Algoritm, veți învăța:

  • Ce este Hashing?
  • Ce este o masă Hash?
  • Funcții Hash
  • Calitățile unei bune funcții hash
  • Coliziune
  • Operații de masă Hash
  • Hash Table Python Exemplu
  • Explicarea codului tabelului Hash
  • Exemplu de dicționar Python
  • Analiza complexității
  • Aplicații din lumea reală
  • Avantajele meselor de hash
  • Dezavantaje ale tabelelor hash

Ce este o masă Hash?

Un TABEL HASH 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ă utilizând o funcție hash.

Numele cheii este utilizat pentru a accesa valoarea sa asociată. 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 și 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 (m * n 2 ) în care variabila m este dimensiunea matricei, 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 de angajat și folosindu-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 utilizată 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.
  • k 1 % m este algoritmul pentru funcția noastră hash unde k1 este valoarea pe care dorim să o stocăm, iar m este dimensiunea listei. Folosim operatorul de 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 fiecare valoare ar trebui să le ocupe.

Următoarea imagine prezintă indexurile disponibile în tabelul nostru de hash.

Pasul 1)

Calculați poziția care va fi ocupată de prima valoare așa

h (1) = 1% 3

= 1

Valoarea 1 va ocupa spațiul de pe indexul 1

Pasul 2)

Calculați poziția care va fi ocupată de a doua valoare

h (2) = 2% 3

= 2

Valoarea 2 va ocupa spațiul de pe indexul 2

Pasul 3)

Calculați poziția care va fi ocupată de a treia valoare.

h (3) = 3% 3

= 0

Valoarea 3 va ocupa spațiul de pe indexul 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 pentru a fi stocate î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 se generează aceeași valoare pentru mai multe valori.
  • Valorile trebuie distribuite în mod consecvent între toate hashurile posibile.

Coliziune

O coliziune apare 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 1 % m) unde m este dimensiunea tabelului hash.

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

Cheie Algoritm Hash (k 1 % m) Valoare 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 multe valori la fiecare poziție.

Problema dată poate fi rezolvată fie prin înlănțuire, fie prin sondare. Următoarele secțiuni discută în detaliu înlănțuirea și sondarea.

Înlănțuirea

Înlănțuirea este o tehnică care este utilizată pentru a rezolva problema coliziunii utilizând liste legate care au fiecare indexuri unice.

Următoarea imagine vizualizează 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.

Avantajele listelor înlănțuite

Următoarele sunt avantajele 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ă utilizată pentru rezolvarea coliziunii este sondarea. Atunci când se utilizează metoda de sondare, dacă are loc o coliziune, putem pur și simplu să mergem mai departe și să găsim un spațiu gol pentru a ne stoca valoarea.

Următoarele sunt metodele de sondare:

Metodă Descriere
Sondare liniară La fel cum sugerează și numele, această metodă caută sloturi goale liniar începând de la poziția în care s-a produs coliziunea și mergând înainte. Dacă se ajunge la sfârșitul listei și nu se găsește niciun slot gol. Sondajul începe la începutul listei.
Sondare quadratică Această metodă utilizează expresii polinomiale pătratice pentru a găsi următorul slot liber disponibil.
Hashing dublu Această tehnică folosește un algoritm de funcție hash secundar pentru a găsi următorul slot disponibil gratuit.

Utilizând exemplul nostru de mai sus, tabelul hash după utilizarea sondării va apărea după cum urmează:

Operații de masă Hash

Iată, Operațiile acceptate de tabelele Hash:

  • Inserare - această operațiune este utilizată pentru a adăuga un element în tabelul hash
  • Căutare - această operație este utilizată pentru a căuta elemente în tabelul hash folosind tasta
  • Ștergere - această operațiune este utilizată pentru a șterge elemente din tabelul hash

Introducerea operației de date

Operațiunea 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 index. Numărul index este calculat utilizând funcția hash. Funcția hash rezolvă orice coliziuni care apar atunci când se calculează numărul de index.

Căutați operațiunea de date

Operația de căutare este utilizată pentru a căuta valori în tabelul hash folosind numărul de index. Operațiunea de căutare returnează valoarea care este legată de numărul indexului de căutare. De exemplu, dacă stocăm valoarea 6 la indexul 2, operațiunea de căutare cu numărul index 2 va returna valoarea 6.

Ștergeți operația de date

Operația de ștergere este utilizată pentru a elimina o valoare dintr-un tabel hash. Pentru a șterge Operațiunea se face folosind numărul de index. Odată ce o valoare a fost ștearsă, numărul indexului este liber. Poate fi folosit pentru a stoca alte valori folosind operația de inserare.

Implementarea tabelului Hash cu exemplu Python

Să vedem un exemplu simplu care calculează valoarea hash a unei chei

def hash_key( key, m):return key % mm = 7print(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)}')

Explicarea codului tabelului Hash

AICI,

  1. Definește o funcție hash_key care acceptă parametrii cheie și m.
  2. Folosește 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 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Exemplu de dicționar Python

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 și orice coliziuni sunt rezolvate pentru noi în fundal.

Următorul exemplu arată cum puteți utiliza un tip de date din dicționar în python 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 stochează 36 de ani, iar poziția stochează valoarea Business Manager.
  2. Preluează valoarea numelui cheii și o imprimă în terminal
  3. Actualizează valoarea poziției cheie la valoarea Software Engineer
  4. Tipărește valorile și numele tastelor
  5. Șterge toate valorile stocate în variabila noastră 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 medie în timp de O (1) în cel mai bun caz. Cea mai rea situație de timp este O (n). Cel mai rău scenariu 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 stocarea datelor

  • Baze de date
  • Tablouri asociative
  • Seturi
  • Memorie cache

Avantajele meselor de hash

Iată care sunt avantajele / avantajele utilizării tabelelor hash:

  • Tabelele Hash au performanțe ridicate atunci când caută date, inserează și șterge valorile existente.
  • Complexitatea timpului pentru tabelele hash este constantă indiferent de numărul de articole din tabel.
  • Au performanțe foarte bune chiar și atunci când lucrează cu seturi de date mari.

Dezavantaje ale tabelelor hash

Aici, există dezavantaje ale 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 utilizată.
  • Dacă funcția de hash are multe coliziuni, acest lucru poate duce la scăderea performanței.

Rezumat:

  • Tabelele Hash sunt utilizate 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 apare atunci când aceeași valoare hash este generată pentru mai multe valori.
  • Înlănțuirea rezolvă coliziunea prin crearea listelor legate.
  • Sondarea rezolvă coliziunea găsind sloturi goale în tabelul hash.
  • Sondajul liniar caută următorul slot gratuit pentru a stoca valoarea începând de la slotul în care s-a produs coliziunea.
  • Sondarea quadratică folosește expresii polinomiale pentru a găsi următorul slot liber atunci când are loc o coliziune.
  • Hash-ul dublu 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 medie a timpului tabelelor hash este O (1)
  • Un tip de date din dicționar în python este un exemplu de tabel hash.
  • Tabelele Hash acceptă operațiile de inserare, căutare și ștergere.
  • O valoare nulă nu poate fi utilizată ca valoare 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.