Hashing in DBMS: statische en dynamische hashtechnieken

⚡ Slimme samenvatting

Hashing in DBMS is een techniek die de schijflocatie van een record rechtstreeks berekent op basis van de sleutel, zonder een index te doorlopen. Een hashfunctie koppelt zoektermen aan databuckets, en statische of dynamische hashing bepaalt hoe die buckets groeien.

⚡ Kernidee: Een hashfunctie zet een sleutel om in een bucketadres, waardoor een record in één stap wordt gevonden in plaats van via een indexdoorloop.
🪣 Gegevensbucket: De geheugenlocatie, of opslageenheid, waar records met dezelfde hashwaarde worden geplaatst.
📌 Statische hashing: Het aantal buckets is vast, dus een bepaalde sleutel verwijst altijd naar hetzelfde adres.
📈 Dynamische hashing: Buckets worden naar behoefte toegevoegd en verwijderd naarmate het datavolume verandert.
???? Botsing: Twee sleutels kaartping naar dezelfde bucket, opgelost door middel van probing, rehashing of chaining.
🔍 Beste voor: Exacte overeenkomsten bij het zoeken op basis van de zoekterm, waarbij hashing beter presteert dan geordende indexering.
📊 Afweging: Geordende indexering is het meest geschikt voor bereikquery's; hashing is het meest geschikt voor constante invoegingen en puntzoekacties.

Meer informatie

Wat is hashen in DBMS?

In DBMS is hashing een techniek om direct de locatie van gewenste gegevens op de schijf te zoeken zonder gebruik te maken van een indexstructuur. De hashingmethode wordt gebruikt om items in een database te indexeren en op te halen, omdat het sneller is om een specifiek item te zoeken met behulp van de kortere gehashte sleutel in plaats van de oorspronkelijke waarde. Gegevens worden opgeslagen in de vorm van datablokken waarvan het adres wordt gegenereerd door een hashfunctie toe te passen; de geheugenlocatie waar deze records zijn opgeslagen, staat bekend als een record. datablok of databucket.

Waarom hebben we hashing nodig?

Hieronder volgen enkele situaties in een DBMS waarin u de hashmethode moet toepassen:

Bij een enorme databasestructuur is het lastig om alle indexwaarden op alle niveaus te doorzoeken en vervolgens het juiste gegevensblok te bereiken om de gewenste gegevens te verkrijgen.
Hashing wordt gebruikt om items in een database te indexeren en op te halen, omdat het sneller is om naar een specifiek item te zoeken met behulp van de kortere gehashte sleutel dan met de oorspronkelijke waarde.
Hashing is een ideale methode om de exacte locatie van een gegevensrecord op de schijf te berekenen zonder gebruik te maken van een indexstructuur.
Het is ook een nuttige techniek voor het implementeren van woordenboeken.

Belangrijke terminologieën in hashing

Hieronder volgen belangrijke termen die bij hashing worden gebruikt:

Gegevensbucket: Databuckets zijn geheugenlocaties waar de gegevens worden opgeslagen. Ze worden ook wel opslageenheden genoemd.
Sleutel: a DBMS-sleutel Een rij- of tuple-attribuut is een kenmerk of een set kenmerken waarmee je een rij (tuple) in een relatie (tabel) kunt identificeren.
Hash-functie: een kaartping Een functie die alle zoektermen koppelt aan het adres waar de daadwerkelijke records zich bevinden.
Lineaire sondering: Een vast interval tussen de metingen. Bij deze methode wordt het eerstvolgende beschikbare datablok gebruikt om de nieuwe record in te voeren, in plaats van de oude record te overschrijven.
Kwadratische peiling: Dit helpt bij het bepalen van het nieuwe bucketadres door de opeenvolgende uitvoer van een kwadratisch polynoom op te tellen bij de startwaarde die door de oorspronkelijke berekening is verkregen.
Hash-index: Het adres van het datablok. Een hashfunctie kan een eenvoudige wiskundige functie zijn of een complexe.
Double hashen: Een methode die in hashtabellen wordt gebruikt om botsingen op te lossen door een tweede hashfunctie toe te passen.
Emmeroverloop: De situatie waarbij een bucket overloopt, wordt een botsing genoemd. Dit is een fatale fase voor elke statische hashfunctie.

Soorten hashtechnieken

In databasesystemen zijn er hoofdzakelijk twee soorten hashingtechnieken:

Statische hasj
Dynamisch hashen

De twee verschillen voornamelijk in de vraag of het aantal emmers vaststaat, zoals in de volgende twee paragrafen wordt uitgelegd.

Statische hasj

Bij statische hashing blijft het adres van de resulterende databucket altijd hetzelfde.

Als u dus een adres genereert voor bijvoorbeeld... Student_ID = 10 gebruikmakend van de hashfunctie mod(3), zal het resulterende bucketadres altijd zijn 1Je zult dus geen verandering zien in het bucketadres.

Bij de statische hashmethode blijft het aantal databuckets in het geheugen dus altijd constant.

Statische hashfuncties

Een record invoegen: Wanneer een nieuw record in de tabel moet worden ingevoegd, genereert u een adres ervoor met behulp van de hash-sleutel. Zodra het adres is gegenereerd, wordt het record op die locatie opgeslagen.
Zoeken: Wanneer je het record moet ophalen, wordt dezelfde hashfunctie gebruikt om het adres van de bucket te achterhalen waar de gegevens zijn opgeslagen.
Een record verwijderen: Met behulp van de hashfunctie haal je eerst de record op die je wilt verwijderen, en vervolgens verwijder je de record van dat adres in het geheugen.

