Hash-tabel i datastruktur: Python-eksempel

Indholdsfortegnelse:

Anonim

Hvad er Hashing?

En hash er en værdi, der har en fast længde, og den genereres ved hjælp af en matematisk formel. Hash-værdier bruges til datakomprimering, kryptologi osv. I dataindeksering bruges hash-værdier, fordi de har en fast længdestørrelse uanset de værdier, der blev brugt til at generere dem. Det gør hash-værdier til at optage minimal plads sammenlignet med andre værdier af varierende længde.

En hash-funktion anvender en matematisk algoritme til at konvertere nøglen til en hash. En kollision opstår, når en hash-funktion producerer den samme hash-værdi for mere end en nøgle.

I denne algoritmevejledning lærer du:

  • Hvad er Hashing?
  • Hvad er et Hash-bord?
  • Hash-funktioner
  • Kvaliteterne ved en god hash-funktion
  • Kollision
  • Hash-bordoperationer
  • Hash Table Python Eksempel
  • Hash-tabelkode Forklaring
  • Eksempel på Python-ordbog
  • Kompleksitetsanalyse
  • Virkelige applikationer
  • Fordele ved hash-tabeller
  • Ulemper ved hash-tabeller

Hvad er et Hash-bord?

En HASH TABLE er en datastruktur, der gemmer værdier ved hjælp af et par nøgler og værdier. Hver værdi tildeles en unik nøgle, der genereres ved hjælp af en hash-funktion.

Navnet på nøglen bruges til at få adgang til dens tilknyttede værdi. Dette gør søgning efter værdier i en hash-tabel meget hurtig, uanset antallet af elementer i hash-tabellen.

Hash-funktioner

For eksempel, hvis vi vil gemme medarbejderoptegnelser, og hver medarbejder identificeres entydigt ved hjælp af et medarbejdernummer.

Vi kan bruge medarbejdernummeret som nøgle og tildele medarbejderdata som værdi.

Ovenstående fremgangsmåde kræver ekstra ledig plads i størrelsesordenen (m * n 2 ), hvor variablen m er størrelsen på arrayet, og variablen n er antallet af cifre for medarbejdernummeret. Denne tilgang introducerer et lagerpladsproblem.

En hash-funktion løser ovenstående problem ved at hente medarbejdernummeret og bruge det til at generere en hash-heltal, faste cifre og optimering af lagerplads. Formålet med en hash-funktion er at oprette en nøgle, der bruges til at henvise til den værdi, vi vil gemme. Funktionen accepterer den værdi, der skal gemmes, og bruger derefter en algoritme til at beregne nøglens værdi.

Følgende er et eksempel på en simpel hash-funktion

h(k) = k1 % m

HER,

  • h (k) er hash-funktionen, der accepterer en parameter k. Parameteren k er den værdi, som vi vil beregne nøglen til.
  • k 1 % m er algoritmen for vores hash-funktion, hvor k1 er den værdi, vi vil gemme, og m er størrelsen på listen. Vi bruger modulusoperatøren til at beregne nøglen.

Eksempel

Lad os antage, at vi har en liste med en fast størrelse på 3 og følgende værdier

[1,2,3]

Vi kan bruge ovenstående formel til at beregne de positioner, som hver værdi skal indtage.

Det følgende billede viser de tilgængelige indekser i vores hash-tabel.

Trin 1)

Beregn den position, der vil blive optaget af den første værdi som sådan

h (1) = 1% 3

= 1

Værdien 1 optager pladsen på indeks 1

Trin 2)

Beregn den position, der vil blive optaget af den anden værdi

h (2) = 2% 3

= 2

Værdien 2 optager pladsen på indeks 2

Trin 3)

Beregn den position, der vil blive besat af den tredje værdi.

h (3) = 3% 3

= 0

Værdien 3 optager pladsen på indeks 0

Endelig resultat

Vores udfyldte hash-tabel vil nu være som følger.

Kvaliteterne ved en god hash-funktion

En god hash-funktion skal have følgende kvaliteter.

  • Formlen til generering af hash skal bruge dataets værdi til at blive gemt i algoritmen.
  • Hash-funktionen skal generere unikke hash-værdier, selv for inputdata, der har samme mængde.
  • Funktionen skal minimere antallet af kollisioner. Kollisioner opstår, når den samme værdi genereres for mere end en værdi.
  • Værdierne skal fordeles konsekvent over hele mulige hashes.

