Úvod do funkcie hashovania v jazyku Java
Ako vieme, že Java je objektovo orientovaný jazyk, mal by existovať mechanizmus na opis stavu objektu, bez ohľadu na to, aký veľký môže byť objekt. Na splnenie tejto požiadavky vznikla funkcia Hashing Function v jazyku Java.
Čo je funkcia hashovania?
Hašovacia funkcia môže byť definovaná ako funkcia, ktorá vracia celé číslo zodpovedajúce objektu. Funkcia hash vždy vracia rovnakú hodnotu pre ten istý objekt. Celé číslo vrátené hashovacou funkciou sa nazýva Hash Value. Nasledujú dôležité body týkajúce sa funkcie Hash:
- Vždy vráti celé číslo (4 bajty) pre objekt.
- Nemôžeme vypočítať stav objektu z hodnoty hash, že hash funkcie sú vo svojej podstate nezvratné.
- Dva rovnaké objekty budú mať rovnakú hodnotu hash.
- Dva nerovnaké objekty nemajú vždy rôzne hodnoty hash.
Aplikácia funkcie hash
Tu sú bežné aplikácie hash funkcií:
1. Štruktúry údajov
Takmer každý programovací jazyk obsahuje hašovacie dátové štruktúry. Napríklad java obsahuje tabuľku Hash, Hash Map, Hash Set, Tree Set dátové štruktúry, ktoré sú založené na Hash funkcii. Základom týchto dátových štruktúr je dizajn kľúč - hodnota, kde každý kľúč je jedinečný, zatiaľ čo rovnaká hodnota môže existovať pre viac kľúčov.
2. Prehľad správ
Tento algoritmus sa používa pri kontrole integrity údajov. Tento algoritmus berie ako vstup správu ľubovoľnej dĺžky a ako výstup vytvára dáta s pevnou dĺžkou (128-bit). Príklady algoritmov prehľadu správ zahŕňajú MD2, MD4, MD5 a MD6.
3. Zabezpečte algoritmus hashovania
Tento algoritmus sa používa na zabezpečenie údajov a používa sa v aplikáciách a protokoloch, ako je Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 a SHA-3 sú bežné kategórie algoritmu Secure Hash.
4. Overenie a uloženie hesla
Uvažujme o prihlasovacom scenári, v ktorom, keď sa zadá heslo na autentifikáciu užívateľa, vypočíta sa hash hodnota zadaného hesla a pošle sa cez sieť na server, kde sa uloží hash originálu. Týmto sa zabezpečí, aby sa pri odosielaní hesla z klienta na server nevykonávalo čuchanie.
5. Prevádzka kompilátora
Pretože sa v programovacom jazyku používajú rôzne kľúčové slová, na rozlíšenie medzi týmito kľúčovými slovami a identifikátormi kompilátor používa hashovaciu sadu, ktorá sa implementuje pomocou hashovej tabuľky na uloženie všetkých týchto kľúčových slov a identifikátorov.
6. Algoritmus Rabina-Karpa
Je to vyhľadávací algoritmus, ktorý využíva hashovanie na vyhľadávanie jedného alebo viacerých vzorov v danom reťazci. Je to jeden z najčastejšie používaných algoritmov.
7. Porovnateľné a porovnávacie rozhrania
Tieto rozhrania obsahujú funkcie, ktoré sa používajú na porovnávanie dvoch objektov súčasne. Návratová hodnota týchto funkcií môže byť záporná, nulová alebo pozitívna na základe toho, či je daný objekt menší, rovný alebo väčší ako objekt, s ktorým porovnávame. Interne komparátor a porovnateľné rozhrania používajú hash funkciu na porovnávanie objektov jeden od druhého.
8. Prioritný front
Fronta priorít je na rozdiel od normálneho frontu, ktorý nasleduje poradie FIFO (First in First out). Prvky frontov priorít sú usporiadané vo vlastnom poradí na základe ich priority, ktorá je interne implementovaná pomocou porovnateľného a porovnávacieho, ktoré stážisti sú založené na Hash Functions.
Navrhovanie Hash funkcií
Tu sú niektoré všeobecné princípy dizajnu na vytváranie hašovacích funkcií:
- Je potrebné efektívne vyhodnotiť hashovaciu funkciu.
- Hodnoty hash vypočítané z hašovacích funkcií by mali byť rovnomerne rozložené, čo pomáha predchádzať zrážkam.
- Programovací jazyk Java poskytuje všeobecnú hašovaciu funkciu s metódou hashCode () v nadtriede objektov.
public int hashCode ()(
//Logic goes here
)
Hash kolízia v Jave
Ku kolízii hash dôjde, keď dva alebo viac objektov vrátia rovnakú hodnotu hash. Vezmime si príklad mapy java hash, ktorá ukladá údaje do párov kľúč - hodnota. Keď vložíme objekt do hashovej mapy, vypočíta sa hašovacia hodnota kľúča a na základe tohto umiestnenia v tvare hašovacej hodnoty sa nájde objekt na uloženie hodnoty. Objekty s rôznymi hodnotami hash musia ísť do rôznych vedier. Ak majú dva alebo viac objektov rovnakú hashovaciu hodnotu, ukladajú sa na rovnakom mieste vedra pomocou ďalšej štruktúry údajov nazývanej prepojený zoznam. Všetky objekty, ktoré majú rovnakú hodnotu hash, sú spojené pomocou prepojeného zoznamu. Tento mechanizmus sa nazýva reťazenie. Nasledujú spôsoby, ako zvládnuť kolíziu, je hashova funkcia:
- Reťazovanie: Ako už bolo uvedené, myšlienkou reťazenia je vytvoriť prepojený zoznam objektov, ktoré majú rovnakú hodnotu hash. Reťazovanie je jednoduchá technika, ale vyžaduje ďalšie režijné náklady na pamäť.
- Otvorené adresovanie: Pri tejto technike sú všetky prvky uložené v hašovacej tabuľke, v ktorej každá položka obsahuje záznam alebo NULL. Pri vyhľadávaní prvku sa v každej položke v hašovacej tabuľke vyhľadáva požadovaný záznam, kým sa nenájde požadovaný záznam alebo kým sa nedospeje k záveru, že záznam v tabuľke neexistuje.
Výhody hashovania
Výhody hashovania sú nasledujúce:
- Porovnať obsah dvoch súborov ľahko a efektívne, bez ich otvorenia.
- Hašovacie funkcie sa používajú na kontrolu integrity súboru.
- Pomocou hashovania sa operácia vyhľadávania v dátových štruktúrach zrýchlila.
- Hašovacie funkcie hrajú dôležitú úlohu v zabezpečení údajov, pretože väčšina bezpečnostných algoritmov a protokolov využíva hashovanie.
- Hashing prevádza údaje na kratšiu hodnotu alebo kľúč s pevnou dĺžkou, ktorý predstavuje pôvodný reťazec, ktorý je možné odoslať v sieti.
Nevýhody Hašovania
Okrem výhod existujú aj obmedzenia hashovania:
- Hašovanie nie je možné implementovať na triedenie údajov.
- Kolízii hashu sa nedá prakticky vyhnúť, čo vedie k neefektívnosti.
Odporúčané články
Toto je sprievodca funkciou hashovania v jazyku Java. Tu diskutujeme aplikácie hašovacej funkcie spolu s výhodami a nevýhodami. Ďalšie informácie nájdete aj v nasledujúcich článkoch -
- Vyhlásenie a inicializácia VB.Net
- Program Java zobrazujúci HashMap a TreeMap
- Typy hasenia v DBMS
- Techniky steganografie
- Polia v programovaní Java
- Hashmap v Jave