Hash-tabel in gegevensstructuur: Python-voorbeeld

Inhoudsopgave:

Anonim

Wat is hashen?

Een hash is een waarde met een vaste lengte en wordt gegenereerd met behulp van een wiskundige formule. Hash-waarden worden gebruikt in datacompressie, cryptologie, enz. Bij data-indexering worden hash-waarden gebruikt omdat ze een vaste lengte hebben, ongeacht de waarden die werden gebruikt om ze te genereren. Het zorgt ervoor dat hash-waarden minimale ruimte innemen in vergelijking met andere waarden van verschillende lengtes.

Een hash-functie gebruikt een wiskundig algoritme om de sleutel in een hash om te zetten. Een botsing treedt op wanneer een hash-functie dezelfde hash-waarde produceert voor meer dan één sleutel.

In deze Algoritme-zelfstudie leert u:

  • Wat is hashen?
  • Wat is een hash-tabel?
  • Hash-functies
  • Eigenschappen van een goede hashfunctie
  • Botsing
  • Hashtabelbewerkingen
  • Hash Table Python-voorbeeld
  • Hashtabelcode Uitleg
  • Voorbeeld van een Python-woordenboek
  • Complexiteitsanalyse
  • Real-world applicaties
  • Voordelen van hashtabellen
  • Nadelen van hashtabellen

Wat is een hash-tabel?

Een HASH TABLE is een gegevensstructuur waarin waarden worden opgeslagen met behulp van een paar sleutels en waarden. Elke waarde krijgt een unieke sleutel toegewezen die wordt gegenereerd met behulp van een hash-functie.

De naam van de sleutel wordt gebruikt om toegang te krijgen tot de bijbehorende waarde. Dit maakt het zoeken naar waarden in een hashtabel erg snel, ongeacht het aantal items in de hashtabel.

Hash-functies

Als we bijvoorbeeld werknemersrecords willen opslaan, en elke werknemer wordt uniek geïdentificeerd aan de hand van een werknemersnummer.

We kunnen het personeelsnummer als sleutel gebruiken en de personeelsgegevens als waarde toewijzen.

De bovenstaande benadering vereist extra vrije ruimte in de orde van (m * n 2 ) waarbij de variabele m de grootte van de array is en de variabele n het aantal cijfers voor het personeelsnummer. Deze benadering introduceert een probleem met de opslagruimte.

Een hash-functie lost het bovenstaande probleem op door het personeelsnummer op te halen en het te gebruiken om een ​​hash-integerwaarde, vaste cijfers te genereren en de opslagruimte te optimaliseren. Het doel van een hash-functie is om een ​​sleutel te maken die wordt gebruikt om te verwijzen naar de waarde die we willen opslaan. De functie accepteert de waarde die moet worden opgeslagen en gebruikt vervolgens een algoritme om de waarde van de sleutel te berekenen.

Het volgende is een voorbeeld van een eenvoudige hash-functie

h(k) = k1 % m

HIER,

  • h (k) is de hash-functie die een parameter k accepteert. De parameter k is de waarde waarvoor we de sleutel willen berekenen.
  • k 1 % m is het algoritme voor onze hash-functie waarbij k1 de waarde is die we willen opslaan, en m de grootte van de lijst. We gebruiken de modulus-operator om de sleutel te berekenen.

Voorbeeld

Laten we aannemen dat we een lijst hebben met een vaste grootte van 3 en de volgende waarden

[1,2,3]

We kunnen de bovenstaande formule gebruiken om de posities te berekenen die elke waarde zou moeten innemen.

De volgende afbeelding toont de beschikbare indexen in onze hashtabel.

Stap 1)

Bereken op deze manier de positie die zal worden ingenomen door de eerste waarde

h (1) = 1% 3

= 1

De waarde 1 zal de ruimte op index 1 innemen

Stap 2)

Bereken de positie die wordt ingenomen door de tweede waarde

h (2) = 2% 3

= 2

De waarde 2 zal de ruimte op index 2 innemen

Stap 3)

Bereken de positie die wordt ingenomen door de derde waarde.

h (3) = 3% 3

= 0

De waarde 3 neemt de ruimte op index 0 in beslag

Eindresultaat

Onze ingevulde hashtabel ziet er nu als volgt uit.

Eigenschappen van een goede hashfunctie

Een goede hashfunctie moet de volgende eigenschappen hebben.

  • De formule voor het genereren van de hash moet de waarde van de gegevens gebruiken die in het algoritme moet worden opgeslagen.
  • De hash-functie moet unieke hash-waarden genereren, zelfs voor invoergegevens met hetzelfde aantal.
  • De functie moet het aantal botsingen minimaliseren. Botsingen doen zich voor wanneer dezelfde waarde wordt gegenereerd voor meer dan één waarde.
  • De waarden moeten consistent over alle mogelijke hashes worden verdeeld.

