Hashing is een fundamentele datastructuur die gegevens efficiënt opslaat en ophaalt op een manier die snelle toegang mogelijk maakt. Het gaat om het toewijzen van gegevens aan een specifieke index in een hashtabel met behulp van a hash-functie waarmee snel informatie kan worden opgehaald op basis van de sleutel. Deze methode wordt vaak gebruikt in databases, C pijnlijke systemen en verschillende programmeertoepassingen om zoek- en ophaaloperaties te optimaliseren.
Gegevensstructuren – Hashing
Inhoudsopgave
- Hash-functie
- Wat is een hash-botsing?
- Technieken voor het oplossen van botsingen
- Toepassingen van hashing
- Eenvoudig probleem met hashen
- Middelgroot probleem met hashing
- Moeilijk probleem met hashen
Hoe het werkt:
- Hash-functie: U geeft uw gegevensitems op in de hashfunctie.
- Hash-code: De hash-functie verwerkt de gegevens en geeft een unieke hash-code.
- Hash-tabel: De hashcode verwijst u vervolgens naar een specifieke locatie binnen de hashtabel.
Hash-functie
De hash-functie is een functie waaraan a moet doorgegeven worden sleutel en retourneert een inhoudsopgave in de hash-tabel . Het doel van een hashfunctie is om sleutels gelijkmatig over de hashtabel te verdelen, waardoor botsingen worden geminimaliseerd (wanneer twee sleutels naar dezelfde index verwijzen).
Veel voorkomende hashfuncties zijn onder meer:
- Verdeelmethode: Sleutel% hashtabelgrootte
- Vermenigvuldigingsmethode: (Sleutel * Constant) % Grootte hashtabel
- Universele hashing: Een familie hashfuncties die zijn ontworpen om botsingen te minimaliseren
Wat is een hash-botsing?
Een hash-botsing treedt op wanneer twee verschillende sleutels zijn toegewezen aan dezelfde index in een hashtabel. Dit kan zelfs gebeuren met een goede hashfunctie, vooral als de hashtabel vol is of de sleutels vergelijkbaar zijn.
Oorzaken van hash-botsingen:
- Slechte hashfunctie: Een hashfunctie die de sleutels niet gelijkmatig over de hashtabel verdeelt, kan tot meer botsingen leiden.
- Hoge belastingsfactor: Een hoge belastingsfactor (verhouding tussen sleutels en hashtabelgrootte) vergroot de kans op botsingen.
- Vergelijkbare sleutels: Sleutels die qua waarde of structuur vergelijkbaar zijn, zullen eerder botsen.
Technieken voor het oplossen van botsingen
Er zijn twee soorten technieken voor het oplossen van botsingen:
- Open adressering:
- Lineair sonderen: Zoek achtereenvolgens naar een leeg slot
- Kwadratisch sonderen: Zoek naar een leeg slot met behulp van een kwadratische functie
- Gesloten adressering:
- Keten: Sla botsende sleutels op in een gekoppelde lijst of binaire zoekboom bij elke index
- Koekoek hashen: Gebruik meerdere hashfuncties om sleutels te distribueren
Toepassingen van hashing
Hashtabellen worden gebruikt in een breed scala aan toepassingen, waaronder:
- Databases: Gegevens opslaan en ophalen op basis van unieke sleutels
- Caching: Opslaan van veelgebruikte gegevens voor sneller ophalen
- Symbooltabellen: ID's toewijzen aan hun waarden in programmeertalen
- Netwerkroutering: Bepalen van het beste pad voor datapakketten
Wat is hashen?
Eenvoudig probleem met hashen
- Zoek of een array een subset is van een andere array
- Unie en kruispunt van twee gekoppelde lijsten
- Gegeven een array A[] en een getal x, controleer dan op een paar in A[] met som x
- Maximale afstand tussen twee exemplaren van hetzelfde element in de array
- Tel het maximale aantal punten op dezelfde lijn
- Meest voorkomende element in een array
- Zoek het enige repetitieve element tussen 1 en n-1
- Hoe controleer ik of twee gegeven sets disjunct zijn?
- Niet-overlappende som van twee sets
- Controleer of twee arrays gelijk zijn of niet
- Vind ontbrekende elementen van een bereik
- Minimumaantal subsets met verschillende elementen
- Verwijder het minimumaantal elementen zodat er geen gemeenschappelijk element in beide arrays bestaat
- Vind paren met een gegeven som, zodat de elementen van het paar zich in verschillende rijen bevinden
- Tel paren met gegeven som
- Tel verviervoudigingen uit vier gesorteerde arrays waarvan de som gelijk is aan een gegeven waarde x
- Sorteer elementen op frequentie
- Vind alle paren (a, b) in een array zodat a% b = k
- Groepeer woorden met dezelfde reeks tekens
- k-de onderscheidend (of niet-herhalend) element in een array.
Middelgroot probleem met hashing
- Zoek het reisplan uit een bepaalde lijst met tickets
- Zoek het aantal werknemers onder elke werknemer
- Langste subarray waarvan de som deelbaar is door k
- Zoek de grootste subarray met een som van 0
- Langste toenemende opeenvolgende deelreeks
- Tel verschillende elementen in elk venster van maat k
- Zoek subarray met gegeven som | Set 2 (verwerkt negatieve getallen)
- Implementatie van onze eigen hashtabel met afzonderlijke ketens in Java
- Implementatie van een eigen hashtabel met open adressering Linear Probing in C++
- Minimale invoegingen om een palindroom te vormen met toegestane permutaties
- Maximaal mogelijk verschil tussen twee subsets van een array
- Sorteren met behulp van triviale hash-functie
- Kleinste subarray met k verschillende getallen
Moeilijk probleem met hashen
- Kloon een binaire boom met willekeurige verwijzingen
- Grootste subarray met een gelijk aantal nullen en enen
- Alle unieke drielingen die samen een bepaalde waarde vormen
- Palindroomsubstringquery's
- Bereikquery's voor frequenties van array-elementen
- Elementen die moeten worden toegevoegd zodat alle elementen van een bereik aanwezig zijn in de array
- Cuckoo Hashing – In het slechtste geval O(1) opzoeken!
- Tel subarrays met totaal verschillende elementen die hetzelfde zijn als de originele array
- Maximale array van twee gegeven arrays waarbij de volgorde hetzelfde blijft
- Zoek de som van alle unieke subarraysom voor een bepaalde array.
- De reeks van Recaman
- Lengte van de langste strikte bitonische deelreeks
- Vind alle dubbele substructuren
- Zoek of er een rechthoek in de binaire matrix is met hoeken als 1
Snelle links:
- ‘Oefenproblemen’ over hashing
- Top 20 op hashtechnieken gebaseerde interviewvragen
- ‘Video’s’ over hashen
Aanbevolen:
- Leer datastructuur en algoritmen | DSA-zelfstudie