Hash tabela

Vremenska kompleksnost u Big O notaciji

Heš tabela (eng. Hash table) ili Heš mapa (eng. Hash map) je jedna struktura podataka koja koristi heš funkciju za učinkovito preslikavanje određenih ključeva u njima pridružene vrijednosti. Npr. imena ljudi u telefonske brojeve. Heš tabela se koristi za transformisanje ključa u indeks (heš), to jeste, mjesto u nizu elemenata gdje treba tražiti odgovarajuću vrijednost. Pošto je osnovna namjena heš tabele efikasan pristup podacima, ulazi heš tabele, pored ključeva, mogu da sadrže same zapise ili pokazivače na zapise koji su smješteni negdje drugo. Ovaj pristup je pogodniji sa stanovišta korištenja memorije, pogotovo ako su zapisi veći, jer kad bi se zapisi čuvali u samoj tabeli, mnogo prostora u praznim ulazima u rjeđe popunjenim tabelama bi ostalo neiskorišteno.

U najboljem slučaju, heš funkcija preslikava svaki mogući ključ u zaseban indeks, ali je to u praksi skoro nemoguće. Većina implementacija heš tabela podrazumijeva da su heš kolizije - parovi različitih ključeva s istim heš vrijednostima - obična pojava, i na neki način se brine da se ovaj problem savlada.

U dobro dimenzioniranoj heš tabeli, prosječna cijena (broj računarskih naredbi) svakog pronalaženja ne zavisi o broja elemenata koji se nalaze u tabeli. Mnoge implementacije heš tabela također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji. U mnogim okolnostima, hash tabele se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tabele u širokoj upotrebi u svim vrstama računarskog softvera.

Prednosti upotrebe heš tabela

Glavna prednost heš tabele nad drugim tabličnim strukturama podataka je njena brzina. Ova je prednost uočljivija kada je broj podataka u tabeli velik (hiljadu ili više). Heš tabele su posebno učinkovite kada se maksimalna količina podataka može predvidjeti unaprijed, tako da se veličina strukture može unaprijed alocirati tako da bude optimalna, i ne mora se kasnije mijenjati.

Ako su svi parovi ključeva-vrijednosti fiksirani i poznati unaprijed (pa dodavanja i brisanja nisu dopuštena), prosječna cijena pretrage može se smanjiti pažljivim izborom heš funkcije, veličine tablice i unutrašnjih struktura podataka. Štoviše, tada je moguće napraviti heš funkciju koja ne stvara kolizije. U ovom slučaju ključeve nije potrebno čuvati u tabeli.

Neka je T[i], 0 ≤ i ≤ n-1, heš tabela sa n ulaza i neka ključevi pripadaju nekom skupu mogućih vrijednosti S, tako da K ∈ S. Broj mogućih vrijednosti ključa je tipično veći ili čak mnogo veći od broja ulaza u tabeli. Neka je h heš funkcija koja vrši mapiranje ključeva u adresni prostor tabele. Ovo je ilustrovano slikom 1.1. Tada funckija primijenjena na neki ključ K daje matičnu adresu ključa K, tako da je i = h(K).

Slika 1.1.

Heš funkcija

Funkcija koja vrši mapiranje ključa u opseg indeksa (adresa) u nizu naziva se heš funkcija. Ponekad se ovaj metod heširanja naziva još i tehnikom rasutog adresiranja ili tehnikom direktnog adresiranja. Heš funkcija je funkcija za identificiranje podataka. Takav sažetak naziva se heš vrijednost ili jednostavno heš (hash), a proces izračunavanja te vrijednosti naziva se heširanje (eng. hashing).

Heš funkcije koje su injekcija i sirjekcija, a time i bijekcija nazivaju se randomizirajuće funkcije. Domena heš funkcija u većini slučajeva veća je od kodomene, pa nisu bijekcija. Heš funkcija sabija proizvoljnu poruku na fiksnu veličinu. Najčešće se podrazumijeva da je heš funkcija javna i ne sadrži ključ.

Kolizija