Botsing

Er treedt een botsing op wanneer het algoritme dezelfde hash genereert voor meer dan één waarde.

Laten we naar een voorbeeld kijken.

Stel dat we de volgende lijst met waarden hebben

[3,2,9,11,7]

Laten we aannemen dat de grootte van de hashtabel 7 is, en we zullen de formule (k 1 % m) gebruiken waarbij m de grootte van de hashtabel is.

De volgende tabel toont de hash-waarden die worden gegenereerd.

Sleutel Hash-algoritme (k 1 % m) Hash-waarde
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Zoals we kunnen zien aan de hand van de bovenstaande resultaten, hebben de waarden 2 en 9 dezelfde hash-waarde en kunnen we niet meer dan één waarde op elke positie opslaan.

Het gegeven probleem kan worden opgelost door gebruik te maken van chaining of sondering. In de volgende secties wordt in detail het koppelen en aftasten besproken.

Keten

Chaining is een techniek die wordt gebruikt om het probleem van botsingen op te lossen door gekoppelde lijsten te gebruiken die elk unieke indexen hebben.

De volgende afbeelding visualiseert hoe een aaneengeschakelde lijst eruitziet

Zowel 2 als 9 bezetten dezelfde index, maar ze worden opgeslagen als gekoppelde lijsten. Elke lijst heeft een unieke identificatie.

Voordelen van gekoppelde lijsten

Hieronder volgen de voordelen van gekoppelde lijsten:

  • Gekoppelde lijsten presteren beter bij het invoegen van gegevens omdat de volgorde van invoeging O (1) is.
  • Het is niet nodig om het formaat van een hashtabel te wijzigen die een gekoppelde lijst gebruikt.
  • Het kan gemakkelijk een groot aantal waarden bevatten, zolang er vrije ruimte beschikbaar is.

Onderzoekend

De andere techniek die wordt gebruikt om een ​​botsing op te lossen, is sonderen. Wanneer we de sonderingsmethode gebruiken, kunnen we, als er een botsing optreedt, gewoon verder gaan en een leeg slot zoeken om onze waarde op te slaan.

Hieronder volgen de methoden om te onderzoeken:

Methode Omschrijving
Lineair sonderen Zoals de naam al doet vermoeden, zoekt deze methode lineair naar lege slots, beginnend vanaf de positie waar de botsing plaatsvond en vooruitgaand. Als het einde van de lijst is bereikt en er geen leeg slot is gevonden. Het zoeken begint aan het begin van de lijst.
Kwadratisch sonderen Deze methode maakt gebruik van kwadratische veeltermuitdrukkingen om het volgende beschikbare vrije slot te vinden.
Dubbel hasjen Deze techniek maakt gebruik van een secundair hash-functie-algoritme om het volgende vrije beschikbare slot te vinden.

Als we ons bovenstaande voorbeeld gebruiken, zou de hashtabel na het gebruik van probing er als volgt uitzien:

Hashtabelbewerkingen

Hier zijn de bewerkingen die worden ondersteund door hash-tabellen:

  • Invoegen - deze bewerking wordt gebruikt om een ​​element aan de hashtabel toe te voegen
  • Zoeken - deze bewerking wordt gebruikt om met de sleutel naar elementen in de hashtabel te zoeken
  • Verwijderen - deze bewerking wordt gebruikt om elementen uit de hashtabel te verwijderen

Gegevensbewerking invoegen

De invoegbewerking wordt gebruikt om waarden in de hashtabel op te slaan. Wanneer een nieuwe waarde wordt opgeslagen in de hashtabel, krijgt deze een indexnummer toegewezen. Het indexnummer wordt berekend met behulp van de hash-functie. De hash-functie lost eventuele botsingen op die optreden bij het berekenen van het indexnummer.

Zoek naar gegevensbewerking

De zoekbewerking wordt gebruikt om waarden in de hashtabel op te zoeken met behulp van het indexnummer. De zoekbewerking retourneert de waarde die is gekoppeld aan het zoekindexnummer. Als we bijvoorbeeld de waarde 6 opslaan in index 2, retourneert de zoekbewerking met indexnummer 2 de waarde 6.

Gegevensbewerking verwijderen

De verwijderbewerking wordt gebruikt om een ​​waarde uit een hashtabel te verwijderen. Het verwijderen van de bewerking gebeurt met behulp van het indexnummer. Nadat een waarde is verwijderd, wordt het indexnummer vrijgemaakt. Het kan worden gebruikt om andere waarden op te slaan met behulp van de invoegbewerking.

Hash-tabelimplementatie met Python-voorbeeld

Laten we eens kijken naar een eenvoudig voorbeeld dat de hash-waarde van een sleutel berekent

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

Hashtabelcode Uitleg

