Vad är Hashing?
En hash är ett värde som har en fast längd och genereras med en matematisk formel. Hash-värden används vid datakomprimering, kryptologi etc. Vid dataindexering används hash-värden eftersom de har fast längdstorlek oavsett vilka värden som användes för att generera dem. Det gör att hash-värden upptar minimalt utrymme jämfört med andra värden av varierande längd.
En hash-funktion använder en matematisk algoritm för att konvertera nyckeln till en hash. En kollision inträffar när en hash-funktion ger samma hash-värde för mer än en tangent.
I denna algoritmhandledning lär du dig:
- Vad är Hashing?
- Vad är en Hash-tabell?
- Hash-funktioner
- Kvaliteter av en bra hashfunktion
- Kollision
- Hash-tabelloperationer
- Hash Table Python Exempel
- Hash-tabellkodförklaring
- Python Dictionary Exempel
- Komplexitetsanalys
- Verkliga applikationer
- Fördelar med hashtabeller
- Nackdelar med hashbord
Vad är en Hash-tabell?
En hash-tabell är en datastruktur som lagrar värden med användning av ett par av nycklar och värden. Varje värde tilldelas en unik nyckel som genereras med en hash-funktion.
Nyckelns namn används för att komma åt dess tillhörande värde. Detta gör att sökning efter värden i en hashtabell väldigt snabbt, oavsett antalet objekt i hashtabellen.
Hash-funktioner
Till exempel om vi vill lagra medarbetarregister och varje anställd identifieras unikt med hjälp av ett anställningsnummer.
Vi kan använda medarbetarnumret som nyckel och tilldela medarbetardata som värde.
Ovanstående tillvägagångssätt kräver extra ledigt utrymme i storleksordningen (m * n 2 ) där variabeln m är storleken på matrisen och variabeln n är antalet siffror för anställdsnummer. Detta tillvägagångssätt introducerar ett lagringsutrymme problem.
En hash-funktion löser ovanstående problem genom att få anställd nummer och använda det för att generera ett hash-heltal, fasta siffror och optimera lagringsutrymme. Syftet med en hash-funktion är att skapa en nyckel som används för att referera till det värde som vi vill lagra. Funktionen accepterar värdet som ska sparas och använder sedan en algoritm för att beräkna nyckelns värde.
Följande är ett exempel på en enkel hash-funktion
h(k) = k1 % m
HÄR,
- h (k) är hashfunktionen som accepterar en parameter k. Parametern k är det värde som vi vill beräkna nyckeln för.
- k 1 % m är algoritmen för vår hash-funktion där k1 är det värde vi vill lagra och m är storleken på listan. Vi använder moduloperatorn för att beräkna nyckeln.
Exempel
Låt oss anta att vi har en lista med en fast storlek på 3 och följande värden
[1,2,3]
Vi kan använda formeln ovan för att beräkna positionerna som varje värde ska inta.
Följande bild visar tillgängliga index i vår hash-tabell.
Steg 1)
Beräkna positionen som kommer att upptas av det första värdet så
h (1) = 1% 3
= 1
Värdet 1 upptar utrymmet i index 1
Steg 2)
Beräkna positionen som kommer att upptas av det andra värdet
h (2) = 2% 3
= 2
Värdet 2 upptar utrymmet i index 2
Steg 3)
Beräkna positionen som kommer att upptas av det tredje värdet.
h (3) = 3% 3
= 0
Värdet 3 upptar utrymmet i index 0
Slutresultat
Vår ifyllda hash-tabell blir nu följande.
Kvaliteter av en bra hashfunktion
En bra hashfunktion bör ha följande egenskaper.
- Formeln för att generera hash bör använda datans värde för att lagras i algoritmen.
- Hashfunktionen ska generera unika hashvärden även för inmatade data som har samma mängd.
- Funktionen ska minimera antalet kollisioner. Kollisioner inträffar när samma värde genereras för mer än ett värde.
- Värdena måste fördelas konsekvent över hela möjliga hash.
Kollision
En kollision inträffar när algoritmen genererar samma hash för mer än ett värde.
Låt oss titta på ett exempel.
Antag att vi har följande värdelista
[3,2,9,11,7]
Låt oss anta att storleken på hashtabellen är 7, och vi kommer att använda formeln (k 1 % m) där m är storleken på hashtabellen.
Följande tabell visar hash-värdena som kommer att genereras.
| Nyckel | Hashalgoritm (k 1 % m) | Hash-värde |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Som vi kan se från ovanstående resultat har värdena 2 och 9 samma hash-värde och vi kan inte lagra mer än ett värde vid varje position.
Det givna problemet kan lösas genom att antingen använda kedjning eller sondering. I följande avsnitt diskuteras kedjning och sondering i detalj.
Kedjning
Kedjning är en teknik som används för att lösa problemet med kollision genom att använda länkade listor som har unika index.
Följande bild visualiserar hur en kedjad lista ser ut
Både 2 och 9 upptar samma index, men de lagras som länkade listor. Varje lista har en unik identifierare.
Fördelar med kedjade listor
Följande är fördelarna med kedjade listor:
- Kedjade listor har bättre prestanda när du infogar data eftersom ordningen på infogningen är O (1).
- Det är inte nödvändigt att ändra storlek på en hashtabell som använder en kedjad lista.
- Det rymmer enkelt ett stort antal värden så länge det finns ledigt utrymme.
Sonder
Den andra tekniken som används för att lösa kollision är sonderande. När en kollision inträffar kan vi helt enkelt gå vidare och hitta en tom plats för att lagra vårt värde när vi använder sonderingsmetoden.
Följande är metoderna för sondering:
| Metod | Beskrivning |
| Linjär sondering | Precis som namnet antyder söker den här metoden efter tomma spår linjärt från och med den position där kollisionen inträffade och framåt. Om slutet på listan nås och ingen tom plats finns. Sonderna börjar i början av listan. |
| Kvadratisk sondering | Denna metod använder kvadratiska polynomuttryck för att hitta nästa tillgängliga lediga spelautomat. |
| Dubbel hasning | Denna teknik använder en sekundär hashfunktionsalgoritm för att hitta nästa lediga lediga plats. |
Med hjälp av vårt ovanstående exempel visas hashtabellen efter att ha använt sondering enligt följande:
Hash-tabelloperationer
Här är de funktioner som stöds av Hash-tabeller:
- Insättning - den här åtgärden används för att lägga till ett element i hashtabellen
- Sökning - den här åtgärden används för att söka efter element i hashtabellen med hjälp av tangenten
- Radering - den här åtgärden används för att radera element från hashtabellen
Infogning av data
Infoga operationen används för att lagra värden i hash-tabellen. När ett nytt värde lagras i hashtabellen tilldelas det ett indexnummer. Indexnumret beräknas med hjälp av hash-funktionen. Hashfunktionen löser alla kollisioner som uppstår vid beräkning av indexnummer.
Sök efter datahantering
Sökningen används för att leta upp värden i hashtabellen med hjälp av indexnumret. Sökoperationen returnerar värdet som är länkat till sökindexnumret. Om vi till exempel lagrar värdet 6 vid index 2, returnerar sökningen med indexnummer 2 värdet 6.
Ta bort datahantering
Radera operationen används för att ta bort ett värde från en hash-tabell. För att radera operationen görs med indexnumret. När ett värde har raderats görs indexnumret gratis. Den kan användas för att lagra andra värden med insättningsoperationen.
Hash-tabellimplementering med Python-exempel
Låt oss titta på ett enkelt exempel som beräknar hashvärdet för en nyckel
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-tabellkodförklaring
HÄR,
- Definierar en funktion hash_key som accepterar parameternyckeln och m.
- Använder en enkel moduloperation för att bestämma hashvärdet
- Definierar en variabel m som initialiseras till värdet 7. Detta är storleken på vår hash-tabell
- Beräknar och skriver ut hashvärdet 3
- Beräknar och skriver ut hashvärdet 2
- Beräknar och skriver ut hashvärdet 9
- Beräknar och skriver ut hashvärdet 11
- Beräknar och skriver ut hashvärdet 7
Att köra ovanstående kod ger följande resultat.
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 Exempel
Python levereras med en inbyggd datatyp som heter Dictionary. En ordbok är ett exempel på en hashtabell. Den lagrar värden med ett par nycklar och värden. Hashvärdena genereras automatiskt för oss och eventuella kollisioner löses för oss i bakgrunden.
Följande exempel visar hur du kan använda en ordlistadatatyp 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)
HÄR,
- Definierar en ordboksvariabel anställd. Nyckelnamnet används för att lagra värdet John Doe, ålder lagrar 36 och position lagrar värdet Business Manager.
- Hämtar värdet på nyckelnamnet och skriver ut det i terminalen
- Uppdaterar värdet på nyckelpositionen till värdet Software Engineer
- Skriver ut värdena för tangenternas namn och position
- Raderar alla värden som är lagrade i vår ordboksvariabel anställd
- Skriver ut anställdens värde
Att köra ovanstående kod ger följande resultat.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Komplexitetsanalys
Hash-tabeller har en genomsnittlig tidskomplexitet av O (1) i bästa fall. Den värsta fallkomplexiteten är O (n). Det värsta fallet inträffar när många värden genererar samma hash-nyckel, och vi måste lösa kollisionen genom att sondera.
Verkliga applikationer
I den verkliga världen används hashtabeller för att lagra data för
- Databaser
- Associerande matriser
- Uppsättningar
- Minnescache
Fördelar med hashtabeller
Här är fördelar / fördelar med att använda hashtabeller:
- Hash-tabeller har hög prestanda när man letar efter data, infogar och tar bort befintliga värden.
- Tidskomplexiteten för hashtabeller är konstant oavsett antalet objekt i tabellen.
- De fungerar mycket bra även när du arbetar med stora datamängder.
Nackdelar med hashbord
Här är nackdelarna med att använda hashtabeller:
- Du kan inte använda ett nollvärde som en nyckel.
- Kollisioner kan inte undvikas när du genererar nycklar med. hashfunktioner. Kollisioner inträffar när en nyckel som redan används genereras.
- Om hashing-funktionen har många kollisioner kan detta leda till att prestandan minskar.
Sammanfattning:
- Hash-tabeller används för att lagra data med ett par nycklar och värden.
- En hash-funktion använder en matematisk algoritm för att beräkna hashvärdet.
- En kollision inträffar när samma hashvärde genereras för mer än ett värde.
- Kedjning löser kollision genom att skapa länkade listor.
- Sondering löser kollision genom att hitta tomma spår i hashtabellen.
- Linjär sondering söker efter nästa lediga plats för att lagra värdet från den plats där kollisionen inträffade.
- Kvadratisk sondering använder polynomiska uttryck för att hitta nästa lediga plats när en kollision inträffar.
- Double hashing använder en sekundär hashfunktionsalgoritm för att hitta nästa lediga plats när en kollision inträffar.
- Hash-tabeller har bättre prestanda jämfört med andra datastrukturer.
- Den genomsnittliga tidskomplexiteten för hashtabeller är O (1)
- En ordlistadatatyp i python är ett exempel på en hashtabell.
- Hash-tabeller stöder insättning, sökning och radering.
- Ett nollvärde kan inte användas som ett indexvärde.
- Kollisioner kan inte undvikas i hashfunktioner. En bra hashfunktion minimerar antalet kollisioner som uppstår för att förbättra prestandan.