Hashing i DBMS: Statiske og dynamiske hashing-teknikker

Af: Fiona Brown Fiona Brown
Hours Opdateret

⚡ Smart opsummering

Hashing i DBMS er en teknik, der beregner en posts diskplacering direkte fra dens nøgle uden at bruge et indeks. En hashfunktion knytter søgenøgler til data-buckets, og statisk eller dynamisk hashing styrer, hvordan disse buckets vokser.

  • ⚡ Kerneidé: En hashfunktion omdanner en nøgle til en bucket-adresse, så en post findes i ét trin i stedet for ved indeksgennemgang.
  • 🪣 Dataspand: Den hukommelsesplacering eller lagringsenhed, hvor poster med samme hash placeres.
  • 📌 Statisk hashing: Antallet af buckets er fast, så en given nøgle knyttes altid til den samme adresse.
  • 📈 Dynamisk hashing: Buckets tilføjes og fjernes efter behov, efterhånden som datamængden ændres.
  • ???? Kollision: To nøglekortping til den samme bucket, løst ved probing, rehashing eller chaining.
  • 🔍 Bedst for: Præcise match-opslag på søgenøglen, hvor hashing er bedre end ordnet indeksering.
  • 📊 Afvejning: Ordnede indekseringsgevinster for intervalforespørgsler; hashing-gevinster for konstante indsættelser og punktopslag.
Læs mere

Statisk og dynamisk hashing i DBMS

Hvad er hashing i DBMS?

I DBMS er hashing en teknik til direkte at søge efter placeringen af ​​ønskede data på disken uden at bruge en indeksstruktur. Hashing-metoden bruges til at indeksere og hente elementer i en database, da det er hurtigere at søge efter et specifikt element ved hjælp af den kortere hashnøgle i stedet for dens oprindelige værdi. Data gemmes i form af datablokke, hvis adresse genereres ved at anvende en hashfunktion; hukommelsesplaceringen, hvor disse poster gemmes, kaldes en datablok eller databøtte.

Hvorfor har vi brug for hashing?

Her er de situationer i et DBMS, hvor du skal anvende hashing-metoden:

  • For en enorm databasestruktur er det svært at søge i alle indeksværdier på alle deres niveauer og derefter nå destinationsdatablokken for at få de ønskede data.
  • Hashing bruges til at indeksere og hente elementer i en database, fordi det er hurtigere at søge efter et specifikt element ved hjælp af den kortere hashnøgle end den oprindelige værdi.
  • Hashing er en ideel metode til at beregne den direkte placering af en datapost på disken uden at bruge en indeksstruktur.
  • Det er også en nyttig teknik til at implementere ordbøger.

Vigtige terminologier i hashing

Her er vigtige terminologier, der bruges i hashing:

  • Dataspand: Data buckets er hukommelsessteder, hvor posterne gemmes. Det er også kendt som lagringsenheden.
  • Nøgle: a DBMS nøgle er en attribut eller et sæt af attributter, der hjælper dig med at identificere en række (tuple) i en relation (tabel).
  • Hash-funktion: et kortping funktion, der knytter alle søgenøgler til den adresse, hvor de faktiske poster er placeret.
  • Lineær sondering: et fast interval mellem sonder. I denne metode bruges den næste tilgængelige datablok til at indtaste den nye post i stedet for at overskrive den ældre post.
  • Kvadratisk sondering: hjælper med at bestemme den nye bucket-adresse ved at lægge det fortløbende output fra et kvadratisk polynomium til startværdien givet af den oprindelige beregning.
  • Hash-indeks: adressen på datablokken. En hashfunktion kan være en simpel matematisk funktion eller en kompleks funktion.
  • Double Hashing: en metode, der bruges i hashtabeller til at løse kollisioner ved at anvende en anden hashfunktion.
  • Spandoverløb: Tilstanden med bucket-overflow kaldes kollision. Dette er en fatal fase for enhver statisk hashfunktion.

Typer af hashing-teknikker

Der er primært to typer hashingteknikker i DBMS:

  1. Statisk hash
  2. Dynamisk hash

De to adskiller sig primært i, om antallet af buckets er fast, som de næste to afsnit forklarer.

Statisk hash

Ved statisk hashing vil den resulterende data bucket-adresse altid forblive den samme.

Derfor, hvis du genererer en adresse til f.eks. Student_ID = 10 ved hjælp af hashingfunktionen mod(3), vil den resulterende bucket-adresse altid være 1Så du vil ikke se nogen ændring i bucket-adressen.

Derfor forbliver antallet af data-buckets i hukommelsen altid konstant i den statiske hashing-metode.

RELATEREDE ARTIKLER

