Úvod do funkcie hashovania v C
Tento článok obsahuje krátku poznámku o hashovaní (hašovacia tabuľka a hašovacia funkcia). Najdôležitejšou koncepciou je „vyhľadávanie“, ktoré určuje časovú zložitosť. Aby sa znížila časová zložitosť, než je akákoľvek iná koncepcia hashovania dátovej štruktúry, zavádza sa v priemere 0 (1) čas a v najhoršom prípade to bude O (n) čas.
Hašovanie je technika s rýchlejším prístupom k prvkom, ktoré mapujú dané údaje pomocou menšieho kľúča na porovnanie. Vo všeobecnosti sa pri tejto technike vysledujú kľúče pomocou hashovej funkcie do tabuľky známej ako hašovacia tabuľka.
Čo je funkcia hash?
Hašovacia funkcia je funkcia, ktorá používa operáciu konštantného času na ukladanie a načítanie hodnoty z hašovacej tabuľky, ktorá sa na kľúčoch používa ako celé čísla a používa sa ako adresa pre hodnoty v hašovacej tabuľke.
Typy funkcie hash
Druhy hashovacích funkcií sú vysvetlené nižšie:
1. Metóda delenia
V tejto metóde je hashova funkcia závislá od zvyšku delenia.
Príklad: prvky, ktoré sa majú vložiť do hashovej tabuľky, sú 42, 78, 89, 64 a veľkosť tabuľky vezmeme ako 10.
Hash (kľúč) = Prvky% veľkosť tabuľky;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Znázornenie tabuľky je uvedené nižšie:
2. Metóda Mid Square
V tejto metóde sa stredná časť štvorcového prvku považuje za index.
Prvky, ktoré sa majú vložiť do hashovej tabuľky, sú 210, 350, 99, 890 a veľkosť tabuľky je 100.
210 * 210 = 44100, index = 1 ako stredná časť výsledku (44100) je 1.
350 * 350 = 122500, index = 25 ako stredná časť výsledku (122500) je 25.
99 * 99 = 9801, index = 80 ako stredná časť výsledku (9801) je 80.
890 * 890 = 792100, index = 21 ako stredná časť výsledku (792100) je 21.
3. Metóda skladania číslic
Pri tejto metóde je prvkom, ktorý sa má umiestniť do tabuľky, has has has key, ktorý sa získa rozdelením prvkov na rôzne časti a potom ich spojí vykonaním jednoduchých matematických operácií.
Prvky, ktoré sa majú umiestniť, sú 23576623, 34687734.
- hash (kľúč) = 235 + 766 + 23 = 1024
- hashovací kľúč) = 34 + 68 + 77 + 34 = 213
Pri týchto typoch hashovania predpokladáme, že máme čísla od 1 do 100 a veľkosť tabuľky hash = 10. Prvky = 23, 12, 32
Hash (kľúč) = 23% 10 = 3;
Hash (kľúč) = 12% 10 = 2;
Hash (kľúč) = 32% 10 = 2;
Z vyššie uvedeného príkladu si všimnite, že oba prvky 12 a 32 ukazujú na 2. miesto v tabuľke, kde nie je možné písať obidva na tom istom mieste, je tento problém známy ako kolízia. Aby sa predišlo takýmto problémom, existuje niekoľko techník hašovacích funkcií, ktoré je možné použiť.
Typy techník riešenia kolízií
Poďme diskutovať o typoch techník riešenia kolízií:
1. Reťazovanie
V tejto metóde, ako už názov napovedá, poskytuje reťazec polí pre záznam v tabuľke, ktorý má dva záznamy prvkov. Takže kedykoľvek dôjde k takým kolíziám, kolónky budú fungovať ako prepojený zoznam.
Príklad: 23, 12, 32 s veľkosťou tabuľky 10.
Hash (kľúč) = 23% 10 = 3;
Hash (kľúč) = 12% 10 = 2;
Hash (kľúč) = 32% 10 = 2;
2. Otvorte Addressing
- Lineárne snímanie
Toto je ďalší spôsob riešenia problémov so zrážkou. Ako už názov hovorí, keď dôjde ku kolízii, mali by sa dva prvky umiestniť na ten istý záznam v tabuľke, ale týmto spôsobom môžeme vyhľadať ďalší prázdny priestor alebo záznam v tabuľke a umiestniť druhý prvok. To môže opäť viesť k ďalšiemu problému; Ak v tabuľke nenájdeme žiadny prázdny záznam, vedie to k zoskupovaniu. Toto je známe ako problém zoskupovania, ktorý možno vyriešiť nasledujúcim spôsobom.
Príklad: 23, 12, 32 s veľkosťou tabuľky 10
Hash (kľúč) = 23% 10 = 3;
Hash (kľúč) = 12% 10 = 2;
Hash (kľúč) = 32% 10 = 2;
V tomto diagrame 12 a 32 môžu byť umiestnené v rovnakom zázname s indexom 2, ale podľa tejto metódy sú umiestnené lineárne.
- Kvadratické skúšanie
Táto metóda je riešením problému zoskupovania počas lineárneho snímania. Pri tejto metóde sa hashova funkcia s hashovacím tlačidlom vypočíta ako hash (key) = (hash (key) + x * x)% ve kos tabuľky (kde x = 0, 1, 2…).
Príklad: 23, 12, 32 s veľkosťou tabuľky 10
Hash (kľúč) = 23% 10 = 3;
Hash (kľúč) = 12% 10 = 2;
Hash (kľúč) = 32% 10 = 2;
V tomto vidíme, že 23 a 12 sa dajú umiestniť ľahko, ale 32 nemôže znovu, 12 a 32 zdieľa rovnaký záznam s rovnakým indexom v tabuľke, podľa tejto metódy hash (kľúč) = (32 + 1 * 1) % 10 = 3. Ale v tomto prípade je záznam tabuľky s indexom 3 umiestnený s 23, takže musíme zvyšovať x hodnotu o 1. Hašovací kláves (kľúč) = (32 + 2 * 2)% 10 = 6. Takže teraz môžeme umiestniť 32 v položke s indexom 6 v tabuľke.
- Dvojité hashovanie
Táto metóda musíme vypočítať 2 hašovacie funkcie, aby sme vyriešili problém kolízie. Prvá sa počíta pomocou jednoduchej metódy delenia. Druhý musí spĺňať dve pravidlá; nesmie sa rovnať 0 a záznamy sa musia skúšať.
- 1 (kľúč) = kľúč% veľkosť tabuľky.
- 2 (klávesa) = p - (klávesa mod p), kde p sú prvočísla <veľkosť tabuľky.
Príklad: 23, 12, 32 s veľkosťou tabuľky 10
Hash (kľúč) = 23% 10 = 3;
Hash (kľúč) = 12% 10 = 2;
Hash (kľúč) = 32% 10 = 2;
V tomto môže byť prvok 32 opäť vložený pomocou hash2 (kľúč) = 5 - (32% 5) = 3. Takže 32 môže byť umiestnené v indexe 5 v tabuľke, ktorá je prázdna, pretože na jeho umiestnenie musíme preskočiť 3 záznamy.
Záver-hasiaca funkcia v C
Hashing je jednou z dôležitých techník pri vyhľadávaní údajov poskytnutých pomocou veľmi účinných a rýchlych metód využívajúcich hašovacie funkcie a hašovacie tabuľky. Každý prvok môže byť prehľadaný a umiestnený pomocou rôznych metód hashovania. Táto technika je z hľadiska časového koeficientu veľmi rýchla ako ktorákoľvek iná štruktúra údajov.
Odporúčané články
Toto je sprievodca funkciou Hašovanie v C. Tu diskutujeme o zavedení funkcie Hašovanie v jazyku C, Čo je to funkcia Hašovanie, Typy funkcie hash atď. Ďalšie informácie nájdete aj v ďalších navrhovaných článkoch -
- Hashing v DBMS
- Proces šifrovania
- Ako nainštalovať CakePHP?
- Ako funguje Blockchain
- Funkcia hashovania v jazyku Java
- Hashing funkcia v PHP | Ako pracovať?