Uvod v funkcijo lova na C
Ta članek vsebuje kratko opombo o hashingu (tabela hash in hash funkcija). Najpomembnejši koncept je „iskanje“, ki določa časovno zapletenost. Za zmanjšanje časovne zahtevnosti je uveden koncept mešanja podatkovne strukture, ki ima O (1) čas v povprečju, najslabši pa bo potreben O (n) čas.
Hashing je tehnika s hitrejšim dostopom do elementov, ki podane podatke preslika z manjše tipke za primerjave. Na splošno se v tej tehniki tipke z uporabo hash funkcije zasledujejo v tabelo, imenovano hash tabela.
Kaj je Hash funkcija?
Hash funkcija je funkcija, ki uporablja operacijo s stalnim časom za shranjevanje in pridobivanje vrednosti iz tabele hash, ki je uporabljena na tipkah kot cela števila in se uporablja kot naslov vrednosti v tabeli hash-a.
Vrste Hash funkcije
Spodaj so razložene vrste hash funkcij:
1. Metoda delitve
Pri tej metodi je hash funkcija odvisna od preostale delitve.
Primer: elementi, ki jih je treba postaviti v tabelo hash, so 42, 78, 89, 64 in vzemimo velikost tabele kot 10.
Hash (tipka) = Elementi% velikosti tabele;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Predstavitev tabele je razvidna kot spodaj:
2. Metoda srednjega kvadrata
Pri tej metodi se kot indeks vzame srednji del kvadrata.
Element, ki ga vstavimo v tabelo hash, je 210, 350, 99, 890, velikost tabele pa 100.
210 * 210 = 44100, indeks = 1, saj je srednji del rezultata (44100) 1.
350 * 350 = 122500, indeks = 25, saj je srednji del rezultata (122500) 25.
99 * 99 = 9801, indeks = 80, srednji del rezultata (9801) pa je 80.
890 * 890 = 792100, indeks = 21, kot srednji del rezultata (792100) je 21.
3. Metoda zlaganja številk
Pri tej metodi je element, ki ga je treba vstaviti v tabelo uh, peti hash ključ, ki ga dobimo tako, da elemente razdelimo na različne dele in nato združimo dele z nekaj preprostimi matematičnimi operacijami.
Element, ki ga je treba postaviti, je 23576623, 34687734.
- hash (ključ) = 235 + 766 + 23 = 1024
- hash ključ) = 34 + 68 + 77 + 34 = 213
Recimo, da imamo pri teh vrstah hashing števil od 1- 100 in velikost hash tabele = 10. Elementi = 23, 12, 32
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
Iz zgornjega primera opazite, da oba elementa 12 in 32 kažeta na 2. mesto v tabeli, kjer ni mogoče napisati obeh na isto mesto, tak problem je znan kot trk. Da bi se izognili tovrstnim težavam, lahko uporabimo nekaj tehnik hash funkcij.
Vrste tehnik reševanja trka
Pogovorimo se o vrstah tehnik reševanja trka:
1. veriženje
Pri tej metodi, kot že ime pove, zagotavlja verigo polj za zapis v tabeli z dvema vnosoma elementov. Kadar koli pride do takšnih trkov, bodo polja oblikovana kot povezan seznam.
Primer: 23, 12, 32 z velikostjo tabele 10.
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
2. Odprite naslavljanje
- Linearno sondiranje
To je še ena metoda reševanja težav pri trčenju. Kot že ime pove, ko pride do trka, je treba na isti vnos v tabeli vstaviti dva elementa, vendar s to metodo lahko poiščemo naslednji prazen prostor ali vnos v tabelo in postavimo drugi element. To lahko spet privede do druge težave; če v tabeli ne najdemo nobenega praznega vnosa, potem to vodi v združevanje. Tako je to znano kot problem grozdenja, ki ga je mogoče rešiti z naslednjo metodo.
Primer: 23, 12, 32 z velikostjo tabele 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
V tem diagramu sta 12 in 32 lahko postavljena v isti vnos z indeksom 2, vendar se po tej metodi postavita linearno.
- Kvadratno sondiranje
Ta metoda je rešitev problema z grozdijo med linearnim sondiranjem. V tej metodi se funkcija hash s hash ključem izračuna kot hash (key) = (hash (tipka) + x * x)% velikosti tabele (kjer je x = 0, 1, 2…).
Primer: 23, 12, 32 z velikostjo tabele 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
V tem lahko vidimo, da je mogoče 23 in 12 postaviti enostavno, vendar 32 ne more, ker 12 in 32 deli isti vnos z istim indeksom v tabeli, kot je po tej metodi hash (tipka) = (32 + 1 * 1) % 10 = 3. Toda v tem primeru je vnos tabele z indeksom 3 postavljen s 23, zato moramo vrednost x povečati za 1. Hash (tipka) = (32 + 2 * 2)% 10 = 6. Torej lahko zdaj postavimo 32 v vnosu z indeksom 6 v tabeli.
- Dvojno mešanje
Za reševanje problema trka moramo s to metodo izračunati 2 hash funkcije. Prva se izračuna z uporabo preproste metode delitve. Drugo mora izpolnjevati dva pravila; ne sme biti enak 0, vnosi pa morajo biti sondirani.
- 1 (tipka) = ključ% velikosti tabele.
- 2 (tipka) = p - (tip mod p), kjer je p preprosta števila <velikost tabele.
Primer: 23, 12, 32 z velikostjo tabele 10
Hash (ključ) = 23% 10 = 3;
Hash (ključ) = 12% 10 = 2;
Hash (ključ) = 32% 10 = 2;
V tem primeru lahko element 32 postavimo s pomočjo hash2 (tipka) = 5 - (32% 5) = 3. Torej lahko 32 postavimo v indeks 5 v tabeli, ki je prazna, saj moramo za postavitev preskočiti 3 vnose.
Zaključek-funkcija lova v C
Hashing je ena od pomembnih tehnik pri iskanju podatkov, ki se zagotavljajo z zelo učinkovitimi in hitrimi metodami z uporabo hash funkcij in hash tabel. Vsak element je mogoče iskati in namestiti z različnimi metodami mešanja. Glede na časovni koeficient je ta tehnika zelo hitra kot katera koli druga struktura podatkov.
Priporočeni članki
To je vodnik o funkciji Hashing v C. Tukaj razpravljamo o uvedbi Hashing funkcije v C, kaj je Hash funkcija, vrste hash funkcije itd. Obiščite lahko tudi druge naše predlagane članke, če želite izvedeti več -
- Hashing v DBMS
- Postopek šifriranja
- Kako namestiti CakePHP?
- Kako deluje Blockchain
- Hashing funkcija na Javi
- Delovanje funkcije v PHP | Kako delati?