Hashing in DBMS: statische en dynamische hashtechnieken
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 de indexstructuur. De hashmethode wordt gebruikt om items in een database te indexeren en op te halen, omdat het sneller is om dat specifieke item te doorzoeken met behulp van de kortere gehashte sleutel in plaats van de oorspronkelijke waarde te gebruiken. Gegevens worden opgeslagen in de vorm van datablokken waarvan het adres wordt gegenereerd door een hash-functie toe te passen op de geheugenlocatie waar deze records worden opgeslagen, ook wel een datablok of databucket.
Waarom hebben we hashing nodig?
Dit zijn de situaties in het DBMS waarin u de Hashing-methode moet toepassen:
- Voor een enorme databasestructuur is het moeilijk om alle indexwaarden op alle niveaus te doorzoeken en dan moet je het doeldatablok bereiken om de gewenste gegevens te verkrijgen.
- De hashmethode wordt gebruikt om items in een database te indexeren en op te halen, omdat het sneller is om dat specifieke item te doorzoeken met behulp van de kortere gehashte sleutel in plaats van de oorspronkelijke waarde te gebruiken.
- Hashing is een ideale methode om de directe locatie van een gegevensrecord op de schijf te berekenen zonder gebruik te maken van de indexstructuur.
- Het is ook een nuttige techniek voor het implementeren van woordenboeken.
Belangrijke terminologieën in hashing
Hier zijn belangrijke terminologieën die worden gebruikt bij Hashing:
- Gegevensbucket – Databuckets zijn geheugenlocaties waar de records worden opgeslagen. Het wordt ook wel opslageenheid genoemd.
- sleutel: A DBMS-sleutel is een attribuut of een set van een attribuut waarmee u een rij(tupel) in een relatie(tabel) kunt identificeren. Hiermee kunt u de relatie tussen twee tabellen vinden.
- Hash-functie: Een hash-functie is een toewijzingsfunctie die alle zoeksleutels toewijst aan het adres waar de werkelijke records zijn geplaatst.
- Lineair onderzoek – Lineair tasten is een vast interval tussen tasten. Bij deze methode wordt het volgende beschikbare datablok gebruikt om het nieuwe record in te voeren, in plaats van het oudere record te overschrijven.
- Kwadratisch sonderen– Het helpt u bij het bepalen van het nieuwe bucketadres. Het helpt u bij het toevoegen van interval tussen probes door de opeenvolgende uitvoer van een kwadratische polynoom toe te voegen aan de startwaarde die door de oorspronkelijke berekening is gegeven.
- Hash-index – Het is een adres van het datablok. Een hashfunctie kan een simpele wiskundige functie zijn tot zelfs een complexe wiskundige functie.
- Double Hashing -Double hashing is een computerprogrammeermethode die in hashtabellen wordt gebruikt om de problemen van een botsing op te lossen.
- Emmer overloop: De toestand waarin de bak overstroomt, wordt botsing genoemd. Dit is een fatale fase voor elke statische functie.
Soorten hashtechnieken
Er zijn hoofdzakelijk twee soorten SQL-hashmethoden/-technieken:
- Statische hasj
- Dynamisch hashen
statische hashing
Bij statische hashing blijft het resulterende gegevensbucketadres altijd hetzelfde.
Daarom, als u bijvoorbeeld een adres genereert Student_ID = 10 met behulp van de hashfunctie mod(3), zal het resulterende bucketadres altijd zijn 1. U zult dus geen verandering in het bucketadres zien.
Daarom blijft bij deze statische hashmethode het aantal databuckets in het geheugen altijd constant.
Statische hashfuncties
- Een record invoegen: Wanneer een nieuw record in de tabel moet worden ingevoegd, kunt u een adres voor het nieuwe record genereren met behulp van de hash-sleutel. Wanneer het adres wordt gegenereerd, wordt de record automatisch op die locatie opgeslagen.
- Zoeken: Wanneer u de record moet ophalen, zou dezelfde hash-functie nuttig moeten zijn om het adres op te halen van de bucket waar de gegevens moeten worden opgeslagen.
- Verwijder een record: Met behulp van de hash-functie kunt u eerst het record ophalen dat u wilt verwijderen. Vervolgens kunt u de records voor dat adres uit het geheugen verwijderen.
Statische hashing is verder onderverdeeld in
- Open hashing
- Sluit hashing.
Hashing openen
Bij de Open hashing-methode wordt in plaats van het oudere te overschrijven het volgende beschikbare datablok gebruikt om het nieuwe record in te voeren. Deze methode staat ook bekend als lineair sonderen.
A2 is bijvoorbeeld een nieuw record dat u wilt invoegen. De hashfunctie genereert adres als 222. Maar het is al bezet door een andere waarde. Daarom zoekt het systeem naar de volgende databucket 501 en wijst daaraan A2 toe.
Sluit hashing
Bij de close hashing-methode wordt, wanneer de buckets vol zijn, een nieuwe bucket toegewezen voor dezelfde hash en worden de resultaten gekoppeld aan de vorige.
Dynamisch hashen
Dynamische hashing biedt een mechanisme waarbij gegevensbuckets dynamisch en op aanvraag worden toegevoegd en verwijderd. Bij deze hashing helpt de hashfunctie je om een groot aantal waarden te creëren.
Verschil tussen geordende indexering en hashing
Hieronder staan de belangrijkste verschillen tussen indexeren en hashen
parameters | Orderindexering | Hashing |
---|---|---|
Opslaan van adres | 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. |
Prestatie | Het kan afnemen wanneer de data in het hashbestand toeneemt. Omdat het de data in een gesorteerde vorm opslaat wanneer er een (insert/delete/update) bewerking wordt uitgevoerd, wat de prestaties ervan vermindert. | De prestaties van hashing zijn het beste als er voortdurend gegevens worden toegevoegd en verwijderd. Wanneer de database echter enorm groot is, zullen de organisatie en het onderhoud van hashbestanden duurder zijn. |
Gebruik voor | De voorkeur gaat uit naar het ophalen van gegevens binnen een bereik. Dit betekent dat wanneer er gegevens voor een bepaald bereik worden opgehaald, deze methode een ideale optie is. | Dit is een ideale methode als u een bepaald record wilt ophalen op basis van de zoeksleutel. Het werkt echter alleen goed als de hashfunctie op de zoeksleutel staat. |
Geheugen management | Er zullen veel ongebruikte datablokken zijn vanwege de delete/update-bewerking. Deze datablokken kunnen niet worden vrijgegeven voor hergebruik. Daarom is regelmatig onderhoud van het geheugen vereist. | Bij statische en dynamische hashmethoden wordt het geheugen altijd beheerd. Het overlopen van de emmer wordt ook perfect afgehandeld om de statische hashing uit te breiden. |
Wat is botsing?
Hash-botsing is een toestand waarbij de resulterende hashes van twee of meer gegevens in de dataset ten onrechte dezelfde plaats in de dataset in kaart brengen. hash tafel.
Hoe om te gaan met een hashing-botsing?
Er zijn twee technieken die u kunt gebruiken om een hash-botsing te voorkomen:
- Herkauwen: Deze methode roept een secundaire hash-functie aan, die continu wordt toegepast totdat een leeg slot wordt gevonden, waar een record moet worden geplaatst.
- chaining: De ketenmethode bouwt een gekoppelde lijst op met items waarvan de sleutel naar dezelfde waarde hasht. Deze methode vereist een extra linkveld naar elke tafelpositie.
Samenvatting
- In dbms, is hashen een techniek om direct naar de locatie van gewenste gegevens op de schijf te zoeken zonder gebruik te maken van de indexstructuur.
- De hashmethode wordt gebruikt om items in een database te indexeren en op te halen, omdat het sneller is om dat specifieke item te doorzoeken met behulp van de kortere gehashte sleutel in plaats van de oorspronkelijke waarde te gebruiken.
- Databucket, sleutel, hashfunctie, lineair sonderen, kwadratisch sonderen, hash-index, Double Hashing en Bucket Overflow zijn belangrijke terminologieën die bij hashing worden gebruikt
- Er zijn twee soorten hashingmethoden: 1) statische hashing en 2) dynamische hashing
- Bij statische hashing blijft het resulterende gegevensbucketadres altijd hetzelfde.
- Dynamische hashing biedt een mechanisme waarbij gegevensbuckets dynamisch en op aanvraag worden toegevoegd en verwijderd.
- In volgorde worden indexeringsadressen in het geheugen gesorteerd op basis van een kritische waarde, terwijl hash-adressen altijd worden gegenereerd met behulp van een hash-functie op de sleutelwaarde.
- Hash-botsing is een toestand waarin de resulterende hashes van twee of meer gegevens in de dataset ten onrechte dezelfde plaats in de hash-tabel in kaart brengen.
- Rehashing en chaining zijn twee methoden die u helpen een hash-botsing te voorkomen.