Statische hashing wordt verder onderverdeeld in:

Open hashing
Gesloten hashing

Hashing openen

Bij de open hashing-methode wordt, in plaats van het oudere record te overschrijven, het eerstvolgende beschikbare datablok gebruikt om het nieuwe record in te voeren. Deze methode staat ook bekend als lineaire probing.

Bijvoorbeeld, A2 is een nieuw record dat u wilt invoegen. De hashfunctie genereert adres 222, maar dit adres is al in gebruik door een andere waarde. Daarom zoekt het systeem naar de volgende gegevensbucket, 501, en wijst A2 daaraan toe.

Hoe open hashing werkt met lineaire probing. — Hoe open hash werkt

Gesloten hashing

Bij de gesloten hashmethode wordt, wanneer buckets vol zijn, een nieuwe bucket toegewezen voor dezelfde hash en wordt het resultaat gekoppeld aan het vorige resultaat.

Dynamisch hashen

Dynamische hashing biedt een mechanisme waarmee databuckets dynamisch en op aanvraag worden toegevoegd en verwijderd. Bij deze hashingmethode helpt de hashfunctie bij het creëren van een groot aantal waarden, en de structuur groeit of krimpt mee met de data. Dit maakt het uitermate geschikt voor tabellen waarvan de grootte niet van tevoren kan worden voorspeld, waar statische hashing ofwel ruimte zou verspillen ofwel tot overloop zou leiden.

Verschil tussen geordende indexering en hashing

Hieronder staan de belangrijkste verschillen tussen indexering en hashing:

Kenmerken	Geordende indexering	Hashing
Opslaan van adres	De adressen in het geheugen worden gesorteerd op basis van een sleutelwaarde die de primaire sleutel wordt genoemd.	Adressen worden altijd gegenereerd met behulp van een hash-functie op de sleutelwaarde.
Prestaties	Het kan afnemen naarmate de hoeveelheid gegevens toeneemt, omdat de gegevens gesorteerd worden opgeslagen en elke invoeging, verwijdering of update de volgorde ervan verandert.	De prestaties zijn het beste bij het constant toevoegen en verwijderen van gegevens. Voor een zeer grote database worden de kosten voor het onderhoud van hashbestanden echter hoger.
Gebruik voor	Bij voorkeur voor het ophalen van gegevens binnen een bepaald bereik.	Ideaal voor het ophalen van een specifiek record op basis van de zoekterm, en werkt alleen goed wanneer de hashfunctie op de zoekterm is toegepast.
Geheugen management	Veel ongebruikte datablokken ontstaan door verwijderings- en updatebewerkingen en kunnen niet opnieuw worden gebruikt; daarom is regelmatig onderhoud noodzakelijk.	Bij statische en dynamische hashing wordt het geheugen altijd beheerd en wordt bucket-overflow afgehandeld om de mogelijkheden van statische hashing uit te breiden.

Kortom, kies in de aangegeven volgorde. indexering voor bereikquery's en hashing voor exacte overeenkomsten op de sleutel.

Wat is botsing?

Een hashbotsing is een situatie waarbij de resulterende hashes van twee of meer items in de dataset ten onrechte naar dezelfde positie in de dataset verwijzen. hash tafel.

Hoe om te gaan met een hashing-botsing

Er zijn twee technieken die je kunt gebruiken om een hash-botsing te voorkomen:

Herhaling: Deze methode roept een secundaire hashfunctie aan, die continu wordt toegepast totdat een lege plek wordt gevonden waar een record kan worden geplaatst.
ketenen: De chaining-methode bouwt een gekoppelde lijst van items waarvan de sleutels dezelfde hashwaarde opleveren. Deze methode vereist een extra linkveld op elke positie in de tabel.

Veelgestelde vragen

Bij statische hashing wordt een vast aantal buckets aangehouden, waardoor het systeem kan overlopen naarmate de hoeveelheid data toeneemt. Dynamische hashing voegt buckets toe en verwijdert ze naar behoefte, waardoor het systeem zich aanpast aan veranderende datagroottes zonder een volledige heropbouw.

Voor bereikquery's. Hashing verspreidt sleutels over buckets, waardoor een query met 'tussen' of 'groter dan' de buckets niet in de juiste volgorde kan doorlopen. Een geordende index houdt sleutels gesorteerd en is daarom beter geschikt.

Een bucket loopt over wanneer er meer records aan worden toegewezen dan erin passen. Bij statische hashing komt dit vaak voor naarmate de hoeveelheid data toeneemt, en dit wordt opgevangen door open adressering, chaining of overloopbuckets.

AI-systemen gebruiken hashing voor het snel opzoeken van kenmerken en voor de hashing-truc, waarmee categorieën met een hoge cardinaliteit worden omgezet in een vaste vector. Hashing op basis van gelijkenis groepeert ook records die bijna identiek zijn op een efficiënte manier.

Bij het opnieuw hashen wordt met behulp van een tweede functie een andere vrije plek in dezelfde tabel gevonden. Door middel van chaining worden botsende records in een gekoppelde lijst bijgehouden die aan de bucket is gekoppeld, zodat de tabel zelf nooit twee keer een plek vult.