Hash-tabell i datastruktur: Python-eksempel

Innholdsfortegnelse:

Anonim

Hva er Hashing?

En hash er en verdi som har en fast lengde, og den genereres ved hjelp av en matematisk formel. Hash-verdier brukes i datakomprimering, kryptologi, etc. I dataindeksering brukes hash-verdier fordi de har fast lengdestørrelse uavhengig av verdiene som ble brukt til å generere dem. Det gjør hashverdier for å oppta minimal plass sammenlignet med andre verdier av varierende lengde.

En hash-funksjon benytter en matematisk algoritme for å konvertere nøkkelen til en hash. En kollisjon oppstår når en hashfunksjon produserer den samme hashverdien for mer enn en nøkkel.

I denne algoritmeopplæringen lærer du:

  • Hva er Hashing?
  • Hva er et Hash-bord?
  • Hash-funksjoner
  • Egenskapene til en god hash-funksjon
  • Kollisjon
  • Hash-bordoperasjoner
  • Hash Table Python Eksempel
  • Hash Tabell Kode Forklaring
  • Python Dictionary Eksempel
  • Kompleksitetsanalyse
  • Virkelige applikasjoner
  • Fordeler med hasjbord
  • Ulemper med hasjbord

Hva er et Hash-bord?

EN HASH TABLE er en datastruktur som lagrer verdier ved hjelp av et par nøkler og verdier. Hver verdi tildeles en unik nøkkel som genereres ved hjelp av en hash-funksjon.

Navnet på nøkkelen brukes til å få tilgang til den tilknyttede verdien. Dette gjør det raskt å søke etter verdier i en hash-tabell, uavhengig av antall elementer i hash-tabellen.

Hash-funksjoner

For eksempel hvis vi ønsker å lagre ansattes poster, og hver ansatt er unikt identifisert ved hjelp av et ansattnummer.

Vi kan bruke ansattnummeret som nøkkel og tilordne medarbeiderdataene som verdien.

Ovennevnte tilnærming vil kreve ekstra ledig plass i størrelsesorden (m * n 2 ) der variabelen m er størrelsen på matrisen, og variabelen n er antall sifre for ansattnummeret. Denne tilnærmingen introduserer et lagringsplassproblem.

En hash-funksjon løser ovennevnte problem ved å hente ansattens nummer og bruke det til å generere et hash-heltall, faste sifre og optimalisere lagringsplass. Hensikten med en hash-funksjon er å lage en nøkkel som skal brukes til å referere til verdien vi vil lagre. Funksjonen aksepterer verdien som skal lagres, og bruker deretter en algoritme for å beregne verdien på nøkkelen.

Følgende er et eksempel på en enkel hash-funksjon

h(k) = k1 % m

HER,

  • h (k) er hash-funksjonen som godtar en parameter k. Parameteren k er verdien vi vil beregne nøkkelen for.
  • k 1 % m er algoritmen for vår hash-funksjon der k1 er verdien vi vil lagre, og m er størrelsen på listen. Vi bruker moduloperatøren til å beregne nøkkelen.

Eksempel

La oss anta at vi har en liste med en fast størrelse på 3 og følgende verdier

[1,2,3]

Vi kan bruke formelen ovenfor for å beregne posisjonene som hver verdi skal innta.

Følgende bilde viser tilgjengelige indekser i hash-tabellen vår.

Trinn 1)

Beregn posisjonen som blir okkupert av den første verdien slik

h (1) = 1% 3

= 1

Verdien 1 vil oppta plassen på indeks 1

Steg 2)

Beregn posisjonen som blir okkupert av den andre verdien

h (2) = 2% 3

= 2

Verdien 2 vil oppta plassen på indeks 2

Trinn 3)

Beregn posisjonen som blir okkupert av den tredje verdien.

h (3) = 3% 3

= 0

Verdien 3 vil oppta plassen på indeks 0

Endelig resultat

Vår utfylte hash-tabell vil nå være som følger.

Egenskapene til en god hash-funksjon

En god hashfunksjon skal ha følgende egenskaper.

  • Formelen for generering av hash skal bruke dataens verdi for å bli lagret i algoritmen.
  • Hashfunksjonen skal generere unike hashverdier selv for inndata som har samme mengde.
  • Funksjonen skal minimere antall kollisjoner. Kollisjoner oppstår når den samme verdien genereres for mer enn én verdi.
  • Verdiene må fordeles konsekvent over hele mulige hashes.