HIER,

  1. Definieert een functie hash_key die de parameters key en m accepteert.
  2. Gebruikt een eenvoudige modulusbewerking om de hash-waarde te bepalen
  3. Definieert een variabele m die is geïnitialiseerd op de waarde 7. Dit is de grootte van onze hashtabel
  4. Berekent en drukt de hash-waarde van 3 af
  5. Berekent en drukt de hash-waarde van 2 af
  6. Berekent en drukt de hash-waarde van 9 af
  7. Berekent en drukt de hash-waarde van 11 af
  8. Berekent en drukt de hash-waarde van 7 af

Het uitvoeren van de bovenstaande code levert de volgende resultaten op.

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

Voorbeeld van een Python-woordenboek

Python wordt geleverd met een ingebouwd gegevenstype genaamd Dictionary. Een woordenboek is een voorbeeld van een hashtabel. Het slaat waarden op met behulp van een paar sleutels en waarden. De hash-waarden worden automatisch voor ons gegenereerd en eventuele botsingen worden op de achtergrond voor ons opgelost.

Het volgende voorbeeld laat zien hoe u een woordenboekgegevenstype in python 3 kunt gebruiken

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)

HIER,

  1. Definieert een woordenboekvariabele werknemer. De sleutelnaam wordt gebruikt om de waarde John Doe op te slaan, leeftijd slaat 36 op en positie slaat de waarde Business Manager op.
  2. Haalt de waarde van de sleutelnaam op en drukt deze af in de terminal
  3. Werkt de waarde van de sleutelpositie bij naar de waarde Software Engineer
  4. Drukt de waarden van de naam en positie van de sleutel af
  5. Verwijdert alle waarden die zijn opgeslagen in onze woordenboekvariabele medewerker
  6. Drukt de waarde van werknemer af

Het uitvoeren van de bovenstaande code levert de volgende resultaten op.

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

Complexiteitsanalyse

Hash-tabellen hebben in het beste geval een gemiddelde tijdcomplexiteit van O (1). De tijdcomplexiteit in het slechtste geval is O (n). Het worstcasescenario doet zich voor wanneer veel waarden dezelfde hash-sleutel genereren en we de botsing moeten oplossen door te onderzoeken.

Real-world applicaties

In de echte wereld worden hashtabellen gebruikt om gegevens voor op te slaan

  • Databases
  • Associatieve arrays
  • Sets
  • Geheugencache

Voordelen van hashtabellen

Hier zijn de voor- / voordelen van het gebruik van hashtabellen:

  • Hash-tabellen hebben hoge prestaties bij het opzoeken van gegevens, het invoegen en verwijderen van bestaande waarden.
  • De tijdcomplexiteit voor hashtabellen is constant, ongeacht het aantal items in de tabel.
  • Ze presteren erg goed, zelfs bij het werken met grote datasets.

Nadelen van hashtabellen

Hier zijn de nadelen van het gebruik van hashtabellen:

  • U kunt een null-waarde niet als sleutel gebruiken.
  • Botsingen kunnen niet worden vermeden bij het genereren van sleutels met. hash-functies. Botsingen doen zich voor wanneer een sleutel wordt gegenereerd die al in gebruik is.
  • Als de hashing-functie veel botsingen heeft, kan dit leiden tot prestatieverlies.

Overzicht:

  • Hash-tabellen worden gebruikt om gegevens op te slaan met behulp van een paar sleutels en waarden.
  • Een hash-functie gebruikt een wiskundig algoritme om de hash-waarde te berekenen.
  • Er treedt een botsing op wanneer dezelfde hash-waarde wordt gegenereerd voor meer dan één waarde.
  • Chaining lost botsingen op door gekoppelde lijsten te maken.
  • Proberen lost botsingen op door lege slots in de hashtabel te vinden.
  • Lineair tasten zoekt naar het volgende vrije slot om de waarde op te slaan, beginnend bij het slot waar de botsing plaatsvond.
  • Kwadratische sondering maakt gebruik van veeltermuitdrukkingen om het volgende vrije slot te vinden wanneer er een botsing plaatsvindt.
  • Double hashing gebruikt een secundair hash-functie-algoritme om het volgende vrije slot te vinden wanneer er een botsing plaatsvindt.
  • Hash-tabellen presteren beter in vergelijking met andere datastructuren.
  • De gemiddelde tijdcomplexiteit van hashtabellen is O (1)
  • Een woordenboekgegevenstype in python is een voorbeeld van een hashtabel.
  • Hash-tabellen ondersteunen bewerkingen voor invoegen, zoeken en verwijderen.
  • Een null-waarde kan niet als indexwaarde worden gebruikt.
  • Botsingen kunnen niet worden vermeden in hash-functies. Een goede hash-functie minimaliseert het aantal botsingen dat optreedt om de prestaties te verbeteren.