% Hash funkcije - pripremni materijal % SPA2, DMI-PMF-UNS, www.dmi.rs % 2015 Heš kod i jednakost u programskom jeziku Java ============================================= U programskom jeziku Java u svakoj klasi mogu (i često i trebaju) da postoje metodi public int hashCode() public boolean equals(Object o) Oni omogućavaju vrlo efikasne operacije nad velikim skupovima objekata, ali je bitno da uzajamno imaju konzistentno ponašanje. Tačnije, ako su dva objekta jednaka u skladu sa `equals` tada im i heš vrednost koju vraća `hashCode` mora biti ista. Obrnutno ne mora da važi, odnosno može postojati neograničeni broj različitih objekata koji imaju isti heš kod. Isto tako ako dva objekta imaju različih heš, tada oni ne bi smeli biti jednaki kad se pita `equals`. No i ovde ne važi obrnuto, odnosno ako su dva objekta različiti, heš kod im ne mora biti različit. Zbog ovih podrazumevanih odnosa je jako bitno da se ova dva metoda pišu zajedno, odnosno da se ne menja samo jedan bez promena u drugom. U opštem slučaju ako se ovo ponašanje ne promeni reimplementacijom ovih metoda, objekti u Javi će za ova dva metoda da vraćaju vrednosti koje se odnose na sam pokazivač u memoriji. Odnosno dva objekta su isti samo ako se bukvalno isti objekat u memoriji, bez obzira na to da li imaju isti sadržaj. Isto tako će sam heš kod biti generisan od vrednosti samog pokazivača, a ne od sadržaja objekta. Jako često ovo nije poželjno ponašanje, te se zbog toga moraju pisati svoji metodi. Heš kod je uvek poželjno pisati tako da se dobija što više različitih vrednosti za različite instance objekata. U idealnom slučaju bi se za svaki različit objekat dobijao različit heš kod, međutim to u praksi često nije moguće. Klasa `String` ima redefinisana oba ova metoda. Heš kod koji se dobija za ovu klasu je veoma kvalitetan i uglavnom se vredi osloniti na njega za polja ovog tipa. Ocene kvaliteta funkcije ======================== Kvalitetna heš funkcija ravnomerno raspoređuje elemente po celoj tabeli, odnosno dobijamo podskupove sličnih veličina. Za poređenje kvaliteta heš funkcija se mogu koristi različite mere. Prva je procentualna popunjenost tabele -- odnosno procenat podskupova (listi) u kojima postoji bar po jedan element. Nešto komplikovanija mera je $\chi^2$ \emph{(hi-kvadrat)} test. \begin{equation} \chi ^2 = \sum_{i=1}^{n} \frac{(K_i - E)^2}{E} \end{equation} gde je $K_i$ - broj elemenata u podskupu $i$, a $E$ - očekivan broj elemenata u podskupu, odnosno idealna vrednost koja je jednaka količniku ukupnog broja elemenata i broja skupova. Iako deluje relativno komplikovano, ovo nam zapravo daje dobru ocenu koliko su (ne)ravnomerno raspoređeni elementi. U idealno slučaju bi sve $K_i$ vrednosti bile jednake sa $E$ i imali bi da je vrednost testa nula. U opštem slučaju se naravno javljaju odstupanja od proseka, a pošto kvadriramo udaljenosti, $\chi^2$ brzo raste ukoliko ima većih anomalija. Pri pisanju heš funkcije treba ciljati na što veću procentualnu popunjenost tabele, idealno je to 100\% za veću količinu podataka. Sa druge strane, $\chi^2$ test predstavlja ravnomernost duzina listi, te bi trebao ostajati relativno konzistentan. Kod dobrih heš funkcija koje ravnomerno rasporedjuju elemente ovaj test često daje niže vrednosti tek za veći broj ubačenih elemenata, pošto tek onda dolaze do izražaja statističko ravnomerno raspoređivanje. Dobre vrednosti za ovaj test za heš funkciju zavise od podataka sa kojima se radi, ali u opštem slučaju treba ciljati da budu niže od broja podskupova. Primeri ======= U sledećim primerima će se razmatrati različiti tipovi podataka i kako se oni efikasno mogu skladištiti u heš tabelama. Uglavnom će se razmatrati ideje heš tabele koja ima tačno određen broj podskupova i pratiti njihovu pokrivenosti i hi kvadrat meru. Tipično će se razmatrati razlitiče veličine ovih tabela, na primer 101, 503 i 997 radi bolje ilustracije uticaja veličine na lošije heš funkcije. Korišćenje kancelarija ---------------------- Treba da čuvamo podatke o korišćenju kancelarija u toku jednog dana i da omogućimo što bržu proveru da li je neka konkretna osoba koristila neku konkretnu kancelariju. Podaci vezuju prezimena za identifikacione brojeve soba. Naravno moguće je da više ljudi koristilo istu kancelariju, a moguće je i da je neko više puta koristio istu -- ovo će se u tabeli skladištiti samo jedan put, pošto nas samo zanima ko je bio unutra, a ne koliko puta. Uzmimo sledeću definiciju klase ```Java class Kancelarija { private int broj; private String prezime; .... } ``` U datim fajlovima nema više od~100 prostorija, a i postoji samo oko~60 različitih prezimena (tj zaposlenih). Broj sobe tipa `int` i deluje kao "očigledan" kandidat za heš kod. Validno bi bilo da se ova informacija vraća kao heš kod: ```Java public int hashCode() { return broj; } ``` Pogledajmo primere učitavanja većeg broja podataka u heš tabele sa različitim brojem podskupova, ako imamo tako definisanu heš funkciju: Elements : 4885 Percent full: 99.01 Chi square : 67.3081 'Columns' : 101 Elements : 4885 Percent full: 19.88 Chi square : 19778.4749 'Columns' : 503 Elements : 4885 Percent full: 10.03 Chi square : 44000.6551 'Columns' : 997 Budući da ima samo 100 soba, primećujemo da vrednosti nisu zadovoljavajuće čim imamo veće tabele, odnosno imamo manje od 20\% pokrivenosti tabele sa 503 mesta i oko 10\% za 997 mesta. Slično važi i za prezimena, budući da ih ima samo šestdesetak, bez obzira na koliko je dobar heš kod u klasi `String`, možemo imati samo šestdesetak različitih rezultata, odnosno dobijamo još gore rezultate, čak i za relativno malu tabelu sa 101 podskupom. Ovde treba obratiti pažnju i da je moguće da imamo `null` polje. ```Java public int hashCode() { if (prezime != null) { return prezime.hashCode(); } else { return 0; } } ``` Elements : 4885 Percent full: 49.50 Chi square : 6320.7484 'Columns' : 101 Elements : 4885 Percent full: 11.53 Chi square : 39251.8342 'Columns' : 503 Elements : 4885 Percent full: 5.72 Chi square : 85190.9396 'Columns' : 997 Očigledno je potrebno kombinovati ove dve vrednosti. Možemo ih jednostavno samo sabrati: ```Java public int hashCode() { int rez = 0; if (prezime != null) { rez += prezime.hashCode(); } rez += broj; return rez; } ``` Dobijamo dosta bolje rezultate u testovima: Elements : 4885 Percent full: 100.00 Chi square : 20.7468 'Columns' : 101 Elements : 4885 Percent full: 100.00 Chi square : 720.2837 'Columns' : 503 Elements : 4885 Percent full: 99.00 Chi square : 1341.3007 'Columns' : 997 Množenje će tipično dati bolje vrednosti nego sabiranje kad imamo vrednosti koje su jako blizu jedne drugima (što brojevi kancelarija koji idu zaredom jesu), pošto pomaže u "raspipanju" vrednosti na većem opsegu. Na primer ```Java public int hashCode() { int rez = 1; if (prezime != null) { rez *= prezime.hashCode(); } rez *= broj; return rez; } ``` Elements : 4885 Percent full: 100.00 Chi square : 78.8864 'Columns' : 101 Elements : 4885 Percent full: 100.00 Chi square : 483.8686 'Columns' : 503 Elements : 4885 Percent full: 99.10 Chi square : 951.0727 'Columns' : 997 Iz rezultata se vidi da se konzistentno dobijaju dobre vrednosti sa ovakvom heš funkcijom. Naročito je bitno što nam vrednost hi kvadrat testa govori da imamo odstupanje u veličinama podskupova u proseku manje od jedan. Istovremeno je bitno da se i `equals` definiše da koristi ista polja. Metod zahteva da parametar bude tipa `Object`, pa uvek moramo da krenemo od toga. Najjednostavnija varijanta zahteva da proverimo da li je prosledjeno nešto što je iste klase kao i naš objekat, pa tek onda možemo da menjamo tip i da poredimo polja. ```Java public boolean equals(Object o) { // proveravamo da li je objekat sa // kojim se poredimo Kancelarija if (o instanceof Kancelarija) { // pretvaramo objekat u kancelariju Kancelarija k2 = (Kancelarija) o; // poredimo polja if (prezime.equals(k2.prezime) && broj == k2.broj) { return true; } } return false; } ``` Međutim potpuna verzija `equals` metoda treba da proveri da li je u pitanju baš ista klasa kao naša (moguće da je neki naslednik koji tehnički ne mora biti isti), te da tu uzme u obzir i da je moguće da nam je prosleđen `null` što nikako ne može biti isto kao i naš objekat. Dalje se može ubrzati postupak proverom da li su u pitanju pokazivači na isto mesto pošto nema potrebe za proverama onda. Potpuna verzija bi izgledala ovako: ```Java public boolean equals(Object o) { // Objekat je identican if (this == o) { return true; } // Null je uvek razlicit if (o == null) { return false; } // Ako su klase razlicite, objekti ne mogu bili jednaki if (getClass() != o.getClass()) { return false; } // pretvaramo objekat u kancelariju Kancelarija k2 = (Kancelarija) o; // Prvo proveravamo broj if (broj != k2.broj) { return false; } // A potom prezime if (!Objects.equals(prezime, k2.prezime)) { return false; } // Proverili smo polja i sva su jednaka return true; } ``` Razmotrimo sledeću modifikaciju klase: recimo da se i dalje želi samo pratiti u tabeli ko je bio u kojoj kancelariji, ali da su negde već definisani objekti u kojima se skladišti i vreme poslednjeg pristupanja, ili recimo neki dodatni opis zašto je neko bio u kancelariji. ```Java class KancelarijaVreme { private int broj; private String prezime; private int pristupDan, pristupSat; private String komentar; } ``` Budući da za naše potrebe nije bitno kad je pristupano niti zbog čega, i dalje bi trebali da koristimo iste kodove za `equals` i za `hashCode` pošto nam je dosta da ubacimo samo jedan objekat za svako pojedinačno korišćenje. Negde druge se naravno oni mogu koristiti za detaljije zapise, ali nas to trenutno ne interesuje. Gadjanje mete ------------- Potrebno je da čuvamo podatke o rezultatima gadjanja mete. U nizu se nalazi do 20 brojeva izmedju i uključujući 0 i 10. Recimo da je klasa definisana na sledeći način: ```Java public class Gadjanje { private int[] rezultati; private static int MAX_DUZ = 20; ... } ``` Pošto je moguće (i vrlo verovatno zapravo) da neko nije gađao svih 20 puta, u podacima će biti nizovi različitih dužina. U skladu sa tim je i format za unos takav da je prvi broj u redu zapravo broj gađanja, koji određuje veličinu niza. Funkcija jednakosti bi izgledala ovako: ```Java public boolean equals(Object o) { // Objekat je identican if (this == o) { return true; } // Null je uvek razlicit if (o == null) { return false; } // Ako su klase razlicite, objekti ne mogu bili jednaki if (getClass() != o.getClass()) { return false; } Gadjanje o2 = (Gadjanje) o; // proveravamo da li je polje null pre dalje provere if (rezultati != null && o2.rezultati != null) { if (o2.rezultati.length == rezultati.length) { for (int i = 0; i < rezultati.length; i++) { if (o2.rezultati[i] != rezultati[i]){ // cim je nesto razlicito nisu isti return false; } } // ako se sve vrednosti slazu isti su return true; } return false; } else { // vracamo da li su oba null, tj da li su jednaki return (rezultati == null && o2.rezultati == null); } } ``` "Očigledno" rešenje je samo sabrati sve ove vrednosti i vratiti broj. Međutim ovakvo rešenje daje maksimalno 200 različitih vrednosti i dosta loše vrednosti u tabeli: Elements : 9049 Percent full: 100.00 Chi square : 314.5114 'Columns' : 101 Elements : 9049 Percent full: 27.63 Chi square : 34841.7383 'Columns' : 503 Elements : 9049 Percent full: 13.94 Chi square : 77947.1553 'Columns' : 997 U ovakvoj strukturi, pozicija u nizu bi trebalo da bude značajna za krajnje heš vrednosti. Da bi se to postiglo jedan pristup je množenje brojeva sa svojim pozicijama ili različitim (prostim) brojevima. Za ovaj primer u kome je dužina niza raznolika i ima više "početnih" elemenata je dodatno pogodno da se težine primenjuju unazad, pa recimo možemo uvesti da prvi element ima težinu 21, a poslednji u nizu od 20 elemenata težinu 2. Dodatno to možemo unaprediti množenjem prostim brojem pri svakom sabiranju, tako da se ta množenja akumuliraju na prvim elementima. ```Java public int hashCode() { int rez = 0; if (rezultati != null) { for (int i = 0; i < rezultati.length; i++) { rez = (rez + rezultati[i] * (MAX_DUZ + 1 - i)) * 7; } } return rez; } ``` Elements : 9084 Percent full: 100.00 Chi square : 101.7743 'Columns' : 101 Elements : 9084 Percent full: 100.00 Chi square : 415.1915 'Columns' : 503 Elements : 9084 Percent full: 100.00 Chi square : 981.2660 'Columns' : 997 Tabla za igru XO ---------------- Zadatak nam je da efikasno čuvamo podatke o pozicijama u igri XO, odnosno matrice 3x3, u kojima su vrednosti -1 za "X", 0 za prazno polje i 1 za "O". Npr: ``` 1 0 -1 O _ X 1 1 -1 O O X -1 0 1 X _ O ``` predstavlja poziciju u kojoj je ``O'' pobedio/la. Polja klase bi se mogla definisati na sledeći način: ```Java public class XO { public static final int DIM = 3; private int[][] tabla = new int[DIM][DIM]; .... } ``` Poredjenje ovakvih objekata bi naravno trebalo da pojedinačno ispituje elemente matrice, na primer: ```Java public boolean equals(Object o) { // Objekat je identican if (this == o) { return true; } // Null je uvek razlicit if (o == null) { return false; } // Ako su klase razlicite, objekti ne mogu bili jednaki if (getClass() != o.getClass()) { return false; } // menjamo tip da mozemo da poredimo XO o2 = (XO) o; // posto je u ovoj klasi uvek inicijalizovano polje table // i uvek je DIM x DIM ne moramo proveravati null for (int i = 0; i < DIM; i++) { for (int j = 0; j < DIM; j++) { if (o2.tabla[i][j] != tabla[i][j]) { return false; } } } return true; } ``` Za ovaj primer vredi prvo razmotriti da neke relativno očigledne tehnike nisu efikasne: sumiranje ovakve matrice daje vrednosti do plus ili minus 9, odnosno ima samo 19 različitih vrednosti, što bi predstavljalo jako lošu pokrivenost tabele. Dodatno, vrlo često će rezultat biti 0 i uopšteno će biti više tablica koje su bliže "sredini" rezultatom, što opet dovodi do loše ravnomernosti raspoređivanja elemenata. Dakle ovako definisan metod za heš će davati dosta loše rezultate: ```Java public int hashCode() { int rez = 0; for (int i = 0; i < DIM; i++) { for (int j = 0; j < DIM; j++) { rez += tabla[i][j]; } } return rez; } ``` Elements : 4424 Percent full: 9.90 Chi square : 87664.1198 'Columns' : 101 Elements : 4424 Percent full: 1.99 Chi square : 454193.0719 'Columns' : 503 Elements : 4424 Percent full: 1.00 Chi square : 904604.2717 'Columns' : 997 Efikasnost se u ovakvoj strukturi dobija davanjem "težine" elementima. Odnosno ne treba gledati jednako ako je "1" u gornjem levom uglu i u sredini. Npr u jednostavnijim varijantama se može zbir iz svakog reda množiti različitim brojem. Još bolji rezultati se dobijaju uvodjenjem još detaljnijih "težina": pri sumiranju reda množiti različito, ili čak imati specijalne proste brojeve za svako polje ili uvoditi dodatne operacije. Takodje treba uzeti u obzir i to da sabiranje pozitivnih i negativnih vrednosti može da dovede do "međusobnog poništavanja", te da nula vrednosti ne pomažu zbiru, naročito kad se uvedu težine koje se množe sa vrednostima polja. Jedan način da se ovo uradi u konkretnom slučaju je da se pri računanju heša vrednosti u matrici sabiraju sa 2, pa time imamo 1,2,3 umesto -1,0,1, što dovodi do veće različitosti. Kombinovanjem ovih ideja se mogu napraviti `hashCode` metodi koji će rezultovati sa hi kvadrat vrednostima manjim od broja podskupova ("kolona"), što se ostavlja za samostalnu vežbu.