Uvod u funkciju ležanja u C
Ovaj članak ima kratku bilješku o hashingu (hash tablica i hash funkcija). Najvažniji pojam je 'traženje' koje određuje složenost vremena. Kako bi se smanjila vremenska složenost od bilo kojeg drugog uvedena je koncepcija raspršivanja strukture podataka koja u prosječnom slučaju ima O (1), a u najgorem slučaju trebat će O (n) vremena.
Hashing je tehnika s bržim pristupom elementima koji mapiraju dane podatke s manjim brojem za usporedbe. Općenito, u ovoj se tehnici ključevi pomoću hash funkcije prate u tablici poznatoj kao hash tablica.
Što je Hash funkcija?
Hash funkcija je funkcija koja koristi operaciju stalnog vremena za pohranjivanje i dohvaćanje vrijednosti iz hash tablice, koja se na tipke primjenjuje kao cijeli brojevi i koristi se kao adresa za vrijednosti u hash tablici.
Vrste funkcije sjeckanja
Niže su opisane vrste hash funkcija:
1. Metoda podjele
U ovoj metodi, hash funkcija ovisi o ostatku podjele.
Primjer: elementi koji se trebaju smjestiti u hash tablicu su 42, 78, 89, 64 i uzmimo veličinu tablice kao 10.
Hash (tipka) = Elementi% veličine tablice;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Prikaz tablice može se vidjeti kao dolje:
2. Metoda srednjeg kvadrata
U ovoj se metodi uzima srednji dio kvadratnog elementa kao indeks.
Element koji treba staviti u tablicu hash-a je 210, 350, 99, 890, a veličina tablice je 100.
210 * 210 = 44100, indeks = 1 jer je srednji dio rezultata (44100) 1.
350 * 350 = 122500, indeks = 25 jer je srednji dio rezultata (122500) 25.
99 * 99 = 9801, indeks = 80 jer je srednji dio rezultata (9801) 80.
890 * 890 = 792100, indeks = 21 jer je srednji dio rezultata (792100) 21.
3. Način savijanja cifara
U ovoj se metodi element koji se nalazi u tablici uh pjeva ključ, koji se dobiva dijeljenjem elemenata na različite dijelove, a zatim kombiniranjem dijelova izvođenjem nekih jednostavnih matematičkih operacija.
Element koji treba staviti je 23576623, 34687734.
- hash (ključ) = 235 + 766 + 23 = 1024
- hash ključ) = 34 + 68 + 77 + 34 = 213
Pretpostavimo da u ovim vrstama hash-a imamo brojeve od 1 do 100, a veličina hash tablice = 10. Elementi = 23, 12, 32
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
Iz gornjeg primjera primijetite da oba elementa 12 i 32 upućuju na 2. mjesto u tablici, gdje nije moguće napisati oba na istom mjestu, takav je problem poznat i kao kolizija. Da biste izbjegli ovu vrstu problema, postoje neke tehnike hash funkcija koje se mogu koristiti.
Vrste tehnika rješavanja sudara
Razgovarajmo o vrstama tehnika rješavanja sudara:
1. Lančanje
U ovoj metodi, kao što ime sugerira, pruža se niz kutija za zapis u tablici s dva unosa elemenata. Dakle, kad god se dogodi takav sudar, okviri će djelovati kao povezan popis.
Primjer: 23, 12, 32 s veličinom tablice 10.
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
2. Otvorite Adresiranje
- Linearno sondiranje
Ovo je još jedna metoda za rješavanje problema sudara. Kao što ime kaže kad god se dogodi sudar, dva elementa treba staviti na isti unos u tablici, ali ovom metodom možemo tražiti sljedeći prazan prostor ili unos u tablici i staviti drugi element. To opet može dovesti do drugog problema; ako u tablici ne nađemo bilo koji prazan unos, to vodi u grupisanje. Stoga je ovo poznato kao problem klastera, koji se može riješiti slijedećom metodom.
Primjer: 23, 12, 32 s veličinom tablice 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
U ovom se dijagramu 12 i 32 mogu smjestiti u isti unos s indeksom 2, ali pomoću ove metode postavljaju se linearno.
- Kvadratno sondiranje
Ova metoda je rješenje za problem klastera tijekom linearnog sondiranja. U ovoj se metodi hash funkcija s hash ključem izračunava kao hash (tipka) = (hash (tipka) + x * x)% veličine tablice (gdje je x = 0, 1, 2…).
Primjer: 23, 12, 32 s veličinom tablice 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
U ovome možemo vidjeti da se 23 i 12 mogu lako postaviti, ali 32 ne mogu opet 12 i 32 dijeliti isti unos s istim indeksom u tablici, kao što je po ovoj metodi hash (tipka) = (32 + 1 * 1) % 10 = 3. Ali u ovom slučaju unos u tablicu s indeksom 3 postavlja se s 23, tako da moramo povećati x vrijednost za 1. Hash (tipka) = (32 + 2 * 2)% 10 = 6. Dakle, sada možemo smjestiti 32 unosa s indeksom 6 u tablici.
- Dvostruko hashing
Ovom metodom moramo riješiti 2 hash funkcije za rješavanje problema sudara. Prva se izračunava pomoću jednostavne metode podjele. Drugo mora zadovoljiti dva pravila; ne smije biti jednak 0 i unosi se moraju provjeriti.
- 1 (tipka) = ključ% veličine tablice.
- 2 (tipka) = p - (tip mod p), gdje je p glavni brojevi <veličina tablice.
Primjer: 23, 12, 32 s veličinom tablice 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
U ovom se slučaju element 32 može postaviti pomoću hash2 (tipka) = 5 - (32% 5) = 3. Dakle, 32 se može smjestiti u indeks 5 u tablici koja je prazna jer moramo preskočiti 3 unosa da bismo je postavili.
Zaključak - Funkcija zaslađivanja u C
Hashing je jedna od važnih tehnika u pogledu pretraživanja podataka s vrlo učinkovitim i brzim metodama pomoću hash funkcije i tablica hash-a. Svaki se element može pretraživati i postavljati pomoću različitih metoda raspršivanja. Ova je tehnika vrlo brza od bilo koje druge strukture podataka s obzirom na vremenski koeficijent.
Preporučeni članci
Ovo je vodič za funkciju Hashing u C. Ovdje smo raspravljali o uvođenju Hashing funkcije u C, Što je Hash funkcija, Vrste hash funkcije itd. Također možete proći kroz naše druge predložene članke da biste saznali više -
- Hashing u DBMS-u
- Postupak šifriranja
- Kako instalirati CakePHP?
- Kako djeluje Blockchain
- Funkcija skrivanja u Javi
- Funkcija ležanja u PHP-u | Kako raditi?