Statiske hash-funktioner

  • Indsættelse af en post: Når en ny post skal indsættes i tabellen, genererer du en adresse til den ved hjælp af dens hash-nøgle. Når adressen er genereret, gemmes posten på den placering.
  • Søger: Når du skal hente posten, bruges den samme hashfunktion til at hente adressen på den bucket, hvor dataene er gemt.
  • Slet en post: Ved at bruge hashfunktionen henter du først den post, du vil slette, og fjerner derefter posten fra den adresse i hukommelsen.

Statisk hashing er yderligere opdelt i:

  1. Åbn hashing
  2. Lukket hashing

Åbn Hashing

I den åbne hashing-metode bruges den næste tilgængelige datablok til at indtaste den nye post i stedet for at overskrive den ældre post. Denne metode er også kendt som lineær probing.

For eksempel er A2 en ny post, du vil indsætte. Hashfunktionen genererer adressen 222, men den er allerede optaget af en anden værdi. Derfor søger systemet efter den næste data bucket, 501, og tildeler A2 til den.

Hvordan åben hashing fungerer med lineær probing
Sådan fungerer Open Hash

Lukket hashing

I den lukkede hashing-metode, når buckets er fulde, allokeres en ny bucket til den samme hash, og resultatet linkes efter den forrige.

Dynamisk hash

Dynamisk hashing tilbyder en mekanisme, hvor data buckets tilføjes og fjernes dynamisk og efter behov. I denne hashing-metode hjælper hashfunktionen dig med at oprette et stort antal værdier, og strukturen vokser eller krymper med dataene. Dette gør den til et godt valg til tabeller, hvis størrelse ikke kan forudsiges på forhånd, hvor statisk hashing enten ville spilde plads eller overløbe.

Forskellen mellem ordnet indeksering og hashing

Nedenfor er de vigtigste forskelle mellem indeksering og hashing:

Driftsparametre Ordnet indeksering hashing
Opbevaring af adresse Adresser i hukommelsen sorteres efter en nøgleværdi kaldet primærnøglen. Adresser genereres altid ved hjælp af en hash-funktion på nøgleværdien.
Ydeevne Den kan falde, efterhånden som dataene øges, fordi dataene lagres sorteret, og hver indsættelse, sletning eller opdatering omorganiserer dem. Ydeevnen er bedst med konstant tilføjelse og sletning af data. For en enorm database bliver vedligeholdelse af hashfiler dyrere.
Brugt til Foretrukket til hentning af område, hvor data hentes for et bestemt område. Ideel til at hente en bestemt post baseret på søgenøglen og fungerer kun godt, når hashfunktionen er på søgenøglen.
Hukommelsesstyring Mange ubrugte datablokke opstår fra sletning og opdatering og kan ikke frigives til genbrug, så regelmæssig vedligeholdelse er påkrævet. I statisk og dynamisk hashing administreres hukommelse altid, og bucket overflow håndteres for at udvide statisk hashing.

Kort sagt, vælg bestilt Indeksering til områdeforespørgsler og hashing til opslag med eksakt match på nøglen.

Hvad er kollision?

En hash-kollision er en tilstand, hvor de resulterende hashes fra to eller flere elementer i datasættet forkert mappes til det samme sted i hash bord.

Sådan håndterer du en hashingkollision

Der er to teknikker, du kan bruge til at undgå en hash-kollision:

  1. Genopvarmning: Denne metode aktiverer en sekundær hashfunktion, som anvendes kontinuerligt, indtil der findes et tomt slot, hvor en post kan placeres.
  2. Kædning: Kædningsmetoden opbygger en linket liste over elementer, hvis nøgler hashes til den samme værdi. Denne metode kræver et ekstra linkfelt på hver tabelposition.

Ofte Stillede Spørgsmål

Statisk hashing holder et fast antal buckets, så det kan overløbe, efterhånden som data vokser. Dynamisk hashing tilføjer og fjerner buckets efter behov, så det tilpasser sig ændret datastørrelse uden en fuldstændig genopbygning.

For rækkeviddeforespørgsler. Hashing spreder nøgler på tværs af buckets, så en mellem- eller større-end-forespørgsel kan ikke føre dem i rækkefølge. Et ordnet indeks holder nøglerne sorteret og passer bedre der.

En bucket løber over, når der tilføres flere poster, end der kan indeholdes. Ved statisk hashing er dette almindeligt, efterhånden som data vokser, og det håndteres af åbne adresseringer, kæder eller overflow-buckets.

AI-systemer bruger hashing til hurtig funktionssøgning og til hashing-tricket, som mapper kategorier med høj kardinalitet til en fast vektor. Similarity-hashing grupperer også næsten duplikerede poster effektivt.

Genhashing finder en anden ledig plads i den samme tabel ved hjælp af en anden funktion. Kædning holder poster kolliderende i en linket liste, der er knyttet til bucket'en, så tabellen i sig selv aldrig udfylder en plads to gange.

Opsummer dette indlæg med: