240px|мини|десно|Heš funkcija koja slika imena u cele brojeve u opsegu od 0-15. Dolazi do kolizije u slučajevima "John Smith" i "Sandra Dee".
Heš funkcija je svaki algoritam koji podacima proizvoljne dužine dodeljuje podatke fiksne dužine.
Vrednost koju vraća heš funkcija zove se heš vrednost ili heš kod.
Opis Heš funkcije se prvenstveno koriste za generisanje fiksne dužine izlaznih podataka koji se ponašaju kao reference na originalne podatke. Ovo je korisno kada su originalni podaci suviše glomazni da bi se koristili u celosti. Jedna praktična primena je struktura podataka koja se zove heš tabela u kojoj su podaci smešteni asocijativno. Linearna pretraga imena osobe u listi traje duže kako se dužina liste povećava, ali heširana vrednost može biti skladištiti referencu na originalni podatak, pa tako dobijamo konstantno vreme za pretragu.
Druga upotreba je u kriptografiji, nauci kodiranja i očuvanja podataka. Heš funkcije predstavljaju osnovni princip za PGP algoritam za validaciju podataka. Takođe se koriste da bi se ubrzalo traženje stavki u bazama podataka, detektovanje dupliranih ili sličnih vrednosti u velikom fajlu i pronalaženje sličnih segmenata u DNK sekvenci. Heš funkcija treba da bude deterministički određena, tj. kada se dva puta pozove nad identičnim podacima (npr. dve niske koje sadrže potpuno iste karaktere), funkcija treba da proizvede istu vrednost. To je od ključnog značaja za ispravnost gotovo svih algoritama na osnovu heširanja. Heš funkcije obično nisu invertibilne, što znači da nije moguće rekonstruisati ulaznu vrednost x samo iz njene heš vrednosti h(x). U mnogim aplikacijama uobičajeno je da se nekoliko različitih vrednosti slika u istu heš vrednost i to stanje zovemo heš kolizijama. Ovi sudari mogu izazvati zabunu među objektima, što može doprineti da algoritmi rade sporije i da budu manje precizni. Heš funkcije su dizajnirane tako da se što više smanji verovatnoća sudara. Za kriptografske namene, heš funkcije su projektovane na takav način da je nemoguće rekonstruisati bilo kakav ulaz samo iz heš funkcije, bez trošenja velikog računarskog vremena.
Upotreba
Heš tabele Heš funkcije se prvenstveno koriste u heš tabelama, da se brzo pronađe podatak (definicija u rečniku npr.) ako imamo dat ključ, odnosno reč čije značenje tražimo. Pretpostavimo da je dato n ključeva iz skupa U veličine |U|=M>>n. Ideja je da ključeve smestimo u tabelu veličine m, tako da m nije mnogo veće od n. Konkretno, potrebno je definisati funkciju h: {0, 1, ... , M-1} -> {0, 1, ... , m-1}, heš funkciju, koja za svaki podatak određuje njegovu poziciju na osnovu vrednosti odgovarajućeg ključa. Tipično, domen heš funkcija (skup mogućih ključeva) je veći od svog opsega (broja različitih indeksa tabele), tako da se više različitih ključeva preslikava u isti indeks. Dakle, potrebno je rešiti dva problema: nalaženje heš funkcija koje minimiziraju mogućnost pojave kolizija i postupak za obradu kolizija kada do njih ipak dođe. Iako je veličina M skupa U mnogo veća od veličine tabele m, stvarni skup ključeva koje treba obraditi obično nije veliki. Dobra heš funkcija preslikava ključeve ravnomerno po tabeli - da bi se minimizirala mogućnost kolizija prouzrokovanih nagomilavanjem ključeva u nekim oblastima tabele. U proseku se u svaku lokaciju tabele ovako izabranom heš funkcijom preslikava veliki broj (iz skupa svih mogućih) ključeva, njih M/m. Heš funkcija treba da transformiše skup ključeva ravnomerno u skup slučajnih lokacija iz skupa {0, 1, ... , m-1}. Uniformnost i slučajnost su bitne osobine heš funkcije. Tako, na primer, pogrešno je za heš funkciju od 13-cifrenog matičnog broja uzeti broj koji čine peta, šesta i sedma cifra matičnog broja: te tri cifre su tri najniže cifre godine rođenja, pa za bilo koju veličinu grupe studenata uzimaju manje od desetak različitih vrednosti od 1000 mogućih. Ako je veličina tabele m prost broj, a ključevi su celi brojevi, onda je jednostavna i dobra heš funkcija data izrazom h(x)=x mod m. Ako pak m nije prost broj (npr. m=2k), onda se može koristiti funkcija h(x)=(x mod p) mod m, gde je p prost broj takav da je m<<p<<M. Neugodna je situacija kad su svi ključevi oblika r + k * p za neki celi broj r, jer će svi ključevi imati istu vrednost heš funkcije r. Tada ima smisla uvesti još jedan nivo randomizacije, time što bi se sama heš funkcija birala na slučajan način. Na primer, broj p mogao bi se birati sa unapred pripremljene liste prostih brojeva. Druga mogućnost je da se koriste heš funkcije oblika h(x) = (ax + b mod p) mod m, gde su a≠0 i b slučajno izabrani brojevi manji od p. Vrednosti ove funkcije se izračunavaju na složeniji način, ali je njena prednost da je u proseku dobra za sve ulaze. Razume se da se za sve pristupe u istoj tabeli mora koristiti ista heš funkcija. U mnogo slučajeva potrebno je više nezavisnih heš tabela, ili se tabele često kreiraju i brišu. Tada se za svaku novu tabelu može koristiti druga heš funkcija.
Keš Heš funkcije se takođe koriste za izgradnju keševa za velike skupove podataka uskladištenih u sporim medijima. Keš je generalno jednostavniji od heš tabele za pretragu, pošto svaki sudar može da se reši odbacivanjem starije od dve sudarajuće stavke.
Blumov filter Heš funkcije su esencijalni sastojak u Blumovom filteru, strukturi podataka koja se koristi da se utvrdi da li element pripada datom skupu.
Pronalaženje dupliranih zapisa Kada se skladište zapisi u velikoj običnoj datoteci, može se koristiti heš funkcija da svakom podatku dodeli indeks u tabeli T i da sakupi u isti niz T[i] listu brojeva svih podataka sa istom heš vrednosti i. Kada se tabela popuni, svi duplikati podatka će završiti u istom nizu. Duplikati se onda mogu naći čitanjem svakog niza T[i] koji sadrži dva ili više elementa, njihovim preuzimanjem i poređenjem. Sa tabelom odgovarajuće veličine, verovatno je da će ovaj metod biti mnogo brži nego alternativni pristupi kao što su sortiranje datoteke i upoređivanje svih uzastopnih parova.
Zaštita podataka Heš vrednost u kriptografiji je broj generisan iz niza teksta. Heš vrednost je znatno manja od samog teksta i generisana je heš algoritmom na takav način da je verovatnoća da neki drugi tekst ima istu heš vrednost zanemarljiva.
Pronalaženje sličnih zapisa Heš funkcije se takođe mogu koristiti da lociraju podatke čiji su ključevi slični, ali ne i identični datom ključu ili parove podataka u dugačkoj datoteci koji imaju slične ključeve. Za tu namenu potrebna je heš funkcija koja dodeljuje slične ključeve heš vrednostima koji se razlikuju najviše do m, gde je m mali ceo broj (1,2). Ako formiramo tabelu T sa brojevima svih podataka, koristeći takvu heš funkciju, onda će slični podaci završiti u istom ili u susednom nizu. Onda samo treba proveriti podatke u svakom nizu T[i] i one u nizovima T[i+k], gde se k kreće od -m do m. Ovo se takođe koristi u algoritmima koji pronalaze slične delove audio zapisa u velikoj kolekciji audio zapisa. Za ovo je potrebno da heš funkcija bude neosetljiva na greške u prenosu podataka i na trivijalne promene kao što su jačina zvuka i kompresija."Robust Audio Hashing for Content Identification by Jaap Haitsma, Ton Kalker and Job Oostveen"
Pronalaženje sličnih podniski Ista tehnika se može koristiti da se pronađu jednaki ili slični segmenti u velikim kolekcijama niski. U ovom slučaju ulazna niska se deli na više manjih delova i heš funkcija se koristi za detektovanje potencijalno jednakih delova, kao gore. Rabin-Karp algoritam je relativno brz algoritam koji pretražuje niske u prosečnom vremenu O(n). Baziran je na korišćenju heširanja pri poređenju niski.
Geometrijska heširanja Ovaj princip se široko koristi u kompjuterskoj grafici, računarskoj geometriji i mnogim drugim disciplinama, pri rešavanju mnogih problema u ravni i prostoru, kao što su pronalaženje najbližih parova u skupu tačaka, sličnih oblika, sličnih slika u bazama podataka itd. U ovim aplikacijama, skup svih ulaza je neka vrsta metričkog prostora, a heš funkcija deli taj prostor na mrežu ćelija. Geometrijsko heširanje se takođe koristi u telekomunikacijama za kodiranje i kompresiju multidimenzionalnih signala.
Standardna upotreba heširanja u kriptografiji Neke standardne aplikacije koje koriste heš funkcije uključuju autentifikaciju, integritet poruka, otkrivanje korumpiranih podataka i efikasnost digitalnog potpisa.
Osobine heš funkcije
Determinizam Postupak heširanja mora biti deterministički određen, tj. za svaku ulaznu vrednost mora da se generiše ista heš vrednost. Ovaj uslov isključuje heš funkcije koje zavise od spoljašnjih parametara , kao što su generatori pseudo-slučajnih brojeva. Takođe su isključene funkcije koje zavise od memorijske lokacije objekta koji se hešira, zato što njegova adresa prilikom izvršavanja može da se promeni (na sistemima koji koriste neke metode sakupljača otpadaka npr.).
Uniformnost Svaka heš vrednost treba da se generiše sa približno istom verovatnoćom. Razlog za to je što se troškovi heširanja povećavaju kako broj kolizija raste. Heš tabele često sadrže samo mali podskup važećih ulaza. Na primer, lista članova nekog kluba će sadržati samo stotinak imena, od veoma velikog skupa svih mogućih imena. U ovim slučajevima, kriterijum uniformnosti treba da važi za sve tipične podskupove ulaza koji se mogu naći u tabeli, ne samo za globalni set svih mogućih ulaza.
Opseg promenljivih U mnogim aplikacijama, opseg heš vrednosti može biti različit pri svakom pokretanju programa, ili može da se promeni prilikom samog izvršavanja (npr. kada heš tabela treba da se proširi). U tim situacijama potrebna nam je heš funkcija koja uzima dva parametra - ulazni podatak z i broj n dozvoljenih heš vrednosti.
Kada se heš funkcija koristi za čuvanje vrednosti u heš tabeli koje žive van izvršavanja programa ili kada heš tabela treba da se proširi ili smanji, heš tabela se naziva dinamičkom heš tabelom.
Normalizacija podataka U nekim aplikacijama, ulazni podaci mogu sadržati karakteristike koje su irelevantne za potrebe poređenja. Na primer, kada pretražujemo ime osobe, poželjno bi bilo da se ignoriše razlika između velikih i malih slova. Takvi podaci, ako se smatraju ekvivalentnim, moraju imati istu heš vrednost. Ovo se može postići normalizacijom ulaza pre njegovog heširanja, npr. prebacivanjem svih slova u velika.
Kontinuitet Heš funkcija koja se koristi pri pretrazi sličnih podataka koji se smatraju ekvivalentnim, mora biti kontinualna što je više moguće. Dva ulaza koja se malo razlikuju moraju se slikati u istu ili približno istu heš vrednost. Trebati imati na umu da se kontinualnost može smatrati fatalnom greškom u kriptografiji i sličnim konceptima. Kontinualnost je poželjna za heš funkcije koje se koriste samo u nekim aplikacijama, kao što su heš tabele u kojima se traži najbliži sused datog podatka.
Algoritmi heš funkcija Za većinu tipova funkcija heširanja izbor funkcije zavisi od prirode ulaznih podataka i verovatnoće njihovog korišćenja u nameravanoj aplikaciji.
Trivijalna heš funkcija Ako je podatak koji treba da se hešira dovoljno mali, onda se kao heš vrednost može koristiti sam podatak (predstavljen kao ceo broj u binarnoj notaciji). Trošak izračunavanja ove funkcije efektivno je nula i ova heš funkcija je savršena (identitet). Značenje "dovoljno mali" zavisi od veličine tipa koji se koristi kao heširana vrednost. Na primer, u Javi, heš kod je 32-bitni ceo broj, tako da 32-bitni objekat klase Integer i 32-bitni objekat klase Float mogu jednostavno direktno da se koriste kao heš vrednosti, dok 64-bitni objekti obe klase ne mogu da koriste ovaj metod.
Savršena heš funkcija 240px|мини|десно|Savršena heš funkcija za četiri imena Za heš funkciju koja je injektivna (svaki validan ulaz dodeljuje različitoj heš vrednosti), kažemo da je savršena. Sa takvom funkcijom možemo direktno locirati željeni ulaz u heš tabeli, bez dodatnog traženja.
Minimalno savršeno heširanje 240px|мини|Minimalna heš funkcija za četiri imena