Introduksjon til Hashing-funksjon i C
Denne artikkelen har en kort merknad om hashing (hasjtabell og hasjfunksjon). Det viktigste konseptet er å "søke" som bestemmer tidskompleksiteten. For å redusere tidskompleksiteten enn noe annet datastruktur innføres hashing-konsept som har O (1) tid i gjennomsnittet og i verste fall vil det ta O (n) tid.
Hashing er en teknikk med raskere tilgang til elementer som kartlegger de gitte dataene med en mindre nøkkel for sammenligning. Generelt i denne teknikken spores tastene ved å bruke hash-funksjon til en tabell kjent som hash-tabellen.
Hva er Hash-funksjon?
Hash-funksjonen er en funksjon som bruker konstant-tid-operasjonen til å lagre og hente verdien fra hasj-tabellen, som brukes på tastene som heltall, og denne brukes som adresse for verdier i hasj-tabellen.
Typer av en Hash-funksjon
Typene hasjfunksjoner blir forklart nedenfor:
1. Delingsmetode
I denne metoden er hasjfunksjonen avhengig av resten av en inndeling.
Eksempel: elementer som skal plasseres i en hasjetabell er 42, 78, 89, 64, og la oss ta tabellstørrelse som 10.
Hash (nøkkel) = Elementer% tabellstørrelse;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Tabellrepresentasjonen kan sees som nedenfor:
2. Mid Square-metoden
I denne metoden blir den midtre delen av det kvadratiske elementet tatt som indeksen.
Element som skal plasseres i hasjbordet er 210, 350, 99, 890 og størrelsen på bordet er 100.
210 * 210 = 44100, indeks = 1 som den midtre delen av resultatet (44100) er 1.
350 * 350 = 122500, indeks = 25 som den midtre delen av resultatet (122500) er 25.
99 * 99 = 9801, indeks = 80 som den midtre delen av resultatet (9801) er 80.
890 * 890 = 792100, indeks = 21 som midtre del av resultatet (792100) er 21.
3. Foldemetode for sifre
I denne metoden er elementet som skal plasseres i tabellen uh, sing hash-nøkkel, som oppnås ved å dele elementene i forskjellige deler og deretter kombinere delene ved å utføre noen enkle matematiske operasjoner.
Element som skal plasseres er 23576623, 34687734.
- hasj (nøkkel) = 235 + 766 + 23 = 1024
- hash-nøkkel) = 34 + 68 + 77 + 34 = 213
I disse typer hashing antar vi at vi har tall fra 1 til 100 og størrelsen på hasjbord = 10. Elementer = 23, 12, 32
Hash (nøkkel) = 23% 10 = 3;
Hash (nøkkel) = 12% 10 = 2;
Hash (nøkkel) = 32% 10 = 2;
Fra eksemplet ovenfor, legg merke til at begge elementene 12 og 32 peker til 2. plass i tabellen, der det ikke er mulig å skrive begge på samme sted, slikt problem er kjent som en kollisjon. For å unngå denne typen problemer er det noen teknikker for hasjfunksjoner som kan brukes.
Typer kollisjonsoppløsningsmetoder
La oss diskutere hvilke typer kollisjonsoppløsningsmetoder:
1. Kjetting
I denne metoden, som navnet antyder, gir den en kjede med bokser for posten i tabellen med to elementer. Så når slike kollisjoner oppstår, fungerer boksene som en koblet liste vil bli dannet.
Eksempel: 23, 12, 32 med bordstørrelse 10.
Hash (nøkkel) = 23% 10 = 3;
Hash (nøkkel) = 12% 10 = 2;
Hash (nøkkel) = 32% 10 = 2;
2. Åpne adressering
- Linear Probing
Dette er en annen metode for å løse kollisjonsproblemer. Som navnet sier når en kollisjon oppstår, bør to elementer plasseres på samme oppføring i tabellen, men med denne metoden kan vi søke etter neste tomme plass eller oppføring i tabellen og plassere det andre elementet. Dette kan igjen føre til et annet problem; hvis vi ikke finner noen tomme oppføringer i tabellen, fører det til klynging. Dermed er dette kjent som et klyngeproblem, som kan løses ved følgende metode.
Eksempel: 23, 12, 32 med bordstørrelse 10
Hash (nøkkel) = 23% 10 = 3;
Hash (nøkkel) = 12% 10 = 2;
Hash (nøkkel) = 32% 10 = 2;
I dette diagrammet kan 12 og 32 plasseres i samme oppføring med indeks 2, men ved denne metoden er de plassert lineært.
- Kvadratisk sondering
Denne metoden er en oppløsning for klyngeproblemet under lineær sondering. I denne metoden beregnes hasjfunksjonen med hash-tasten som hash (nøkkel) = (hash (tast) + x * x)% størrelse på tabellen (hvor x = 0, 1, 2 …).
Eksempel: 23, 12, 32 med bordstørrelse 10
Hash (nøkkel) = 23% 10 = 3;
Hash (nøkkel) = 12% 10 = 2;
Hash (nøkkel) = 32% 10 = 2;
I dette kan vi se at 23 og 12 kan plasseres enkelt, men 32 kan ikke igjen 12 og 32 deler samme oppføring med samme indeks i tabellen, i henhold til denne metoden hash (tast) = (32 + 1 * 1) % 10 = 3. Men i dette tilfellet er tabelloppføring med indeks 3 plassert med 23, så vi må øke x-verdien med 1. Hash (tast) = (32 + 2 * 2)% 10 = 6. Så nå kan vi plassere 32 i oppføringen med indeks 6 i tabellen.
- Dobbel hashing
Denne metoden må vi beregne 2 hasjfunksjoner for å løse kollisjonsproblemet. Den første beregnes ved å bruke en enkel inndelingsmetode. Det andre må tilfredsstille to regler; det må ikke være lik 0 og oppføringer må prøves.
- 1 (nøkkel) = nøkkel% størrelse på tabellen.
- 2 (tast) = p - (tast mod p), der p er primtall <størrelsen på tabellen.
Eksempel: 23, 12, 32 med bordstørrelse 10
Hash (nøkkel) = 23% 10 = 3;
Hash (nøkkel) = 12% 10 = 2;
Hash (nøkkel) = 32% 10 = 2;
I dette igjen kan elementet 32 plasseres ved å bruke hash2 (tast) = 5 - (32% 5) = 3. Så 32 kan plasseres ved indeks 5 i tabellen som er tom, da vi må hoppe 3 oppføringer for å plassere det.
Konklusjon-Hashing-funksjon i C
Hashing er en av de viktige teknikkene når det gjelder søking av data utstyrt med svært effektive og raske metoder ved bruk av hasjfunksjon og hasjtabeller. Hvert element kan søkes og plasseres ved hjelp av forskjellige hashingmetoder. Denne teknikken er veldig raskere enn noen annen datastruktur når det gjelder tidskoeffisient.
Anbefalte artikler
Dette er en guide til Hashing-funksjonen i C. Her diskuterer vi introduksjonen av Hashing-funksjonen i C, Hva er Hash-funksjon, Typer av en hasjfunksjon, etc. Du kan også gå gjennom andre foreslåtte artikler for å lære mer–
- Høsting i DBMS
- Krypteringsprosess
- Hvordan installerer CakePHP?
- Slik fungerer blockchain
- Hashing-funksjon i Java
- Hashing-funksjon i PHP | Hvordan arbeide?