Kollision

En kollision opstår, når algoritmen genererer den samme hash til mere end en værdi.

Lad os se på et eksempel.

Antag, at vi har følgende liste over værdier

[3,2,9,11,7]

Lad os antage, at størrelsen på hash-tabellen er 7, og vi bruger formlen (k 1 % m), hvor m er størrelsen på hash-tabellen.

Den følgende tabel viser de hash-værdier, der genereres.

Nøgle Hash-algoritme (k 1 % m) Hash værdi
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Som vi kan se af ovenstående resultater, har værdierne 2 og 9 den samme hash-værdi, og vi kan ikke gemme mere end en værdi på hver position.

Det givne problem kan løses ved enten at bruge kæde eller sondering. De følgende afsnit diskuterer kæde og sondering i detaljer.

Lænkning

Kædning er en teknik, der bruges til at løse problemet med kollision ved hjælp af sammenkædede lister, der hver har unikke indekser.

Følgende billede visualiserer, hvordan en lænket liste ser ud

Både 2 og 9 indtager det samme indeks, men de gemmes som sammenkædede lister. Hver liste har en unik identifikator.

Fordele ved lænkede lænker

Følgende er fordelene ved lænkede lister:

  • Kædede lister har bedre ydeevne, når der indsættes data, fordi rækkefølgen for indsættelsen er O (1).
  • Det er ikke nødvendigt at ændre størrelsen på en hash-tabel, der bruger en lænket liste.
  • Det kan nemt rumme et stort antal værdier, så længe der er ledig plads.

Undersøgelse

Den anden teknik, der bruges til at løse kollision, er sondering. Når der anvendes sonderingsmetoden, kan vi simpelthen gå videre og finde en tom plads til at gemme vores værdi, hvis der opstår en kollision.

Følgende er metoder til sondering:

Metode Beskrivelse
Lineær sondering Ligesom navnet antyder, søger denne metode efter tomme slots lineært startende fra den position, hvor kollisionen opstod og bevæger sig fremad. Hvis slutningen af ​​listen er nået, og der ikke findes nogen tom plads. Sonderingen starter i begyndelsen af ​​listen.
Kvadratisk sondering Denne metode bruger kvadratiske polynomiske udtryk for at finde den næste tilgængelige gratis slot.
Dobbelt hash Denne teknik bruger en sekundær hash-funktionsalgoritme til at finde den næste gratis tilgængelige plads.

Ved hjælp af vores ovenstående eksempel vises hash-tabellen efter brug af sondering som følger:

Hash-bordoperationer

Her er operationerne understøttet af Hash-tabeller:

  • Indsættelse - denne operation bruges til at tilføje et element til hash-tabellen
  • Søgning - denne operation bruges til at søge efter elementer i hash-tabellen ved hjælp af tasten
  • Sletning - denne handling bruges til at slette elementer fra hash-tabellen

Indsættelse af datafunktion

Indsætningsfunktionen bruges til at gemme værdier i hash-tabellen. Når en ny værdi er gemt i hash-tabellen, tildeles den et indeksnummer. Indeksnummeret beregnes ved hjælp af hash-funktionen. Hash-funktionen løser eventuelle kollisioner, der opstår ved beregning af indeksnummeret.

Søg efter datadrift

Søgningen bruges til at slå værdier op i hash-tabellen ved hjælp af indeksnummeret. Søgeoperationen returnerer den værdi, der er knyttet til søgeindeksnummeret. Hvis vi f.eks. Gemmer værdien 6 ved indeks 2, returnerer søgningen med indeksnummer 2 værdien 6.

Slet datafunktion

Sletningsfunktionen bruges til at fjerne en værdi fra en hash-tabel. For at slette operationen udføres ved hjælp af indeksnummeret. Når en værdi er slettet, gøres indeksnummeret frit. Det kan bruges til at gemme andre værdier ved hjælp af indsættelsesfunktionen.

Hash-tabelimplementering med Python-eksempel

Lad os se på et simpelt eksempel, der beregner hash-værdien for en nøgle

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

Hash-tabelkode Forklaring

