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
 287                 // Prvo proveravamo broj
 288                 if (broj != other.broj) {
 289                     return false;
 290                 }
 291
 292                 // A potom prezime
 293                 if (!Objects.equals(prezime, other.prezime)) {
 294                     return false;
 295                 }
 296
 297                 // Proverili smo polja i sva su jednaka
 298                 return true;
 299         }
 300 ```
 301
 302 Razmotrimo sledeću modifikaciju klase: recimo da se i dalje želi samo
 303 pratiti u tabeli ko je bio u kojoj kancelariji, ali da su negde već
 304 definisani objekti u kojima se skladišti i vreme poslednjeg
 305 pristupanja, ili recimo neki dodatni opis zašto je neko bio u
 306 kancelariji.
 307
 308 ```Java
 309     class KancelarijaVreme {
 310        private int broj;
 311        private String prezime;
 312
 313        private int pristupDan, pristupSat;
 314
 315        private String komentar;
 316     }
 317 ```
 318
 319 Budući da za naše potrebe nije bitno kad je pristupano niti zbog čega,
 320 i dalje bi trebali da koristimo iste kodove za `equals` i za
 321 `hashCode` pošto nam je dosta da ubacimo samo jedan objekat za svako
 322 pojedinačno korišćenje. Negde druge se naravno oni mogu koristiti za
 323 detaljije zapise, ali nas to trenutno ne interesuje.
 324
 325
 326 Gadjanje mete
 327 -------------
 328
 329 Potrebno je da čuvamo podatke o rezultatima gadjanja mete. U nizu se
 330 nalazi do 20 brojeva izmedju i uključujući 0 i 10.
 331
 332 Recimo da je klasa definisana na sledeći način:
 333
 334 ```Java
 335 public class Gadjanje {
 336         private int[] rezultati;
 337         private static int MAX_DUZ = 20;
 338         ...
 339 }
 340 ```
 341
 342 Pošto je moguće (i vrlo verovatno zapravo) da neko nije gađao svih 20
 343 puta, u podacima će biti nizovi različitih dužina.  U skladu sa tim je
 344 i format za unos takav da je prvi broj u redu zapravo broj gađanja,
 345 koji određuje veličinu niza.
 346
 347 Funkcija jednakosti bi izgledala ovako:
 348
 349 ```Java
 350         public boolean equals(Object o) {
 351                 // Objekat je identican
 352                 if (this == o) {
 353                         return true;
 354                 }
 355                 // Null je uvek razlicit
 356                 if (o == null) {
 357                         return false;
 358                 }
 359                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 360                 if (getClass() != o.getClass()) {
 361                         return false;
 362                 }
 363
 364                 Gadjanje o2 = (Gadjanje) o;
 365                 if (o2.rezultati.length == rezultati.length) {
 366                         for (int i = 0; i < rezultati.length; i++) {
 367                                 if (o2.rezultati[i] != rezultati[i])
 368                                         return false;
 369                         }
 370                         return true;
 371                 }
 372                 return false;
 373         }
 374 ```
 375
 376 "Očigledno" rešenje je samo sabrati sve ove vrednosti i vratiti broj.
 377 Međutim ovakvo rešenje daje maksimalno 200 različitih vrednosti i dosta
 378 loše vrednosti u tabeli:
 379
 380 Elements    : 9049
 381 Percent full: 100.00
 382 Chi square  : 314.5114
 383 'Columns'   : 101
 384
 385 Elements    : 9049
 386 Percent full:  27.63
 387 Chi square  : 34841.7383
 388 'Columns'   : 503
 389
 390 Elements    : 9049
 391 Percent full:  13.94
 392 Chi square  : 77947.1553
 393 'Columns'   : 997
 394
 395 U ovakvoj strukturi, pozicija u nizu bi trebalo da bude značajna za
 396 krajnje heš vrednosti. Da bi se to postiglo jedan pristup je množenje
 397 brojeva sa svojim pozicijama ili različitim (prostim) brojevima.
 398
 399 Za ovaj primer u kome je dužina niza raznolika i ima više "početnih"
 400 elemenata je dodatno pogodno da se težine primenjuju unazad, pa recimo
 401 možemo uvesti da prvi element ima težinu 21, a poslednji u nizu od 20
 402 elemenata težinu 2. Dodatno to možemo unaprediti množenjem prostim
 403 brojem pri svakom sabiranju, tako da se ta množenja akumuliraju na
 404 prvim elementima.
 405
 406 ```Java
 407         public int hashCode() {
 408                 int rez = 0;
 409                 for (int i = 0;i < rezultati.length; i++) {
 410                         rez = (rez + rezultati[i] * (MAX_DUZ+1-i)) * 7;
 411                 }
 412                 return rez;
 413         }
 414 ```
 415
 416 Elements    : 9084
 417 Percent full: 100.00
 418 Chi square  : 101.7743
 419 'Columns'   : 101
 420
 421 Elements    : 9084
 422 Percent full: 100.00
 423 Chi square  : 415.1915
 424 'Columns'   : 503
 425
 426 Elements    : 9084
 427 Percent full: 100.00
 428 Chi square  : 981.2660
 429 'Columns'   : 997
 430
 431
 432 Tabla za igru XO
 433 ----------------
 434
 435 Zadatak nam je da efikasno čuvamo podatke o pozicijama u igri XO,
 436 odnosno matrice 3x3, u kojima su vrednosti -1 za "X", 0 za prazno
 437 polje i 1 za "O".
 438
 439 Npr:
 440 ```
 441  1 0 -1  O _ X
 442  1 1 -1  O O X
 443 -1 0  1  X _ O
 444 ```
 445 predstavlja poziciju u kojoj je ``O'' pobedio/la.
 446
 447 Polja klase bi se mogla definisati na sledeći način:
 448
 449 ```Java
 450 public class XO  {
 451         public static final int DIM = 3;
 452         private int[][] tabla = new int[DIM][DIM];
 453 ....
 454 }
 455 ```
 456
 457 Poredjenje ovakvih objekata bi naravno trebalo da pojedinačno ispituje
 458 elemente matrice, na primer:
 459
 460 ```Java
 461         public boolean equals(Object o) {
 462                 // Objekat je identican
 463                 if (this == o) {
 464                         return true;
 465                 }
 466                 // Null je uvek razlicit
 467                 if (o == null) {
 468                         return false;
 469                 }
 470                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 471                 if (getClass() != o.getClass()) {
 472                         return false;
 473                 }
 474                 XO o2 = (XO) o;
 475                 for (int i = 0; i < DIM; i++) {
 476                         for (int j = 0; j < DIM; j++) {
 477                                 if (o2.tabla[i][j] != tabla[i][j]) {
 478                                         return false;
 479                                 }
 480                         }
 481                 }
 482                 return true;
 483         }
 484 ```
 485
 486 Za ovaj primer vredi prvo razmotriti da neke relativno očigledne
 487 tehnike nisu efikasne: sumiranje ovakve matrice daje vrednosti do plus
 488 ili minus 9, odnosno ima samo 19 različitih vrednosti, što bi
 489 predstavljalo jako lošu pokrivenost tabele.  Dodatno, vrlo često će
 490 rezultat biti 0 i uopšteno će biti više tablica koje su bliže
 491 "sredini" rezultatom, što opet dovodi do loše ravnomernosti
 492 raspoređivanja elemenata.
 493
 494 Dakle ovako definisan metod za heš će davati dosta loše rezultate:
 495
 496 ```Java
 497         public int hashCode() {
 498                 int rez = 0;
 499                 for (int i = 0; i < DIM; i++) {
 500                         for (int j = 0; j < DIM; j++) {
 501                                 rez += tabla[i][j];
 502                         }
 503                 }
 504                 return rez;
 505         }
 506 ```
 507
 508 Elements    : 4424
 509 Percent full:   9.90
 510 Chi square  : 87664.1198
 511 'Columns'   : 101
 512
 513 Elements    : 4424
 514 Percent full:   1.99
 515 Chi square  : 454193.0719
 516 'Columns'   : 503
 517
 518 Elements    : 4424
 519 Percent full:   1.00
 520 Chi square  : 904604.2717
 521 'Columns'   : 997
 522
 523 Efikasnost se u ovakvoj strukturi dobija davanjem "težine"
 524 elementima. Odnosno ne treba gledati jednako ako je "1" u gornjem
 525 levom uglu i u sredini. Npr u jednostavnijim varijantama se može zbir
 526 iz svakog reda množiti različitim brojem. Još bolji rezultati se
 527 dobijaju uvodjenjem još detaljnijih "težina": pri sumiranju reda
 528 množiti različito, ili čak imati specijalne proste brojeve za svako
 529 polje ili uvoditi dodatne operacije.
 530
 531 Takodje treba uzeti u obzir i to da sabiranje pozitivnih i negativnih
 532 vrednosti može da dovede do "međusobnog poništavanja", te da nula
 533 vrednosti ne pomažu zbiru, naročito kad se uvedu težine koje se množe
 534 sa vrednostima polja. Jedan način da se ovo uradi u konkretnom slučaju
 535 je da se pri računanju heša vrednosti u matrici sabiraju sa 2, pa time
 536 imamo 1,2,3 umesto -1,0,1, što dovodi do veće različitosti.
 537
 538 Kombinovanjem ovih ideja se mogu napraviti `hashCode` metodi koji će
 539 rezultovati sa hi kvadrat vrednostima manjim od broja podskupova
 540 ("kolona"), što se ostavlja za samostalnu vežbu.
 541