Hashtabel in gegevensstructuur: Python Voorbeeld

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 bij datacompressie, cryptologie, enz. Bij het indexeren van gegevens worden hash-waarden gebruikt omdat ze een vaste lengte hebben, ongeacht de waarden die zijn gebruikt om ze te genereren. Het zorgt ervoor dat hashwaarden minimale ruimte innemen in vergelijking met andere waarden van verschillende lengtes.

Een hash-functie maakt gebruik van een wiskundig algoritme om de sleutel in een hash om te zetten. Er treedt een botsing op wanneer een hashfunctie dezelfde hashwaarde voor meer dan één sleutel produceert.

Wat is een hashtabel?

A HASH-TAFEL is een gegevensstructuur waarin waarden worden opgeslagen met behulp van een paar sleutels en waarden. Aan elke waarde wordt een unieke sleutel toegewezen die wordt gegenereerd met behulp van een hashfunctie.

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 werknemersgegevens willen opslaan en elke werknemer uniek wordt geïdentificeerd met behulp van een werknemersnummer.

We kunnen het werknemersnummer als sleutel gebruiken en de werknemersgegevens als waarde toekennen.

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

Een hashfunctie lost het bovenstaande probleem op door het werknemersnummer op te halen en dit te gebruiken om een ​​hash-getalwaarde en vaste cijfers te genereren en de opslagruimte te optimaliseren. Het doel van een hashfunctie is om een ​​sleutel te creëren die zal worden 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.

Hieronder volgt een voorbeeld van een eenvoudige hashfunctie

h(k) = k1 % m

HIER,

• h(k) is de hashfunctie die een parameter k accepteert. De parameter k is de waarde waarvoor we de sleutel willen berekenen.
• k₁ % m is het algoritme voor onze hashfunctie waarbij k1 de waarde is die we willen opslaan en m de grootte van de lijst. We gebruiken de modulusoperator 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 onderstaande afbeelding toont de beschikbare indexen in onze hashtabel.

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

h(1) = 1 % 3

= 1

De waarde 1 zal bezetten de ruimte op index 1

Stap 2) Bereken de positie die zal worden ingenomen door de tweede waarde

h(2) = 2 % 3

= 2

De waarde 2 zal bezetten de ruimte op index 2

Stap 3) Bereken de positie die wordt ingenomen door de derde waarde.

h(3) = 3 % 3

= 0

De waarde 3 zal bezetten de ruimte op index 0

Eindresultaat

Onze ingevulde hashtabel ziet er nu als volgt uit.

Kwaliteiten van een goede hashfunctie

Een goede hashfunctie moet de volgende kwaliteiten hebben.

• De formule voor het genereren van de hash moet de waarde van de gegevens gebruiken die in het algoritme moet worden opgeslagen.
• De hashfunctie moet unieke hashwaarden genereren, zelfs voor invoergegevens met dezelfde hoeveelheid.
• De functie moet het aantal botsingen minimaliseren. Botsingen treden op wanneer dezelfde waarde voor meer dan één waarde wordt gegenereerd.
• 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 een voorbeeld bekijken.

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₁ % m) waarbij m de grootte van de hashtabel is.

De volgende tabel toont de hashwaarden die worden gegenereerd.