Pošto dva ključa ne mogu biti smještena na istom mjestu u tabeli, ovaj slučaj predstavlja problem koji se naziva kolizijom. Ključevi K_i  i K_j koji se mapiraju na istu matičnu adresu u tabeli se nazivaju sinonimima, a skup sinonima se naziva klasa ekvivalencije. Kolizije je praktično nemoguće izbjeći ukoliko ključevi nisu unaprijed poznati. Zato je neophodno predvidijeti način razrješavanja problema kolizije. U ovom slučaju kolizija se javlja pri umetanju ključa K_j, jer je njegovu matičnu adresu već zauzeo ključ K_i. Tada se ključu K_j mora naći drugo mjesto, ali na takav način da se, pri kasnijem pretraživanju na ključ K_j, pošto se ne nalazi na matičnoj adresi, on može nedvosmisleno locirati. Na Slici 1.1. se vidi da kolizija nastaje za ključeve K₁ i K₄. 

Heš funkcije nezavisne od raspodjele ključeva

• Metod dijeljenja
• Metod množenja
• Metod sredine kvadrata
• Metod sklapanja
• Metod konverzije osnove
• Metod algebarskog kodovanja

Metod dijeljenja

Metod dijeljenja je jedan od najjednostavnijih, ali ipak najčešće korištenih tehnika. Rezultat heš funkcije je ostatak pri dijeljenju cjelobrojnog ključa nekim brojem n koji je manji ili jednak veličini heš tabele.

h( K ) = K mod n

Performanse ovog metoda u smislu smanjenja vjerovatnoće kolizija veoma zavise od pravilnog odabira djelioca n. Pokazuje se da neke vrijednosti djelioca svakako treba izbjegavati. To su:

1. nije dobro da djelioc bude paran broj, jer se tada parni ključevi mapiraju u parne ulaze tabele, a neparni u neparne ulaze. Ako su ključevi pretežno parni ili neparni, samo polovina ulaza će biti opterećena
2. djelioc koji je stepen broja 2, n = 2ⁱ, iako omogućava lako izračunavanje ostatka jednostavnim izdvajanjem donjih i bitova ključa, upravo zbog toga nije preporučljiv jer ne zavisi od svih bitova ključa. Tako bi, u slučaju da su ključevi znakovni nizovi sa istim završnim znacima, vjerovatnoća kolizije znatno porasla.
3. djelioc kao stepen broja 10 nije pogodan ako su ključevi decimalni brojevi
4. u slučaju da su ključevi kongruentni po modulu d, da se izbjegava vrijednost n koja nije uzajamno prosta sa d. 

Metod množenja

Metod je zasnovan na množenju ključa sa pogodno odabranom realnom konstantom čija je vrijednost između 0 i 1. Zatim se od proizvoda uzme samo dio iza decimalne tačke, što bi trebalo da predstavlja slučajan broj, koji zavisi od svh cirafa ključa. Na kraju se dobijeni broj pomnoži sa veličinom tabele i dobije pozicija ulaza u tabelu. Pokazuje se da izbog n nije mnogo kritičan, pa se lako izračunavanje može uzeti da je n = 2^p. 

Metod sredine kvadrata

U metodi sredine kvadrata numerička reprezentacija ključa se pomnoži sama sa sobom, pa se sa fiksnih pozicija iz sredine kvadrata uzme onoliko cifara koliko je potrebno za adresiranje tabele. Opravdanje za ovakav metod se nalazi u činjenici da obično cifre u sredini kvadrata zavise od svih cifara u ključevima.

Metod sklapanja

Sklapanje je, također, jednostavan metod koji se zaniva na diobi ključa na dijelove iste dužine koja odgovara broju cifara potrebnih za adresiranje tabele. Zatim se svi dijelovi saberu, a prijenos se ignoriše. 

Metod konverzije osnove

Ako je ključ dat u brojnom sistemu sa osnovom q, metod konverzije osnove ( radix transformation ) tretira ključ kao broj u osnovi q ( q > p ).

PRIMJER:

Ako ključ ima vrijednost 6154 u dekadnom brojnom sistemu ( p = 10 ), interpretacijom u sistemu sa osnovom q = 13, dobija se:

