Hash/hash.txt

   1 % Hash funkcije - pripremni materijal
   2 % SPA2, DMI-PMF-UNS, www.dmi.rs
   3 % 2015
   4
   5 Heš kod i jednakost u programskom jeziku Java
   6 =============================================
   7
   8 U programskom jeziku Java u svakoj klasi mogu (i često i trebaju) da
   9 postoje metodi
  10
  11     public int hashCode()
  12     public boolean equals(Object o)
  13
  14 Oni omogućavaju vrlo efikasne operacije nad velikim skupovima
  15 objekata, ali je bitno da uzajamno imaju konzistentno ponašanje.
  16
  17 Tačnije, ako su dva objekta jednaka u skladu sa `equals` tada im i heš
  18 vrednost koju vraća `hashCode` mora biti ista. Obrnutno ne mora da važi,
  19 odnosno može postojati neograničeni broj različitih objekata koji
  20 imaju isti heš kod. Isto tako ako dva objekta imaju različih heš, tada
  21 oni ne bi smeli biti jednaki kad se pita `equals`. No i ovde ne važi
  22 obrnuto, odnosno ako su dva objekta različiti, heš kod im ne mora biti
  23 različit.
  24
  25 Zbog ovih podrazumevanih odnosa je jako bitno da se ova dva metoda
  26 pišu zajedno, odnosno da se ne menja samo jedan bez promena u drugom.
  27
  28 U opštem slučaju ako se ovo ponašanje ne promeni reimplementacijom
  29 ovih metoda, objekti u Javi će za ova dva metoda da vraćaju vrednosti
  30 koje se odnose na sam pokazivač u memoriji. Odnosno dva objekta su
  31 isti samo ako se bukvalno isti objekat u memoriji, bez obzira na to da
  32 li imaju isti sadržaj. Isto tako će sam heš kod biti generisan od
  33 vrednosti samog pokazivača, a ne od sadržaja objekta. Jako često ovo
  34 nije poželjno ponašanje, te se zbog toga moraju pisati svoji metodi.
  35
  36 Heš kod je uvek poželjno pisati tako da se dobija što više različitih
  37 vrednosti za različite instance objekata. U idealnom slučaju bi se za
  38 svaki različit objekat dobijao različit heš kod, međutim to u praksi
  39 često nije moguće.
  40
  41 Klasa `String` ima redefinisana oba ova metoda. Heš kod koji se dobija
  42 za ovu klasu je veoma kvalitetan i uglavnom se vredi osloniti na njega
  43 za polja ovog tipa.
  44
  45
  46 Ocene kvaliteta funkcije
  47 ========================
  48
  49 Kvalitetna heš funkcija ravnomerno raspoređuje elemente po celoj tabeli,
  50 odnosno dobijamo podskupove sličnih veličina.
  51
  52 Za poređenje kvaliteta heš funkcija se mogu koristi različite mere. Prva je
  53 procentualna popunjenost tabele -- odnosno procenat podskupova (listi)
  54 u kojima postoji bar po jedan element.
  55
  56 Nešto komplikovanija mera je $\chi^2$ \emph{(hi-kvadrat)} test.
  57 \begin{equation}
  58   \chi ^2 = \sum_{i=1}^{n} \frac{(K_i - E)^2}{E}
  59 \end{equation}
  60
  61 gde je $K_i$ - broj elemenata u podskupu $i$, a $E$ - očekivan broj
  62 elemenata u podskupu, odnosno idealna vrednost koja je jednaka
  63 količniku ukupnog broja elemenata i broja skupova.
  64
  65 Iako deluje relativno komplikovano, ovo nam zapravo daje dobru ocenu
  66 koliko su (ne)ravnomerno raspoređeni elementi.  U idealno slučaju bi
  67 sve $K_i$ vrednosti bile jednake sa $E$ i imali bi da je vrednost
  68 testa nula. U opštem slučaju se naravno javljaju odstupanja od
  69 proseka, a pošto kvadriramo udaljenosti, $\chi^2$ brzo raste ukoliko
  70 ima većih anomalija.
  71
  72 Pri pisanju heš funkcije treba ciljati na što veću procentualnu
  73 popunjenost tabele, idealno je to 100\% za veću količinu podataka.
  74
  75 Sa druge strane, $\chi^2$ test predstavlja ravnomernost duzina listi,
  76 te bi trebao ostajati relativno konzistentan. Kod dobrih heš funkcija
  77 koje ravnomerno rasporedjuju elemente ovaj test često daje niže
  78 vrednosti tek za veći broj ubačenih elemenata, pošto tek onda dolaze
  79 do izražaja statističko ravnomerno raspoređivanje.
  80
  81 Dobre vrednosti za ovaj test za heš funkciju zavise od podataka sa
  82 kojima se radi, ali u opštem slučaju treba ciljati da budu niže od
  83 broja podskupova.
  84
  85
  86 Primeri
  87 =======
  88
  89 U sledećim primerima će se razmatrati različiti tipovi podataka i kako
  90 se oni efikasno mogu skladištiti u heš tabelama. Uglavnom će se
  91 razmatrati ideje heš tabele koja ima tačno određen broj podskupova i
  92 pratiti njihovu pokrivenosti i hi kvadrat meru. Tipično će se
  93 razmatrati razlitiče veličine ovih tabela, na primer 101, 503 i 997
  94 radi bolje ilustracije uticaja veličine na lošije heš funkcije.
  95
  96
  97 Korišćenje kancelarija
  98 ----------------------
  99
 100 Treba da čuvamo podatke o korišćenju kancelarija u toku jednog dana i
 101 da omogućimo što bržu proveru da li je neka konkretna osoba koristila
 102 neku konkretnu kancelariju. Podaci vezuju prezimena za identifikacione
 103 brojeve soba.  Naravno moguće je da više ljudi koristilo istu
 104 kancelariju, a moguće je i da je neko više puta koristio istu -- ovo
 105 će se u tabeli skladištiti samo jedan put, pošto nas samo zanima ko je
 106 bio unutra, a ne koliko puta.
 107
 108 Uzmimo sledeću definiciju klase
 109
 110 ```Java
 111     class Kancelarija {
 112        private int broj;
 113        private String prezime;
 114        ....
 115     }
 116 ```
 117
 118 U datim fajlovima nema više od~100 prostorija, a i postoji samo
 119 oko~60 različitih prezimena (tj zaposlenih).
 120
 121 Broj sobe tipa `int` i deluje kao "očigledan" kandidat za heš kod.
 122 Validno bi bilo da se ova informacija vraća kao heš kod:
 123
 124 ```Java
 125     public int hashCode() {
 126         return broj;
 127     }
 128 ```
 129
 130 Pogledajmo primere učitavanja većeg broja podataka u heš tabele sa
 131 različitim brojem podskupova, ako imamo tako definisanu heš funkciju:
 132
 133 Elements    : 4885
 134 Percent full:  99.01
 135 Chi square  :  67.3081
 136 'Columns'   : 101
 137
 138 Elements    : 4885
 139 Percent full:  19.88
 140 Chi square  : 19778.4749
 141 'Columns'   : 503
 142
 143 Elements    : 4885
 144 Percent full:  10.03
 145 Chi square  : 44000.6551
 146 'Columns'   : 997
 147
 148 Budući da ima samo 100 soba, primećujemo da vrednosti nisu
 149 zadovoljavajuće čim imamo veće tabele, odnosno imamo manje od 20\% pokrivenosti
 150 tabele sa 503 mesta i oko 10\% za 997 mesta.
 151
 152 Slično važi i za prezimena, budući da ih ima samo šestdesetak, bez
 153 obzira na koliko je dobar heš kod u klasi `String`, možemo imati samo
 154 šestdesetak različitih rezultata, odnosno dobijamo još gore rezultate,
 155 čak i za relativno malu tabelu sa 101 podskupom.
 156
 157 ```Java
 158     public int hashCode() {
 159         return prezime.hashCode();
 160     }
 161 ```
 162
 163
 164 Elements    : 4885
 165 Percent full:  49.50
 166 Chi square  : 6320.7484
 167 'Columns'   : 101
 168
 169 Elements    : 4885
 170 Percent full:  11.53
 171 Chi square  : 39251.8342
 172 'Columns'   : 503
 173
 174 Elements    : 4885
 175 Percent full:   5.72
 176 Chi square  : 85190.9396
 177 'Columns'   : 997
 178
 179 Očigledno je potrebno kombinovati ove dve vrednosti. Možemo ih
 180 jednostavno samo sabrati:
 181
 182 ```Java
 183         public int hashCode() {
 184                 return prezime.hashCode() + broj;
 185         }
 186 ```
 187
 188 Dobijamo dosta bolje rezultate u testovima:
 189
 190 Elements    : 4885
 191 Percent full: 100.00
 192 Chi square  :  20.7468
 193 'Columns'   : 101
 194
 195 Elements    : 4885
 196 Percent full: 100.00
 197 Chi square  : 720.2837
 198 'Columns'   : 503
 199
 200 Elements    : 4885
 201 Percent full:  99.00
 202 Chi square  : 1341.3007
 203 'Columns'   : 997
 204
 205 Množenje će tipično dati bolje vrednosti nego sabiranje kad imamo
 206 vrednosti koje su jako blizu jedne drugima (što brojevi kancelarija
 207 koji idu zaredom jesu), pošto pomaže u "raspipanju" vrednosti na većem
 208 opsegu.
 209
 210 Na primer
 211
 212 ```Java
 213         public int hashCode() {
 214                 return prezime.hashCode() * broj;
 215         }
 216 ```
 217
 218 Elements    : 4885
 219 Percent full: 100.00
 220 Chi square  :  78.8864
 221 'Columns'   : 101
 222
 223 Elements    : 4885
 224 Percent full: 100.00
 225 Chi square  : 483.8686
 226 'Columns'   : 503
 227
 228 Elements    : 4885
 229 Percent full:  99.10
 230 Chi square  : 951.0727
 231 'Columns'   : 997
 232
 233 Iz rezultata se vidi da se konzistentno dobijaju dobre vrednosti sa
 234 ovakvom heš funkcijom. Naročito je bitno što nam vrednost hi kvadrat
 235 testa govori da imamo odstupanje u veličinama podskupova u proseku
 236 manje od jedan.
 237
 238 Istovremeno je bitno da se i `equals` definiše da koristi ista polja.
 239 Metod zahteva da parametar bude tipa `Object`, pa uvek moramo da krenemo
 240 od toga. Najjednostavnija varijanta zahteva da proverimo da li je
 241 prosledjeno nešto što je iste klase kao i naš objekat, pa tek
 242 onda možemo da menjamo tip i da poredimo polja.
 243
 244 ```Java
 245         public boolean equals(Object o) {
 246                 // proveravamo da li je objekat sa
 247                 // kojim se poredimo Kancelarija
 248                 if (o instanceof Kancelarija) {
 249                         // pretvaramo objekat u kancelariju
 250                         Kancelarija k2 = (Kancelarija) o;
 251                         // poredimo polja
 252                         if (prezime.equals(k2.prezime) && broj == k2.broj) {
 253                                 return true;
 254                         }
 255                 }
 256                 return false;
 257         }
 258 ```
 259
 260 Međutim potpuna verzija `equals` metoda treba da proveri da li je u
 261 pitanju baš ista klasa kao naša (moguće da je neki naslednik koji
 262 tehnički ne mora biti isti), te da tu uzme u obzir i da je moguće da
 263 nam je prosleđen `null` što nikako ne može biti isto kao i naš
 264 objekat. Dalje se može ubrzati postupak proverom da li su u pitanju
 265 pokazivači na isto mesto pošto nema potrebe za proverama onda.
 266
 267 Potpuna verzija bi izgledala ovako:
 268
 269 ```Java
 270         public boolean equals(Object o) {
 271                 // Objekat je identican
 272                 if (this == o) {
 273                         return true;
 274                 }
 275                 // Null je uvek razlicit
 276                 if (o == null) {
 277                         return false;
 278                 }
 279                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 280                 if (getClass() != o.getClass()) {
 281                         return false;
 282                 }
 283
 284                 // pretvaramo objekat u kancelariju
 285                 Kancelarija k2 = (Kancelarija) o;
 286                 // poredimo polja
 287                 if (prezime.equals(k2.prezime) && broj == k2.broj) {
 288                         return true;
 289                 }
 290
 291                 return false;
 292         }
 293 ```
 294
 295 Razmotrimo sledeću modifikaciju klase: recimo da se i dalje želi samo
 296 pratiti u tabeli ko je bio u kojoj kancelariji, ali da su negde već
 297 definisani objekti u kojima se skladišti i vreme poslednjeg
 298 pristupanja, ili recimo neki dodatni opis zašto je neko bio u
 299 kancelariji.
 300
 301 ```Java
 302     class KancelarijaVreme {
 303        private int broj;
 304        private String prezime;
 305
 306        private int pristupDan, pristupSat;
 307
 308        private String komentar;
 309     }
 310 ```
 311
 312 Budući da za naše potrebe nije bitno kad je pristupano niti zbog čega,
 313 i dalje bi trebali da koristimo iste kodove za `equals` i za
 314 `hashCode` pošto nam je dosta da ubacimo samo jedan objekat za svako
 315 pojedinačno korišćenje. Negde druge se naravno oni mogu koristiti za
 316 detaljije zapise, ali nas to trenutno ne interesuje.
 317
 318
 319 Gadjanje mete
 320 -------------
 321
 322 Potrebno je da čuvamo podatke o rezultatima gadjanja mete. U nizu se
 323 nalazi do 20 brojeva izmedju i uključujući 0 i 10.
 324
 325 Recimo da je klasa definisana na sledeći način:
 326
 327 ```Java
 328 public class Gadjanje {
 329         private int[] rezultati;
 330         private static int MAX_DUZ = 20;
 331         ...
 332 }
 333 ```
 334
 335 Pošto je moguće (i vrlo verovatno zapravo) da neko nije gađao svih 20
 336 puta, u podacima će biti nizovi različitih dužina.  U skladu sa tim je
 337 i format za unos takav da je prvi broj u redu zapravo broj gađanja,
 338 koji određuje veličinu niza.
 339
 340 Funkcija jednakosti bi izgledala ovako:
 341
 342 ```Java
 343         public boolean equals(Object o) {
 344                 // Objekat je identican
 345                 if (this == o) {
 346                         return true;
 347                 }
 348                 // Null je uvek razlicit
 349                 if (o == null) {
 350                         return false;
 351                 }
 352                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 353                 if (getClass() != o.getClass()) {
 354                         return false;
 355                 }
 356
 357                 Gadjanje o2 = (Gadjanje) o;
 358                 if (o2.rezultati.length == rezultati.length) {
 359                         for (int i = 0; i < rezultati.length; i++) {
 360                                 if (o2.rezultati[i] != rezultati[i])
 361                                         return false;
 362                         }
 363                         return true;
 364                 }
 365                 return false;
 366         }
 367 ```
 368
 369 "Očigledno" rešenje je samo sabrati sve ove vrednosti i vratiti broj.
 370 Međutim ovakvo rešenje daje maksimalno 200 različitih vrednosti i dosta
 371 loše vrednosti u tabeli:
 372
 373 Elements    : 9049
 374 Percent full: 100.00
 375 Chi square  : 314.5114
 376 'Columns'   : 101
 377
 378 Elements    : 9049
 379 Percent full:  27.63
 380 Chi square  : 34841.7383
 381 'Columns'   : 503
 382
 383 Elements    : 9049
 384 Percent full:  13.94
 385 Chi square  : 77947.1553
 386 'Columns'   : 997
 387
 388 U ovakvoj strukturi, pozicija u nizu bi trebalo da bude značajna za
 389 krajnje heš vrednosti. Da bi se to postiglo jedan pristup je množenje
 390 brojeva sa svojim pozicijama ili različitim (prostim) brojevima.
 391
 392 Za ovaj primer u kome je dužina niza raznolika i ima više "početnih"
 393 elemenata je dodatno pogodno da se težine primenjuju unazad, pa recimo
 394 možemo uvesti da prvi element ima težinu 21, a poslednji u nizu od 20
 395 elemenata težinu 2. Dodatno to možemo unaprediti množenjem prostim
 396 brojem pri svakom sabiranju, tako da se ta množenja akumuliraju na
 397 prvim elementima.
 398
 399 ```Java
 400         public int hashCode() {
 401                 int rez = 0;
 402                 for (int i = 0;i < rezultati.length; i++) {
 403                         rez = (rez + rezultati[i] * (MAX_DUZ+1-i)) * 7;
 404                 }
 405                 return rez;
 406         }
 407 ```
 408
 409 Elements    : 9084
 410 Percent full: 100.00
 411 Chi square  : 101.7743
 412 'Columns'   : 101
 413
 414 Elements    : 9084
 415 Percent full: 100.00
 416 Chi square  : 415.1915
 417 'Columns'   : 503
 418
 419 Elements    : 9084
 420 Percent full: 100.00
 421 Chi square  : 981.2660
 422 'Columns'   : 997
 423
 424
 425 Tabla za igru XO
 426 ----------------
 427
 428 Zadatak nam je da efikasno čuvamo podatke o pozicijama u igri XO,
 429 odnosno matrice 3x3, u kojima su vrednosti -1 za "X", 0 za prazno
 430 polje i 1 za "O".
 431
 432 Npr:
 433 ```
 434  1 0 -1  O _ X
 435  1 1 -1  O O X
 436 -1 0  1  X _ O
 437 ```
 438 predstavlja poziciju u kojoj je ``O'' pobedio/la.
 439
 440 Polja klase bi se mogla definisati na sledeći način:
 441
 442 ```Java
 443 public class XO  {
 444         public static final int DIM = 3;
 445         private int[][] tabla = new int[DIM][DIM];
 446 ....
 447 }
 448 ```
 449
 450 Poredjenje ovakvih objekata bi naravno trebalo da pojedinačno ispituje
 451 elemente matrice, na primer:
 452
 453 ```Java
 454         public boolean equals(Object o) {
 455                 // Objekat je identican
 456                 if (this == o) {
 457                         return true;
 458                 }
 459                 // Null je uvek razlicit
 460                 if (o == null) {
 461                         return false;
 462                 }
 463                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 464                 if (getClass() != o.getClass()) {
 465                         return false;
 466                 }
 467                 XO o2 = (XO) o;
 468                 for (int i = 0; i < DIM; i++) {
 469                         for (int j = 0; j < DIM; j++) {
 470                                 if (o2.tabla[i][j] != tabla[i][j]) {
 471                                         return false;
 472                                 }
 473                         }
 474                 }
 475                 return true;
 476         }
 477 ```
 478
 479 Za ovaj primer vredi prvo razmotriti da neke relativno očigledne
 480 tehnike nisu efikasne: sumiranje ovakve matrice daje vrednosti do plus
 481 ili minus 9, odnosno ima samo 19 različitih vrednosti, što bi
 482 predstavljalo jako lošu pokrivenost tabele.  Dodatno, vrlo često će
 483 rezultat biti 0 i uopšteno će biti više tablica koje su bliže
 484 "sredini" rezultatom, što opet dovodi do loše ravnomernosti
 485 raspoređivanja elemenata.
 486
 487 Dakle ovako definisan metod za heš će davati dosta loše rezultate:
 488
 489 ```Java
 490         public int hashCode() {
 491                 int rez = 0;
 492                 for (int i = 0; i < DIM; i++) {
 493                         for (int j = 0; j < DIM; j++) {
 494                                 rez += tabla[i][j];
 495                         }
 496                 }
 497                 return rez;
 498         }
 499 ```
 500
 501 Elements    : 4424
 502 Percent full:   9.90
 503 Chi square  : 87664.1198
 504 'Columns'   : 101
 505
 506 Elements    : 4424
 507 Percent full:   1.99
 508 Chi square  : 454193.0719
 509 'Columns'   : 503
 510
 511 Elements    : 4424
 512 Percent full:   1.00
 513 Chi square  : 904604.2717
 514 'Columns'   : 997
 515
 516 Efikasnost se u ovakvoj strukturi dobija davanjem "težine"
 517 elementima. Odnosno ne treba gledati jednako ako je "1" u gornjem
 518 levom uglu i u sredini. Npr u jednostavnijim varijantama se može zbir
 519 iz svakog reda množiti različitim brojem. Još bolji rezultati se
 520 dobijaju uvodjenjem još detaljnijih "težina": pri sumiranju reda
 521 množiti različito, ili čak imati specijalne proste brojeve za svako
 522 polje ili uvoditi dodatne operacije.
 523
 524 Takodje treba uzeti u obzir i to da sabiranje pozitivnih i negativnih
 525 vrednosti može da dovede do "međusobnog poništavanja", te da nula
 526 vrednosti ne pomažu zbiru, naročito kad se uvedu težine koje se množe
 527 sa vrednostima polja. Jedan način da se ovo uradi u konkretnom slučaju
 528 je da se pri računanju heša vrednosti u matrici sabiraju sa 2, pa time
 529 imamo 1,2,3 umesto -1,0,1, što dovodi do veće različitosti.
 530
 531 Kombinovanjem ovih ideja se mogu napraviti `hashCode` metodi koji će
 532 rezultovati sa hi kvadrat vrednostima manjim od broja podskupova
 533 ("kolona"), što se ostavlja za samostalnu vežbu.
 534