Kollisjon

En kollisjon oppstår når algoritmen genererer den samme hash for mer enn en verdi.

La oss se på et eksempel.

Anta at vi har følgende verdiliste

[3,2,9,11,7]

La oss anta at størrelsen på hash-tabellen er 7, og vi vil bruke formelen (k 1 % m) der m er størrelsen på hash-tabellen.

Tabellen nedenfor viser hashverdiene som skal genereres.

Nøkkel Hash-algoritme (k 1 % m) Hash verdi
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Som vi kan se fra resultatene ovenfor, har verdiene 2 og 9 samme hash-verdi, og vi kan ikke lagre mer enn en verdi på hver posisjon.

Det gitte problemet kan løses ved å bruke kjetting eller sondering. De følgende avsnittene diskuterer kjetting og sondering i detalj.

Kjetting

Kjetting er en teknikk som brukes til å løse problemet med kollisjon ved hjelp av koblede lister som hver har unike indekser.

Følgende bilde visualiserer hvordan en lenket liste ser ut

Både 2 og 9 har samme indeks, men de er lagret som koblede lister. Hver liste har en unik identifikator.

Fordeler med lenke lister

Følgende er fordelene med kjedede lister:

  • Kjedede lister har bedre ytelse når du setter inn data fordi rekkefølgen på innsatsen er O (1).
  • Det er ikke nødvendig å endre størrelse på en hash-tabell som bruker en lenket liste.
  • Det kan lett imøtekomme et stort antall verdier så lenge ledig plass er tilgjengelig.

Sonder

Den andre teknikken som brukes til å løse kollisjon, er sondering. Når en kollisjon skjer, når vi bruker sonderingsmetoden, kan vi bare gå videre og finne et tomt spor for å lagre verdien vår.

Følgende er metodene for sondering:

Metode Beskrivelse
Lineær sondering Akkurat som navnet antyder, søker denne metoden etter tomme spor lineært fra posisjonen der kollisjonen skjedde og beveger seg fremover. Hvis slutten av listen er nådd og ingen tomme spor blir funnet. Sonderingen begynner på begynnelsen av listen.
Kvadratisk sondering Denne metoden bruker kvadratiske polynomiske uttrykk for å finne neste tilgjengelige gratis spilleautomat.
Dobbel hasj Denne teknikken bruker en sekundær hashfunksjonsalgoritme for å finne neste gratis tilgjengelige spor.

Ved å bruke eksemplet ovenfor, vil hash-tabellen etter bruk av sondering se ut som følger:

Hash-bordoperasjoner

Her er operasjonene som støttes av Hash-tabeller:

  • Innsetting - denne operasjonen brukes til å legge til et element i hash-tabellen
  • Søker - denne operasjonen brukes til å søke etter elementer i hashtabellen ved hjelp av tasten
  • Slette - denne operasjonen brukes til å slette elementer fra hash-tabellen

Setter inn datadrift

Innsettingsoperasjonen brukes til å lagre verdier i hash-tabellen. Når en ny verdi er lagret i hashtabellen, tildeles den et indeksnummer. Indeksnummeret beregnes ved hjelp av hash-funksjonen. Hashfunksjonen løser eventuelle kollisjoner som oppstår når indeksnummeret beregnes.

Søk etter datadrift

Søkeoperasjonen brukes til å slå opp verdier i hash-tabellen ved hjelp av indeksnummeret. Søkeoperasjonen returnerer verdien som er knyttet til søkeindeksnummeret. Hvis vi for eksempel lagrer verdien 6 i indeks 2, vil søkeoperasjonen med indeksnummer 2 returnere verdien 6.

Slett datadrift

Sletteoperasjonen brukes til å fjerne en verdi fra en hash-tabell. For å slette operasjonen gjøres ved hjelp av indeksnummeret. Når en verdi er slettet, blir indeksnummeret gratis. Den kan brukes til å lagre andre verdier ved hjelp av innsettingsoperasjonen.

Hash-tabellimplementering med Python-eksempel

La oss se på et enkelt eksempel som beregner hashverdien til en nøkkel

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 Tabell Kode Forklaring