$6*13^{3}+1*13^{2}+5*13^{1}+4*13^{0}$

pa se izdvoji potreban broj cifara. Da bi se smanjila vjerovatnoća kolizije, q se odabire tako da bude uzajamno prosto sa p, baš kao i u ovom primjeru.

Metod algebarskog kodovanja

Algebarsko kodovanje se zasniva na aritmetici po modulu 2 sa polinomima i predložen je za hardversku implementaciju. Tako se, ključ čija je binarna predstava sa r bitova

( k_r-1, ... ,k₀ )  tretira kao polinom K(x) = k_r-1 x ^r-1 + ... + k₀. Ako je veličina tabele n = 2^m, onda se izabere polinom reda m, P(x) = x^m + p_m-1x^m-1 + ... + p₀, pa se izračuna 

$K(X){\pmod {P(X)}}=h{\scriptstyle {\text{m-1}}}*X^{m}-1+...+h{\scriptstyle {\text{0}}}$

Koeficjenti dobijenog polinoma predstavljaju rezultat heš funkcije u binarnom obliku ( h_m-1,...,h₀ ). Pokazuje se da sa odabirom pogodnog polinoma smanjuje vjerovatnoća kolizije. 

 == Heš funkcije zavisne od raspodjele ključeva == Kada je skup ključeva unaprijed poznat, onda je moguće naći efikasnu heš funkciju koja će smanjiti broj kolizija. Jedna od heurističkih metoda koja se koristi se zasniva na principu ekstrakcija koja se naziva analiza cifara. Prvo se analizira skup numeričkih reprezentacija vrijednosti svih ključeva, pa se napravi tabela koja za svaku poziciju ključa daje broj pojavljivanja pojedinih cifara na toj poziciji u svim ključevima. Zatim se selektuje onoliko pozicija koliko je cifara potrebno da se adresira heš tabela tako što se odaberu kolone tabele koje pokazuju najmanje varijacije pojavljivanja različitih cifara.

U nekim slučajevima je za skup ključeva S poznata raspodijela vrijednosti, pa je moguće pronaći heš funkciju koja ključeve iz S mapira u ulaze tabele  (0..n-1) uniformno. Ova funkcija se nalazi preko diskretne kumulativne funkcije raspodijele F_z(x) koja se definira kao:

$f{\scriptstyle {\text{z}}}(x)=P(Z\leq x)$

što znači da je jednaka vjerovatnoći da slučajna promjenljiva Z nije veća od neke vrijednosti x. Ukoliko skup S sadrži m ključeva K₁ <...< K_m onda ova funkcija ima diskretnu uniformnu raspodijelu na ( 1/m, 2/m,..., 1 ) što znači da je:

$P(F{\scriptstyle {\text{z}}}(Z))\leq {\frac {i}{m}}$ za za 0 ≤ i ≤ m, pa je $F{\scriptstyle {\text{z}}}(K{\scriptstyle {\text{1}}})={\frac {1}{m}}$ , $F{\scriptstyle {\text{z}}}(K{\scriptstyle {\text{2}}})={\frac {2}{m}}$ , ... , $F{\scriptstyle {\text{z}}}(K{\scriptstyle {\text{m}}})=1$

Pošto je cilj da h(K) bude uniformna u opsegu tabele: $P(h(K)=i)={\frac {1}{n}}$ za 0 ≤ i ≤ n-1 , onda se ona može dobiti kao:

$h(K)=\lceil nF{\scriptstyle {\text{z}}}(K)\rceil -1$

Razriješavanje kolizija

Koriste se dva načina:

1. Otvoreno adresiranje
2. Ulančavanje

Otvoreno adresiranje

Pojava kolizije, kada je matična adresa ključa zauzeta, u tehnici otvorenog adresiranja, se razrješava tako što se za taj ključ na sistematičan način nalazi neka druga lokacija u okviru same tabele. Osnovna ideja je formulisati pravilo koje za svaki ključ daje ispitni niz, kao niz adresa u tabeli koje se provjeravaju pri umetanju novog ključa ili pretraživanju. Ako treba da se umetne novi ključ, a matična adresa zauzeta, onda se pokušava sa sljedećom adresom u ispitnom nizu, sve dok se ne nađe slobodna lokacija. Pri pretraživanju na zadani ključ, prolazi se isti ispitni niz adresa koji se za ovaj ključ generiše pri umetanju, sve dok se ključ pronađe ili se dođe do prazne lokacije u tabeli. U drugom slučaju se pretraživanje smatra neuspjelim, jer, da ključ postoji u tabeli, primjena istog isptinog niza kao pri umetanju garantuje da bi on bio pronađen prije pojave prve slobodne lokacije. 

Umetanje ključa K u tabelu T

Pretraživanje na zadati ključ K je realizovano funkcijom HASH – SEARCH koja je dosta slična postupku pri umetanju. 

Pretraživanje na zadani ključ K u tabeli T

Problem brisanja nameće određene teškoće. Prilikom brisanja se ne može ključ jednostavno obrisati iz tabele i taj ulaz proglasiti slobodnim, jer se može prekinuti ispitni niz do nekih drugih ključeva. Ovaj problem se razrješava tako što se na mjestu obrisanog ključa ostavi kod (Npr. deleted ) koji je različit od svih vrijednosti ključeva, ali i od vrijednosti empty. Sada se pri pretraživanju ispitni niz ne prekida kad se dođe do lokacije sa vrijednošću deleted, već se preskače kao da je zauzeta i ispitni niz se dalje generiše. 

Ulančavanje

Tehnike otvorenog adresiranja imaju dva nedostatka. Prvi problem nastaje u primjenama gdje ima dosta brisanja, jer se zauzete lokacije ne oslobađaju, a premještanje može biti vrlo složeno. Drugi problem je neefikasno pretraživanje kod tabele sa većom popunjenošću, jer se u ispitnom nizu mogu naći i adrese zauzete ključevima koji nisu sinonimi traženog ključa. Ovi problemi se rješavaju korištenjem tehnike ulančavanja.

Suština ove tehnike je da se sinonimi ulančavaju u liste čija se zaglavlja nalaze na matičnim adresama. U ovom slučaju zauzeti ulaz heš tabele sadrži samo pokazivač na listu sinonima koji odgovaraju toj matičnoj adresi, dok se sama lista nalazi u dinamičkoj oblasti memorije. Pošto svaka lista odgovara samo jednoj klasi ekvivalencije, ova varijanta ulančavanja se naziva odvojeno ulančavanje ( separate chaining ). Operacije sa ključevima kod tehnike ulančavanja su jednostavnije nego kod otvorenog adresiranja. Pretraživanje na zadati ključ se vrši prolaskom kroz ulančanu listu čije se zaglavlje nalazi na matičnoj adresi. Ako se cijela lista prođe, a ključ se ne pronađe, pretraživanje je neuspješno. Umetanje novog ključa može da se vrši na početak liste, ako se zna da ključ nije u tabeli, ili na kraj liste ako treba prvo provjeriti da li je ključ unesen, jer se tu završava neuspješno pretraživanje. U cilju poboljšanja efikasnosti neuspješnog pretraživanja i umetanja, ulančana lista sinonima može da se drži i uređenom po vrijednosti ključa, tako da se pri umetanju ključ mora postaviti na mjesto koje mu po poretku odgovara. Za razliku od otvorenog adresiranja, operacija brisanja je mnogo jednostavnija jer se svodi na jednostavno povezivanje liste. Zbog brisanja je pogodno da lista bude dvostruko povezana. Može se očekivati da prosječna dužina liste bude mala, pa su operacije sa heš tabelom brze. Kad bi liste bile duge, onda bi bilo efikasnije da se umjesto liste koristi binarno stablo pretraživanja. 

Izvori

1. Milo Tomašević - Algoritmi i strukture podataka (2008) ISBN: 978-86-7466-328-8
2. Thomas H. Cormen, Charles_E._Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms 3. izd.
3. Steven D. Galbraith - Mathematics of Public Key Cryptography (2012 ) ISBN: 9781139012843