sleutel	Hash-algoritme (k1 % 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 uit de bovenstaande resultaten kunnen zien, hebben de waarden 2 en 9 dezelfde hashwaarde en kunnen we niet meer dan één waarde op elke positie opslaan.

Het gegeven probleem kan worden opgelost door chaining of probing te gebruiken. De volgende secties bespreken chaining en probing in detail.

chaining

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

De volgende afbeelding visualiseert hoe een gekoppelde lijst eruitziet

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

Voordelen van gekoppelde lijsten

Dit zijn de voordelen van gekoppelde lijsten:

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

Onderzoeken

De andere techniek die wordt gebruikt om botsingen op te lossen is sonderen. Als we de indringende methode gebruiken, kunnen we, als er een botsing plaatsvindt, eenvoudig verder gaan en een leeg slot vinden om onze waarde op te slaan.

De volgende methoden worden gebruikt voor het onderzoeken:

Methode	Beschrijving
Lineair tasten	Zoals de naam al doet vermoeden, zoekt deze methode lineair naar lege slots, beginnend vanaf de positie waar de botsing plaatsvond en verder vooruit. Als het einde van de lijst is bereikt en er geen leeg slot wordt gevonden. Het onderzoek begint aan het begin van de lijst.
Kwadratisch sonderen	Deze methode maakt gebruik van kwadratische polynoomuitdrukkingen om het volgende beschikbare vrije slot te vinden.
Double Hashing	Deze techniek maakt gebruik van een secundair hashfunctie-algoritme om het volgende vrije beschikbare slot te vinden.

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

Hashtabelbewerkingen

Hier zijn de Operaties ondersteund door hashtabellen:

• Invoeging - deze OperaDeze wordt gebruikt om een ​​element aan de hashtabel toe te voegen
• Zoeken - deze OperaDeze wordt gebruikt om met behulp van de sleutel naar elementen in de hashtabel te zoeken
• wissen - deze OperaDeze procedure wordt gebruikt om elementen uit de hashtabel te verwijderen

Gegevensbewerking invoegen

De insert-bewerking wordt gebruikt om waarden op te slaan in de hashtabel. Wanneer een nieuwe waarde wordt opgeslagen in de hashtabel, wordt er een indexnummer aan toegewezen. Het indexnummer wordt berekend met behulp van de hashfunctie. De hashfunctie lost alle botsingen op die optreden bij het berekenen van het indexnummer.

Zoeken naar gegevensbewerking

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

Gegevens verwijderen

De delete-bewerking wordt gebruikt om een ​​waarde uit een hashtabel te verwijderen. Om de Operation wordt gedaan met behulp van het indexnummer. Zodra een waarde is verwijderd, wordt het indexnummer vrijgemaakt. Het kan worden gebruikt om andere waarden op te slaan met behulp van de insert-bewerking.

Implementatie van hashtabellen met Python Voorbeeld

Laten we eens kijken naar een eenvoudig voorbeeld waarin de hashwaarde van een sleutel wordt berekend

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

Uitleg van hashtabelcode

HIER,

1. Definieert een functie hash_key die de parameters key en m accepteert.
2. Gebruikt een eenvoudige modulusbewerking om de hashwaarde 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 hashwaarde van 3 af
5. Berekent en drukt de hashwaarde van 2 af
6. Berekent en drukt de hashwaarde van 9 af
7. Berekent en drukt de hashwaarde van 11 af
8. Berekent en drukt de hashwaarde van 7 af

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

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 Woordenboek voorbeeld

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 hashwaarden worden automatisch voor ons gegenereerd en eventuele botsingen worden op de achtergrond voor ons opgelost.

Het volgende voorbeeld laat zien hoe u een woordenboekgegevenstype kunt gebruiken in 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)

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 sleutelnaam en positie af
5. Verwijdert alle waarden die zijn opgeslagen in onze woordenboekvariabele medewerker
6. Drukt de waarde van de werknemer af

Wanneer u de bovenstaande code uitvoert, krijgt u de volgende resultaten.

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

Complexiteitsanalyse

Hashtabellen hebben een gemiddelde tijdcomplexiteit van O (1) in het beste geval. De slechtste tijdcomplexiteit is O(n). Het slechtste geval doet zich voor wanneer veel waarden dezelfde hashsleutel genereren en we de botsing moeten oplossen door te peilen.

Toepassingen in de echte wereld

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

• databases
• Associatieve arrays
• Sets
• Geheugencache

Voordelen van hashtabellen

Hier volgen de voor- en nadelen van het gebruik van hashtabellen:

• Hashtabellen presteren uitstekend 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 zeer goed, zelfs bij het werken met grote datasets.

Nadelen van hashtabellen

Hier volgen de nadelen van het gebruik van hashtabellen:

• U kunt geen null-waarde als sleutel gebruiken.
• Botsingen kunnen niet worden vermeden bij het genereren van sleutels met behulp van. hash-functies. Botsingen treden op wanneer een sleutel wordt gegenereerd die al in gebruik is.
• Als de hashfunctie veel botsingen kent, kan dit leiden tot prestatievermindering.

Samenvatting

• Hashtabellen worden gebruikt om gegevens op te slaan met behulp van een paar sleutels en waarden.
• Een hashfunctie gebruikt een wiskundig algoritme om de hashwaarde te berekenen.
• Er treedt een botsing op wanneer dezelfde hashwaarde voor meer dan één waarde wordt gegenereerd.
• Chaining lost botsingen op door gekoppelde lijsten te maken.
• Probing lost botsingen op door lege slots in de hashtabel te vinden.
• Lineair sonderen zoekt naar het volgende vrije slot om de waarde op te slaan, beginnend bij het slot waar de botsing plaatsvond.
• Kwadratisch sonderen maakt gebruik van polynoomuitdrukkingen om het volgende vrije slot te vinden wanneer er een botsing optreedt.
• Double hashing gebruikt een secundair hashfunctie-algoritme om het volgende vrije slot te vinden wanneer er een botsing optreedt.
• Hashtabellen presteren beter in vergelijking met andere datastructuren.
• De gemiddelde tijdscomplexiteit van hashtabellen is O (1)
• Een woordenboekgegevenstype in Python is een voorbeeld van een hashtabel.
• Hashtabellen ondersteunen invoeg-, zoek- en verwijderbewerkingen.
• Een nulwaarde kan niet als indexwaarde worden gebruikt.
• Bij hashfuncties kunnen botsingen niet worden vermeden. Een goede hashfunctie minimaliseert het aantal botsingen dat optreedt om de prestaties te verbeteren.