HER,

  1. Definerer en funksjon hash_key som godtar parameternøkkelen og m.
  2. Bruker en enkel moduloperasjon for å bestemme hashverdien
  3. Definerer en variabel m som er initialisert til verdien 7. Dette er størrelsen på hash-tabellen vår
  4. Beregner og skriver ut hash-verdien på 3
  5. Beregner og skriver ut hash-verdien på 2
  6. Beregner og skriver ut hasjverdien på 9
  7. Beregner og skriver ut hash-verdien på 11
  8. Beregner og skriver ut hasjverdien på 7

Å utføre koden ovenfor gir 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

Python Dictionary Eksempel

Python kommer med en innebygd datatype kalt ordbok. En ordbok er et eksempel på en hash-tabell. Den lagrer verdier ved hjelp av et par nøkler og verdier. Hashverdiene genereres automatisk for oss, og eventuelle kollisjoner løses for oss i bakgrunnen.

Følgende eksempel viser hvordan du kan bruke en ordbokdatatype 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 ordbokvariabel ansatt. Nøkkelnavnet brukes til å lagre verdien John Doe, lagre alder 36, og posisjonslagre verdien Business Manager.
  2. Henter verdien av nøkkelnavnet og skriver det ut i terminalen
  3. Oppdaterer verdien av nøkkelposisjonen til verdien Software Engineer
  4. Skriver ut verdiene til tastenes navn og posisjon
  5. Sletter alle verdiene som er lagret i vår ordbokvariabel ansatt
  6. Skriver ut verdien av ansatt

Å kjøre ovennevnte kode gir 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 gjennomsnittlig tidskompleksitet på O (1) i beste fall. Tidskompleksiteten i verste fall er O (n). Verste fall oppstår når mange verdier genererer den samme hash-nøkkelen, og vi må løse kollisjonen ved å undersøke.

Virkelige applikasjoner

I den virkelige verden brukes hashtabeller til å lagre data for

  • Databaser
  • Assosiative matriser
  • Settene
  • Minnebuffer

Fordeler med hasjbord

Her er fordeler / fordeler ved å bruke hash-tabeller:

  • Hash-tabeller har høy ytelse når du leter etter data, setter inn og sletter eksisterende verdier.
  • Tidskompleksiteten for hasjtabeller er konstant, uavhengig av antall elementer i tabellen.
  • De fungerer veldig bra selv når du arbeider med store datasett.

Ulemper med hasjbord

Her er ulempene med å bruke hashtabeller:

  • Du kan ikke bruke en nullverdi som nøkkel.
  • Kollisjoner kan ikke unngås når du genererer nøkler ved hjelp av. hash-funksjoner. Kollisjoner oppstår når en nøkkel som allerede er i bruk genereres.
  • Hvis hashing-funksjonen har mange kollisjoner, kan dette føre til redusert ytelse.

Sammendrag:

  • Hash-tabeller brukes til å lagre data ved hjelp av et par nøkler og verdier.
  • En hash-funksjon bruker en matematisk algoritme for å beregne hash-verdien.
  • En kollisjon oppstår når den samme hashverdien genereres for mer enn én verdi.
  • Kjetting løser kollisjon ved å lage koblede lister.
  • Sondering løser kollisjon ved å finne tomme spor i hasjbordet.
  • Lineær sondering søker etter neste ledige spor for å lagre verdien fra sporet der kollisjonen skjedde.
  • Quadratic sondering bruker polynomiske uttrykk for å finne neste ledige spor når en kollisjon inntreffer.
  • Dobbel hashing bruker en sekundær hashfunksjonsalgoritme for å finne neste ledige spor når det oppstår en kollisjon.
  • Hash-tabeller har bedre ytelse sammenlignet med andre datastrukturer.
  • Gjennomsnittlig tidskompleksitet for hasjetabeller er O (1)
  • En ordbokdatatype i python er et eksempel på en hash-tabell.
  • Hash-tabeller støtter innsetting, søk og slett operasjoner.
  • En nullverdi kan ikke brukes som indeksverdi.
  • Kollisjoner kan ikke unngås i hashfunksjoner. En god hash-funksjon minimerer antall kollisjoner som oppstår for å forbedre ytelsen.