Uvod v Hashing funkcijo na Javi
Kot vemo, da je Java objektno usmerjen jezik, bi moral obstajati mehanizem za opis stanja predmeta, ne glede na to, kako velik je objekt. Da bi izpolnili to zahtevo, se je na Javi pojavila funkcija hašinga.
Kaj je funkcija lova?
Hash funkcijo lahko definiramo kot funkcijo, ki vrne celo število, ki ustreza predmetu. Hash funkcija vedno vrne isto vrednost celega števila za isti objekt. Celotna vrednost, ki jo vrne hash funkcija, se imenuje Hash Value. Sledijo pomembne točke v zvezi s funkcijo Hash:
- Vedno vrne celo število (4 bajte) za predmet.
- Stanja objekta ne moremo izračunati iz vrednosti hash-a, da so hash funkcije po naravi nepovratne.
- Dva enaka predmeta bosta imela enake vrednosti.
- Dva neenaka predmeta nimata vedno različnih vrednosti Hash.
Uporaba Hash funkcije
Tu so pogoste aplikacije hash funkcij:
1. Strukture podatkov
Skoraj vsak programski jezik vsebuje podatkovne strukture na osnovi hash. Na primer, java vsebuje tabelo Hash, Hash Map, Hash Set, Tree Set podatkovne strukture, ki temeljijo na funkciji Hash. Osnova teh podatkovnih struktur je zasnova Key-Value, kjer je vsak ključ enkraten, medtem ko lahko za več ključev obstaja enaka vrednost.
2. Poročilo o prenosu sporočil
Ta algoritem se uporablja pri preverjanju integritete podatkov. Ta algoritem kot sporočilo sprejme sporočilo katere koli dolžine in ustvari podatke s fiksno dolžino (128-bitno) kot izhod. Primeri algoritmov za prebavo sporočil vključujejo MD2, MD4, MD5 in MD6.
3. Zaščiten algoritem osvetlitve
Ta algoritem se uporablja za varnost podatkov in se uporablja v aplikacijah in protokolih, kot je Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 in SHA-3 so pogoste kategorije algoritma za varno hašiš.
4. Preverjanje in shranjevanje gesla
Razmislimo o prijavnem scenariju, v katerem se ob vnosu gesla za preverjanje pristnosti uporabnika izračuna heš vrednost vnesenega gesla in se po omrežju pošlje strežniku, kjer je shranjen hash izvirnika. To se naredi, da se prepreči, da se ne opravi njuhanje, ko se odjemalca pošlje geslo strežniku.
5. Delovanje prevajalnika
Ker se v programskem jeziku uporabljajo različne ključne besede, za razlikovanje med temi ključnimi besedami in identifikatorji prevajalnik uporablja nabor hash-ja, ki je implementiran s pomočjo hash tabele, za shranjevanje vseh teh ključnih besed in identifikatorjev.
6. Algoritem Rabin- Karp
Gre za algoritem iskanja, ki uporablja hashing za iskanje enega ali več vzorcev v danem nizu. Gre za enega najpogosteje uporabljenih algoritmov.
7. Primerljivi in primerjalni vmesniki
Ti vmesniki vsebujejo funkcije, ki se uporabljajo za primerjavo dveh predmetov hkrati. Povratna vrednost teh funkcij je lahko negativna, ničelna ali pozitivna glede na to, ali je določen objekt manjši, enak ali večji od predmeta, s katerim primerjamo. Notranji primerjalni in primerljivi vmesniki za primerjavo predmetov med seboj uporabljajo hash funkcijo.
8. Prednostna vrsta
Prednostna vrsta ni za razliko od običajne čakalne vrste, ki sledi vrstnemu redu FIFO (First in First out). V prednostni vrsti so elementi razporejeni po vrstnem redu glede na prednostno nalogo, ki se interno izvaja s primerljivimi in primerjalniki, ki stažarji temeljijo na Hash funkcijah.
Oblikovanje Hash funkcij
Tu je nekaj splošnih načinov oblikovanja za ustvarjanje hash funkcij:
- Učinkovito je treba ovrednotiti hash funkcijo.
- Hash vrednosti, izračunane iz hash funkcij, morajo biti enakomerno porazdeljene, kar pomaga preprečiti trke.
- Programski jezik Java zagotavlja splošno funkcijo mešanja z metodo hashCode () v nadklasi Object.
public int hashCode ()(
//Logic goes here
)
Hash Collision na Javi
Hash trčenje se zgodi, ko dva ali več predmetov vrne isto vrednost hash. Vzemimo primer karte java hash, ki shranjuje podatke v pare ključ-vrednost. Ko predmet postavimo na zemljevid hash, se izračuna vrednost hash-ja ključa in na podlagi tega mesta vedre hash vrednosti za shranjevanje vrednosti vrednosti najde. Predmeti z različnimi vrednostmi hash-a morajo biti v različnih vedrih. Kadar imata dva ali več predmetov isto hash vrednost, se shranijo na isto mesto vedra z uporabo dodatne podatkovne strukture, imenovane povezani seznam. Vsi predmeti z isto hash vrednostjo so povezani skupaj s povezanim seznamom. Ta mehanizem se imenuje vezanje. Spodaj so načini za reševanje trkov je hash funkcija:
- Veriženje: Kot je že zajeto, je ideja veriženja ustvariti povezan seznam predmetov, ki imajo isto mešanico. Veriženje je preprosta tehnika, vendar zahteva dodatne spominske stroške.
- Odprto naslavljanje: V tej tehniki so vsi elementi shranjeni v tabeli hash, v kateri vsak vnos vsebuje zapis ali NULL. Ko se element išče, se pri vsakem vnosu v hash tabeli išče želeni zapis, dokler ni najden potreben zapis ali če se ugotovi, da zapis ne obstaja v tabeli.
Prednosti Hashinga
Sledijo prednosti hashinga:
- Primerjajte vsebino dveh datotek enostavno in učinkovito, ne da bi ju odpirali.
- Hash funkcije se uporabljajo pri preverjanju celovitosti datoteke.
- S pomočjo hashiranja je iskanje podatkov v podatkovnih strukturah postalo hitrejše.
- Hash funkcije igrajo ključno vlogo pri varnosti podatkov, saj večina varnostnih algoritmov in protokolov uporablja hashing.
- Hashing pretvori podatke v krajšo vrednost ali ključ s fiksno dolžino, ki predstavlja izvirni niz, ki ga je mogoče poslati po omrežju.
Slabosti Hashinga
Poleg prednosti obstajajo tudi nekatere omejitve mešanja:
- Hashing ni mogoče izvesti za razvrščanje podatkov.
- Haš trka ni mogoče praktično preprečiti, kar posledično vodi v neučinkovitost.
Priporočeni članki
To je priročnik za Hashing funkcijo na Javi. Tukaj razpravljamo o uporabih hash funkcije, skupaj s prednostmi in slabostmi. Če želite izvedeti več, si oglejte tudi naslednje članke -
- Izjava in inicializacija VB.Net
- Program Java, ki prikazuje HashMap in TreeMap
- Vrste lopustov v DBMS
- Tehnike steganografije
- Nizi v programiranju Java
- Hashmap v Javi