Heš funkcija

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 prakticna 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 odredjena, 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 medju 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 ralič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=2^k), 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 poredjenjem. 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 niski 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.

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š fukcije

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šnih parametara , kao što su generatori pseudo-slučajnih brojeva. Takodje 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 prlikom 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 sadrzati 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š fukcija 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.

Agoritmi 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

Savršena heš funkcija za četiri imena

Za heš funkciju koja je injektivna (svaki validan ulaz dodeljuje razlicitoj 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

Minimalna heš funkcija za četiri imena

Za savršenu funkciju od n ključeva kažemo da je minimalna ako se njen opseg sastoji od n uzastopnih celih brojeva, obično od 0 do n-1. Pored toga što je potreban jedan korak za pronalaženje, minimalna savršena funkcija daje kompaktnu heš tabelu, bez praznih polja. Minimalne savršene funkcije je mnogo teže pronaći nego one savršene sa širim opsegom.

Heširanje uniformno raspoređenih podataka

Ako su ulazi niske fiksne dužine i svaki ulaz može samostalno doći sa uniformnom verovatnoćom (kao što su telefonski brojevi, brojevi registarskih tablica i slično), tada heš funkcija svakom broju grubo dodeljuje svoju heš vrednost. Na primer, pretpostavimo da je svaki ulaz ceo broj z u opsegu od 0 do N-1, a izlaz h mora biti u opsegu od 0 do n-1, gde je N mnogo veće od n. Tada bi se heš funkcija mogla definisati kao h = z mod n ili h = (z * n) / N. Ove jednostavne formule nece raditi ako ulazne vrednosti nisu jednake ili nezavisne. Na primer, korisnici jednog supermarketa će da žive u istoj geografskoj oblasti, tako da je verovatno da će njihovi brojevi pocinjati sa 3 ili 4 iste cifre. U tom slučaju, ako je m 10000 ili slično, formula (z * m) / M koja zavisi uglavnom od vodećih cifara će da generise mnogo kolizija.

Heširanje podataka promenljive dužine

Kada su podaci dugački karakterski nizovi - kao lična imena, adrese web stranica, njihova distribucija je obično vrlo neujednačena, sa komplikovanim zavisnostima. Na primer tekst na bilo kom jeziku ima neuniformnu raspodelu karaktera. Za ovakve podatke mudro je koristiti heš funkciju koja zavisi od svakog karaktera na drugačiji način. U kriptografiji se koristi Merkle Damgrad kostrukcija. Shema za heširanje ovakvih podataka jeste da se razbije ulaz na niz manjih jednica (bitova, bajtova, reči) i da se kombinuju te jednice b[1], b[2], ... , b[m] sekvencijalno, kao što sledi:

S ← S0; //inicijalizuje se stanje
for k in 1, 2, .. m do //učitavaju se ulazne jedinice
  S ← F(S, b[k]);        // kombinovanje jedinice b[k] sa stanjem
return G(S, n)

Stanje varijable S može biti 32-bitni ili 64-bitni neoznačeni ceo broj. U tom slučaju S0 može biti 0, a G(S,n) može biti samo S mod n. Najbolji izbor za F je kompleksni problem i zavisi od prirode podataka. Ako su jednice b[k] pojedinačni bitovi, onda F(S,b) može biti, na primer:

if najvišibit(S) = 0 then
   return 2 * S + b
 else
   return (2 * S + b) ^ P

Ovde najvišiBit(S) označava najznačajniji bit S; operator * označava celobrojno množenje bez prekoračenja, ^ je bitovska ekskluzivna disjunkcija koja se primenjuje na reči, a P je pogodna fiksna reč.

Namenske heš funkcije

U mnogim slučajevima se mogu dizajnirati heš funkcije koje daju mnogo manje sudara nego funckija opšte namene. Na primer, pretpostavimo da su ulazni podaci imena fajlova kao što su FILE0000.CHK, FILE0001.CHK, FILE0002.CHK. Za takve podatke, funkcija koja izdvaja numerički deo k iz imena fajla i vraća k mod n bila bi skoro optimalna.

Roling heš

U nekim aplikacijama, kao što su pretrage podniski, mora da se izračuna funkcija h za svaki k-ti karakter podniske, datog n-tog karaktera niske t, gde je k fiksirani ceo broj, a n je k. Rešenje da se ovde izdvoji svaka podniska s od t i da se posebno izračuna h(s) za svaku podnisku, zahteva k * n operacija. Ali odgovarajućim izborom h, tehnika roling heša može da se koristi pri izračunavanju vrednosti sa trudom proporcionalnim k + n.

Univerzalno heširanje

Shema univerzalnog heširanja je randomizirani algoritam koji bira heš funkcije h medju familijom funkcija takvih da je verovatnoća kolizija bilo koja dva raličita ključa 1/n, gde je n broj različitih heš vrednosti nezavisan od ta dva ključa. Ono nam omogućava (u smislu verovatnoće) da se heš funkcija ponaša kao da smo koristili random funkciju, za bilo kakve ulazne podatke. Kako god, imaćemo mnogo više kolizija nego kod savršenog heširanja i verovatno će nam trebati više operacija nego kod heš funkcije specijalne namene.

Efikasno heširanje niski

Moderni mikroprocesori će omogućiti mnogo bržu obradu, ako 8-bitne karakterske niske nisu heširane obradom jednog karaktera u jednom trenutku, već ako se posmatraju kao nizovi 32-bitnih ili 64-bitnih celih brojeva i heširanjem/usitnjavanjem ovih velikih reči putem aritmetičkih operacija (množenjem konstantom i šiftovanjem bitova). Preostali karakteri niske koji su manji od dužine reči, procesor mora da obradi drugačije (obradom pojedinačnih karaktera). Za ovaj pristup je dokazano da povećava brzinu generisanja heš koda pet ili više puta na modernim mikroprocesorima, sa veličinom reči od 64 bita. Drugi pristup je da se konvertuju niske u 32-bitne ili 64-bitne numeričke vrednosti, a onda primeniti heš funkciju. Jedan od metoda kojim može da se izbegne problem jer niske imaju veliku sličnost (Aaaaaaaa i Aaaaaaab), jeste da se koristi ciklička provera redundansi (CRC algoritam) nad niskom, kako bi se izračunale 32-bitne ili 64-bitne vrednosti. Iako je moguće da dve različite niske imaju isti CRC, verovatnoća je veoma mala. CRC pristup radi za niske proizvoljne dužine.

Lokalno-osetljivo heširanje

Ovde je osnovna ideja da se heširaju ulazne stavke, tako da se one slične slikaju u iste segmente sa velikom verovatnoćom (broj segmenata je mnogo manji od broja mogućih ulaznih stavki). Ovde je cilj da se maksimizuje verovatnoća kolizija sličnih stavki, za razliku od konvencionalnih heš funkcija, gde je osnovni motiv da se kolizije izbegnu.

Poreklo termina

Termin heš dolazi analogno svom ne-tehničkom značenju - "iseckati i pomešati". I zaista, tipična heš funkcija radi kao mod operator, "secka" ulazni domen na mnogo pod-domena koji bivaju izmešani u izlaznom opsegu kako bi se poboljšala uniformnost. Donald Knut napominje da je Hans Piter Lun iz IBM-a prvobitno koristio ovaj koncept u memorandumu iz januara 1953, a da je Robert Moris koristio termin u istraživačkom radu u CACM-u, što je proizvelo da termin iz tehničkog žargona uđe u formalnu terminologiju.

Spoljašnje veze

• Hash Functions and Block Ciphers by Bob Jenkins
• = 25. 10. 2009+21:06:51 The Goulburn Hashing Function (PDF) by Mayur Patel
• Hash Function Construction for Textual and Geometrical Data Retrieval Latest Trends on Computers, Vol.2. стр. 483–489, CSCC conference, Corfu, 2010
• Algoritmi, Miodrag Živković