Hashing verwijst naar het proces van het genereren van een uitvoer van een vaste grootte uit een invoer van variabele grootte met behulp van de wiskundige formules die bekend staan ​​als hash-functies. Deze techniek bepaalt een index of locatie voor de opslag van een item in een datastructuur.

Behoefte aan hash-datastructuur

De hoeveelheid gegevens op internet groeit elke dag exponentieel, waardoor het moeilijk wordt om deze allemaal effectief op te slaan. Bij de dagelijkse programmering is deze hoeveelheid gegevens misschien niet zo groot, maar toch moet deze eenvoudig en efficiënt worden opgeslagen, toegankelijk en verwerkt. Een veel voorkomende datastructuur die voor een dergelijk doel wordt gebruikt, is de Array-datastructuur.

Nu rijst de vraag: als Array er al was, wat was dan de noodzaak voor een nieuwe datastructuur! Het antwoord hierop ligt in het woord efficiëntie. Hoewel het opslaan in Array duurt O(1) tijd, het zoeken erin duurt minstens O(logboek n) tijd. Deze tijd lijkt klein, maar voor een grote dataset kan dit veel problemen veroorzaken en dit maakt op zijn beurt de Array-datastructuur inefficiënt.

Dus nu zijn we op zoek naar een datastructuur die de data kan opslaan en daarin in constante tijd kan zoeken, d.w.z. in O(1) tijd. Dit is hoe de Hashing-datastructuur in het spel kwam. Met de introductie van de Hash-datastructuur is het nu mogelijk om eenvoudig gegevens in constante tijd op te slaan en deze ook in constante tijd op te halen.

Componenten van hashing

Er zijn grofweg drie componenten van hashing:

1. Sleutel: A Sleutel kan elke string of geheel getal zijn dat als invoer wordt ingevoerd in de hashfunctie, de techniek die een index of locatie bepaalt voor opslag van een item in een datastructuur.
2. Hash-functie: De hash-functie ontvangt de invoersleutel en retourneert de index van een element in een array die een hashtabel wordt genoemd. De index staat bekend als de hash-index .
3. Hash-tabel: Hashtabel is een gegevensstructuur die sleutels aan waarden toewijst met behulp van een speciale functie die een hashfunctie wordt genoemd. Hash slaat de gegevens op een associatieve manier op in een array waarbij elke gegevenswaarde zijn eigen unieke index heeft.

Componenten van hashing

Wat is een botsing?

Het hashingproces genereert een klein getal voor een grote sleutel, dus er is een mogelijkheid dat twee sleutels dezelfde waarde kunnen produceren. De situatie waarin de nieuw ingevoegde sleutel wordt toegewezen aan een reeds bezette sleutel, en deze moet worden afgehandeld met behulp van een of andere technologie voor het afhandelen van botsingen.

Botsing in Hashing

Voordelen van hashen in datastructuren

• Ondersteuning van sleutel-waarde: Hashing is ideaal voor het implementeren van sleutelwaardedatastructuren.
• Snel ophalen van gegevens: Hashing zorgt voor snelle toegang tot elementen met constante tijdscomplexiteit.
• Efficiëntie: Invoeg-, verwijder- en zoekbewerkingen zijn zeer efficiënt.
• Vermindering van geheugengebruik: Hashing vereist minder geheugen omdat het een vaste ruimte toewijst voor het opslaan van elementen.
• Schaalbaarheid: Hashing presteert goed met grote datasets, waarbij een constante toegangstijd wordt gehandhaafd.
• Beveiliging en encryptie: Hashing is essentieel voor veilige gegevensopslag en integriteitsverificatie.

Voor meer informatie over Hashing verwijzen wij u naar de Inleiding tot hashing - Tutorials voor gegevensstructuur en algoritmen