HER,

  1. Definerer en funktion hash_key, der accepterer parameternøglen og m.
  2. Bruger en simpel moduloperation til at bestemme hashværdien
  3. Definerer en variabel m, der initialiseres til værdien 7. Dette er størrelsen på vores hash-tabel
  4. Beregner og udskriver hashværdien 3
  5. Beregner og udskriver hashværdien 2
  6. Beregner og udskriver hashværdien 9
  7. Beregner og udskriver hashværdien 11
  8. Beregner og udskriver hashværdien 7

Udførelse af ovenstående kode giver følgende resultater.

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

Eksempel på Python-ordbog

Python leveres med en indbygget datatype kaldet ordbog. En ordbog er et eksempel på en hash-tabel. Den gemmer værdier ved hjælp af et par nøgler og værdier. Hashværdierne genereres automatisk for os, og eventuelle kollisioner løses for os i baggrunden.

Følgende eksempel viser, hvordan du kan bruge en ordbogsdatatype i 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)

HER,

  1. Definerer en ordbogvariabel medarbejder. Nøglenavnet bruges til at gemme værdien John Doe, lagre alder 36 og placere værdien Business Manager.
  2. Henter værdien af ​​nøglenavnet og udskriver det i terminalen
  3. Opdaterer værdien af ​​nøglepositionen til værdien Softwareingeniør
  4. Udskriver værdierne for tasterne navn og placering
  5. Sletter alle de værdier, der er gemt i vores ordbogvariabel medarbejder
  6. Udskriver medarbejderens værdi

Kørsel af ovenstående kode giver følgende resultater.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Kompleksitetsanalyse

Hash-tabeller har en gennemsnitlig tidskompleksitet på O (1) i bedste tilfælde. Den værst tænkelige tidskompleksitet er O (n). Det værst tænkelige scenarie opstår, når mange værdier genererer den samme hash-nøgle, og vi skal løse kollisionen ved at undersøge.

Virkelige applikationer

I den virkelige verden bruges hash-tabeller til at gemme data til

  • Databaser
  • Associerende arrays
  • Sæt
  • Hukommelsescache

Fordele ved hash-tabeller

Her er fordele / fordele ved at bruge hash-tabeller:

  • Hash-tabeller har høj ydeevne, når man søger på data, indsætter og sletter eksisterende værdier.
  • Tidskompleksiteten for hash-tabeller er konstant uanset antallet af elementer i tabellen.
  • De klarer sig meget godt, selv når du arbejder med store datasæt.

Ulemper ved hash-tabeller

Her er ulemper ved at bruge hash-tabeller:

  • Du kan ikke bruge en nulværdi som en nøgle.
  • Kollisioner kan ikke undgås, når du genererer nøgler ved hjælp af. hash-funktioner. Kollisioner opstår, når der genereres en nøgle, der allerede er i brug.
  • Hvis hashing-funktionen har mange kollisioner, kan dette føre til præstationsfald.

Resumé:

  • Hash-tabeller bruges til at gemme data ved hjælp af et par nøgler og værdier.
  • En hash-funktion bruger en matematisk algoritme til at beregne hash-værdien.
  • En kollision opstår, når den samme hashværdi genereres til mere end en værdi.
  • Kædning løser kollision ved at oprette sammenkædede lister.
  • Probing løser kollision ved at finde tomme slots i hash-tabellen.
  • Lineær sondering søger efter den næste gratis plads til at gemme værdien startende fra den plads, hvor kollisionen opstod.
  • Kvadratisk sondering bruger polynomiske udtryk for at finde den næste ledige plads, når der opstår en kollision.
  • Dobbelt hashing bruger en sekundær hash-funktionsalgoritme til at finde den næste gratis slot, når der opstår en kollision.
  • Hash-tabeller har bedre ydeevne sammenlignet med andre datastrukturer.
  • Den gennemsnitlige tidskompleksitet for hash-tabeller er O (1)
  • En ordbogsdatatype i python er et eksempel på en hash-tabel.
  • Hash-tabeller understøtter indsættelse, søgning og sletning.
  • En nulværdi kan ikke bruges som en indeksværdi.
  • Kollisioner kan ikke undgås i hash-funktioner. En god hash-funktion minimerer antallet af kollisioner, der opstår for at forbedre ydelsen.