gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/Hash/OHashSet/hash.txt b/Hash/OHashSet/hash.txt
--- /dev/null
+++ b/Hash/OHashSet/hash.txt
@@ -0,0 +1,571 @@
+% 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.
+