Hashing är en grundläggande datastruktur som effektivt lagrar och hämtar data på ett sätt som möjliggör snabb åtkomst. Det innebär att mappa data till ett specifikt index i en hashtabell med hjälp av en hash-funktion som möjliggör snabb hämtning av information baserat på dess nyckel. Denna metod används ofta i databaser, c värkande system och olika programmeringsapplikationer för att optimera sök- och hämtningsoperationer.

Datastrukturer – Hashing

Innehållsförteckning

• Hash-funktion
• Vad är en Hash-kollision?
• Tekniker för kollisionsupplösning
• Tillämpningar av hashing
• Lätt problem med hashing
• Medelstort problem med hashing
• Svårt problem med hashing

Hur det fungerar:

1. Hash funktion: Du tillhandahåller dina dataobjekt i hashfunktionen.
2. Hash-kod: Hashfunktionen knackar data och ger en unik hashkod.
3. Hashtabell: Hashkoden pekar dig sedan till en specifik plats i hashtabellen.

Hash-funktion

De hash-funktion är en funktion som tar en nyckel och returnerar en index in i hashtabell . Målet med en hashfunktion är att fördela nycklar jämnt över hashtabellen, vilket minimerar kollisioner (när två nycklar mappar till samma index).

Vanliga hashfunktioner inkluderar:

• Uppdelningsmetod: Nyckel % Hash-tabellstorlek
• Multiplikationsmetod: (Key * Konstant) % Hash-tabellstorlek
• Universal hashing: En familj av hashfunktioner utformade för att minimera kollisioner

Vad är en Hash-kollision?

En hashkollision uppstår när två olika nycklar mappas till samma index i en hashtabell. Detta kan hända även med en bra hashfunktion, speciellt om hashtabellen är full eller nycklarna liknar varandra.

Orsaker till Hash-kollisioner:

• Dålig hashfunktion: En hashfunktion som inte fördelar nycklar jämnt över hashtabellen kan leda till fler kollisioner.
• Hög belastningsfaktor: En hög belastningsfaktor (förhållandet mellan nycklar och hashtabellstorlek) ökar sannolikheten för kollisioner.
• Liknande nycklar: Nycklar som är lika i värde eller struktur är mer benägna att kollidera.

Tekniker för kollisionsupplösning

Det finns två typer av kollisionsupplösningstekniker:

1. Öppna adressering:
   • Linjär sondering: Sök efter en tom plats sekventiellt
   • Kvadratisk sondering: Sök efter en tom plats med en kvadratisk funktion
2. Stängd adress:
   • Kedja: Lagra kolliderande nycklar i en länkad lista eller binärt sökträd vid varje index
   • Cuckoo Hashing: Använd flera hash-funktioner för att distribuera nycklar

Tillämpningar av hashing

Hash-tabeller används i en mängd olika applikationer, inklusive:

• Databaser: Lagra och hämta data baserat på unika nycklar
• Cachning: Lagring av data som ofta används för snabbare hämtning
• Symboltabeller: Mappa identifierare till deras värden i programmeringsspråk
• Nätverksrouting: Bestämma den bästa vägen för datapaket

Vad är Hashing?

Indexmappning (eller trivial hashing)

Separat kedja för kollisionshantering

Öppna adressering för kollisionshantering

Dubbel hashing

Belastningsfaktor och omhasning

Lätt problem med hashing

• Ta reda på om en array är en delmängd av en annan array
• Union och skärningspunkt mellan två länkade listor
• Med tanke på en matris A[] och ett tal x, kontrollera efter par i A[] med summa som x
• Maximalt avstånd mellan två förekomster av samma element i arrayen
• Räkna maximala poäng på samma rad
• Det vanligaste elementet i en array
• Hitta det enda repetitiva elementet mellan 1 till n-1
• Hur kontrollerar man om två givna set är osammanhängande?
• Icke-överlappande summa av två uppsättningar
• Kontrollera om två arrayer är lika eller inte
• Hitta saknade element i ett intervall
• Minsta antal delmängder med distinkta element
• Ta bort minsta antal element så att inget gemensamt element finns i båda arrayerna
• Hitta par med given summa så att element i par är i olika rader
• Räkna par med given summa
• Räkna fyrdubblar från fyra sorterade arrayer vars summa är lika med ett givet värde x
• Sortera element efter frekvens
• Hitta alla par (a, b) i en matris så att a % b = k
• Gruppera ord med samma uppsättning tecken
• k:te distinkta (eller icke-repeterande) element i en array.

Medelstort problem med hashing

• Hitta resväg från en given lista med biljetter
• Hitta antal anställda under varje anställd
• Längsta undergrupp med summan delbar med k
• Hitta den största undergruppen med 0 summa
• Längst Ökande på varandra följande följd
• Räkna distinkta element i varje fönster av storlek k
• Hitta subarray med given summa | Set 2 (hanterar negativa tal)
• Implementering av vår egen Hash-tabell med Separat Chaining i Java
• Implementering av egen Hash-tabell med Open Addressing Linear Probing i C++
• Minsta insättningar för att bilda ett palindrom med permutationer tillåtna
• Maximal möjlig skillnad mellan två delmängder av en array
• Sortering med trivial hash-funktion
• Minsta undergrupp med k distinkta nummer

Svårt problem med hashing

• Klona ett binärt träd med slumpmässiga pekare
• Största subarray med lika många 0:or och 1:or
• Alla unika trillingar som summerar till ett givet värde
• Palindrome Substring Queries
• Områdesfrågor för frekvenser för arrayelement
• Element som ska läggas till så att alla element i ett intervall finns i array
• Cuckoo Hashing – Worst case O(1) Lookup!
• Räkna undermatriser som har totalt distinkta element samma som originalmatrisen
• Maximal array från två givna arrayer håller samma ordning
• Hitta summan av alla unika delmatrissummor för en given matris.
• Recamans sekvens
• Längden på längsta strikta bitoniska undersekvens
• Hitta alla dubbletter av underträd
• Ta reda på om det finns en rektangel i binär matris med hörn som 1

Snabblänkar :

• 'Övningsproblem' på hashing
• Topp 20 Hashing-teknikbaserade intervjufrågor
• 'Videos' på Hashing