% Hash funkcije - pripremni materijal % SPA2, DMI-PMF-UNS, www.dmi.uns.ac.rs % 2019 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. Nažalost, nizovi nemaju nijednu od ove dve funkcije definisane kako treba, pa kada se radi sa njima, mora se uložiti napor da se pojedinačni elementi u nizu porede, odnosno hešuju. 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. Za ove potrebe je napravljena klasa `StatSet` koja implementira klasični Java skup (zapravo u pozadini i koristi `HashSet` za skladištenje podataka), ali osim toga vodi računa i o tome kako su se elementi rasporedili i može da da informacije o tome. Najlakše se dolazi do većine ovih informacija metodom `printStats`. Prva mera kvaliteta je broj različih heš vrednosti elemenata u skupu, a ispisuje se zajedno sa procentom u odnosu na ukupni broj elemenata u skupu. U idealnom slučaju je ovo 100%, odnosno svi elementi imaju različite vrednosti, mada nekad u realnim primenama ovo nije lako izvodljivo. Sledeći bitan uvid u raspodelu elemenata je koliko su veliki podskupovi, odnosno koliko su veliki lanci pretraga pri operaciama nad skupom. Ispisuje se prosečna vrednost dužine lanaca, ali i standarno odstupanje (npr 2.12 +- 1.11). U idealnoj raspodeli svi lanci su dužine tačno 1. Osim ovog podatka se ispisuje i dužina najdužeg lanca u skupu, koja daje predstavu o tome koliko je pretraživanje u najgorem slučaju. Ovaj broj takođe treba da je što manji. Program ispisuje i vrednosti $chi^2$ testa, o čemu postoji još komentara na kraju ovog dokumenta, ali se inače neće dublje razmatrati, nego se ostavlja zainteresovanima da pogledaju. Primeri ======= U sledećim primerima će se razmatrati različiti tipovi podataka i kako se oni efikasno mogu skladištiti u heš tabelama. Podaci se smeštaju u instancu `StatSet` koja nam daje statistike o njihovoj raspodeli. Svi dati primeri se mogu pokretati iz odgovarajućih klasa pošto postoje `main` metodi koji pokreću program `TestHash` sa odgovarajućim parametrima. 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: ``` Number of elements: 4885 Different values: 100 ( 2.05 %) Avg. search chain len.: 48.85 +- 2.99 Longest search chain: 56 ``` Budući da ima samo 100 soba, može biti i samo 100 različitih heš vrednosti, te rezultati nisu zadovoljavajući. 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. Bitna razlika u odnosu na prethodnu verziju gde smo koristili samo `int` koji je primitivni tip, ovde se mora voditi računa i o tome da samo polje može biti `null`, tj ne sme se desiti da `hashCode` baci izuzetak zbog ovoga. ```Java public int hashCode() { if (prezime != null) { return prezime.hashCode(); } else { return 0; } } ``` ``` Number of elements: 4885 Different values: 61 ( 1.25 %) Avg. search chain len.: 80.08 +- 3.96 Longest search chain: 89 ``` Očigledno je potrebno kombinovati ove dve vrednosti, odnosno iskoristiti sve različitosti u podacima koje postoje.. Možemo ih jednostavno samo sabrati: ```Java public int hashCode() { int rez = 0; if (prezime != null) { rez += prezime.hashCode(); } rez += broj; return rez; } ``` Dobijamo izuzetne rezultate u testovima, pošto su sve vrednosti različite: ``` Number of elements: 4885 Different values: 4885 (100.00 %) Avg. search chain len.: 1.00 +- 0.00 Longest search chain: 1 ``` 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. Takođe se preporučuje da se polja porede jedno po jedno, pošto je kod pregledniji i lakše se menja, nego kad se kombinuju upiti kao gore. 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. Na početku je već bilo napomenuto da nizovi nemaju `hashCode` i `equals` implementirane na načine koji bi odgovarao ovoj situaciji, tako da se mora implentirati pojedinačno poređenje elemenata, naročito kod ovakvih situacija sa dodatnim značenjima elemenata. 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 su polja null pre dalje provere if (rezultati == null && o2.rezultati != null) { return false; } if (rezultati != null && o2.rezultati == null) { return false; } // ako u obe instance nije null, poredimo delove if (rezultati != null && o2.rezultati != null) { // proverimo duzinu. if (o2.rezultati.length != rezultati.length) { return false; } // ako je ista duzina proveravamo elemente for (int i = 0; i < rezultati.length; i++) { if (o2.rezultati[i] != rezultati[i]) { // cim je nesto razlicito nisu isti return false; } } } // ako nije bilo razlika, vracamo da je sve ok return true; } ``` “Očigledno” rešenje je samo sabrati sve ove vrednosti i vratiti broj. Međutim ovakvo rešenje u najboljem slučaju daje maksimalno 200 različitih vrednosti, pri čemu bi se očekivala i dosta neravnomerna raspodela (sume pri sredini su daleko verovatnije od najviših i najnižih). Na konkretnim podacima su vrednosti u tabeli nešto gore od očekivanih 200 vrednosti: ``` Number of elements: 9049 Different values: 139 ( 1.54 %) Avg. search chain len.: 65.10 +- 37.98 Longest search chain: 118 ``` 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. ```Java public int hashCode() { int rez = 0; if (rezultati != null) { for (int i = 0; i < rezultati.length; i++) { rez += rezultati[i] * (MAX_DUZ + 1 - i); } } return rez; } ``` Vrednosti su dosta bolje, iako još uvek nisu na viskom nivou. ``` Number of elements: 9049 Different values: 1411 (15.59 %) Avg. search chain len.: 6.41 +- 3.89 Longest search chain: 20 ``` Problem je zapravo što brojevi nisu dovoljno različiti. Pošto znamo da su rezultati najviše 10, možemo to iskoristiti da u suštini sastavimo višecifreni broj na sledeći način: ```Java for (int i = 0; i < rezultati.length; i++) { rez = (rez + rezultati[i]) * 10 ; } ``` Ovim smo dobili dosta bolje vrednosti: ``` Number of elements: 9049 Different values: 8911 (98.47 %) Avg. search chain len.: 1.02 +- 0.14 Longest search chain: 4 ``` Možemo uočiti i sledeće - ako na početku nekog niza stoje 0, one će biti ignorisane u ukupnom zbiru, te samim tim možemo imati različite nizove koji vraćaju iste vrednosti. Ovo možemo ispraviti tako što ćemo pojedinačne rezultate povećavati za 1, odnosno pomeriti ih iz opsega 0-10 na 1-11. U skladu sa tim treba da povećamo i broj kojim množimo na 11. ```Java public int hashCode() { int rez = 0; if (rezultati != null) { for (int i = 0; i < rezultati.length; i++) { rez = (rez + rezultati[i] + 1) * 11 ; } } return rez; } ``` ``` Number of elements: 9049 Different values: 9049 (100.00 %) Avg. search chain len.: 1.00 +- 0.00 Longest search chain: 1 ``` 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 final 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; } ``` ``` Number of elements: 4424 Different values: 18 ( 0.41 %) Avg. search chain len.: 245.78 +- 253.74 Longest search chain: 674 ``` 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. Jedno od mogućih rešenja koje daje dobre rezultate je zapravo jako slično onome viđeno kod niza - ako stalno množimo sa brojem koji je veći od mogućih vrednosti jednog elementa, automatski su sva mesta pomnožena različitim koeficijentom. Ovo možemo kombinovati sa pomeranjem pojedinačnih elemenata na pozitivne vrednosti, mada se dobri rezultati mogu postići i bez toga. ```Java public int hashCode() { int rez = 0; int koef = 3; for (int i = 0; i < DIM; i++) { for (int j = 0; j < DIM; j++) { rez = koef * (rez + (tabla[i][j] + 2)); } } return rez; } ``` ``` Number of elements: 4424 Different values: 4424 (100.00 %) Avg. search chain len.: 1.00 +- 0.00 Longest search chain: 1 ``` Dodatne napomene ================ Hi kvadrat ocena kvaliteta heš funkcije ----------------------------------- 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. Program daje vrednosti za ovaj test i u odnosu na idealan slučaj kada je broj lanaca/podskupova jednak sa brojem elemenata, kao i za realan broj podskupova (tj različitih vrednosti elemenata). Ispitivanje različitosti dobijenih podataka ------------------------------------------- Kada se dobiju nepoznati podaci koje treba obraditi i za njih odrediti heš funkcije, nekad vredi prvo probati saznati više o različitostima dobijenih podataka. Kod primera za korišćenje kancelarija, na primer, definisali smo da je `hashCode` zavistan samo od jednog od polja, i samim tim kad smo pokrenuli program smo saznali tačno koliko ima različitih imena i koliko ima različitih brojeva. Isti pristup se može iskoristiti i u drugim situacijama, što nam može dati bolje ideje kako da postavimo različite koeficijente i na koja polja možda ima smisla staviti više "težine" u samom hešu.