Hash/OHashSet/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. Ovde treba obratiti
 156 pažnju i da je moguće da imamo `null` polje.
 157
 158 ```Java
 159     public int hashCode() {
 160         if (prezime != null) {
 161             return prezime.hashCode();
 162         } else {
 163             return 0;
 164         }
 165     }
 166 ```
 167
 168
 169 Elements    : 4885
 170 Percent full:  49.50
 171 Chi square  : 6320.7484
 172 'Columns'   : 101
 173
 174 Elements    : 4885
 175 Percent full:  11.53
 176 Chi square  : 39251.8342
 177 'Columns'   : 503
 178
 179 Elements    : 4885
 180 Percent full:   5.72
 181 Chi square  : 85190.9396
 182 'Columns'   : 997
 183
 184 Očigledno je potrebno kombinovati ove dve vrednosti. Možemo ih
 185 jednostavno samo sabrati:
 186
 187 ```Java
 188         public int hashCode() {
 189                 int rez = 0;
 190                 if (prezime != null) {
 191                         rez += prezime.hashCode();
 192                 }
 193                 rez += broj;
 194                 return rez;
 195         }
 196 ```
 197
 198 Dobijamo dosta bolje rezultate u testovima:
 199
 200 Elements    : 4885
 201 Percent full: 100.00
 202 Chi square  :  20.7468
 203 'Columns'   : 101
 204
 205 Elements    : 4885
 206 Percent full: 100.00
 207 Chi square  : 720.2837
 208 'Columns'   : 503
 209
 210 Elements    : 4885
 211 Percent full:  99.00
 212 Chi square  : 1341.3007
 213 'Columns'   : 997
 214
 215 Množenje će tipično dati bolje vrednosti nego sabiranje kad imamo
 216 vrednosti koje su jako blizu jedne drugima (što brojevi kancelarija
 217 koji idu zaredom jesu), pošto pomaže u "raspipanju" vrednosti na većem
 218 opsegu.
 219
 220 Na primer
 221
 222 ```Java
 223         public int hashCode() {
 224                 int rez = 1;
 225                 if (prezime != null) {
 226                         rez *= prezime.hashCode();
 227                 }
 228                 rez *= broj;
 229                 return rez;
 230         }
 231 ```
 232
 233 Elements    : 4885
 234 Percent full: 100.00
 235 Chi square  :  78.8864
 236 'Columns'   : 101
 237
 238 Elements    : 4885
 239 Percent full: 100.00
 240 Chi square  : 483.8686
 241 'Columns'   : 503
 242
 243 Elements    : 4885
 244 Percent full:  99.10
 245 Chi square  : 951.0727
 246 'Columns'   : 997
 247
 248 Iz rezultata se vidi da se konzistentno dobijaju dobre vrednosti sa
 249 ovakvom heš funkcijom. Naročito je bitno što nam vrednost hi kvadrat
 250 testa govori da imamo odstupanje u veličinama podskupova u proseku
 251 manje od jedan.
 252
 253 Istovremeno je bitno da se i `equals` definiše da koristi ista polja.
 254 Metod zahteva da parametar bude tipa `Object`, pa uvek moramo da krenemo
 255 od toga. Najjednostavnija varijanta zahteva da proverimo da li je
 256 prosledjeno nešto što je iste klase kao i naš objekat, pa tek
 257 onda možemo da menjamo tip i da poredimo polja.
 258
 259 ```Java
 260         public boolean equals(Object o) {
 261                 // proveravamo da li je objekat sa
 262                 // kojim se poredimo Kancelarija
 263                 if (o instanceof Kancelarija) {
 264                         // pretvaramo objekat u kancelariju
 265                         Kancelarija k2 = (Kancelarija) o;
 266                         // poredimo polja
 267                         if (prezime.equals(k2.prezime) && broj == k2.broj) {
 268                                 return true;
 269                         }
 270                 }
 271                 return false;
 272         }
 273 ```
 274
 275 Međutim potpuna verzija `equals` metoda treba da proveri da li je u
 276 pitanju baš ista klasa kao naša (moguće da je neki naslednik koji
 277 tehnički ne mora biti isti), te da tu uzme u obzir i da je moguće da
 278 nam je prosleđen `null` što nikako ne može biti isto kao i naš
 279 objekat. Dalje se može ubrzati postupak proverom da li su u pitanju
 280 pokazivači na isto mesto pošto nema potrebe za proverama onda.
 281
 282 Potpuna verzija bi izgledala ovako:
 283
 284 ```Java
 285         public boolean equals(Object o) {
 286                 // Objekat je identican
 287                 if (this == o) {
 288                         return true;
 289                 }
 290                 // Null je uvek razlicit
 291                 if (o == null) {
 292                         return false;
 293                 }
 294                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 295                 if (getClass() != o.getClass()) {
 296                         return false;
 297                 }
 298
 299                 // pretvaramo objekat u kancelariju
 300                 Kancelarija k2 = (Kancelarija) o;
 301
 302                 // Prvo proveravamo broj
 303                 if (broj != k2.broj) {
 304                     return false;
 305                 }
 306
 307                 // A potom prezime
 308                 if (!Objects.equals(prezime, k2.prezime)) {
 309                     return false;
 310                 }
 311
 312                 // Proverili smo polja i sva su jednaka
 313                 return true;
 314         }
 315 ```
 316
 317 Razmotrimo sledeću modifikaciju klase: recimo da se i dalje želi samo
 318 pratiti u tabeli ko je bio u kojoj kancelariji, ali da su negde već
 319 definisani objekti u kojima se skladišti i vreme poslednjeg
 320 pristupanja, ili recimo neki dodatni opis zašto je neko bio u
 321 kancelariji.
 322
 323 ```Java
 324     class KancelarijaVreme {
 325        private int broj;
 326        private String prezime;
 327
 328        private int pristupDan, pristupSat;
 329
 330        private String komentar;
 331     }
 332 ```
 333
 334 Budući da za naše potrebe nije bitno kad je pristupano niti zbog čega,
 335 i dalje bi trebali da koristimo iste kodove za `equals` i za
 336 `hashCode` pošto nam je dosta da ubacimo samo jedan objekat za svako
 337 pojedinačno korišćenje. Negde druge se naravno oni mogu koristiti za
 338 detaljije zapise, ali nas to trenutno ne interesuje.
 339
 340
 341 Gadjanje mete
 342 -------------
 343
 344 Potrebno je da čuvamo podatke o rezultatima gadjanja mete. U nizu se
 345 nalazi do 20 brojeva izmedju i uključujući 0 i 10.
 346
 347 Recimo da je klasa definisana na sledeći način:
 348
 349 ```Java
 350 public class Gadjanje {
 351         private int[] rezultati;
 352         private static int MAX_DUZ = 20;
 353         ...
 354 }
 355 ```
 356
 357 Pošto je moguće (i vrlo verovatno zapravo) da neko nije gađao svih 20
 358 puta, u podacima će biti nizovi različitih dužina.  U skladu sa tim je
 359 i format za unos takav da je prvi broj u redu zapravo broj gađanja,
 360 koji određuje veličinu niza.
 361
 362 Funkcija jednakosti bi izgledala ovako:
 363
 364 ```Java
 365         public boolean equals(Object o) {
 366                 // Objekat je identican
 367                 if (this == o) {
 368                         return true;
 369                 }
 370                 // Null je uvek razlicit
 371                 if (o == null) {
 372                         return false;
 373                 }
 374                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 375                 if (getClass() != o.getClass()) {
 376                         return false;
 377                 }
 378
 379                 Gadjanje o2 = (Gadjanje) o;
 380                 // proveravamo da li je polje null pre dalje provere
 381                 if (rezultati != null && o2.rezultati != null) {
 382                         if (o2.rezultati.length == rezultati.length) {
 383                                 for (int i = 0; i < rezultati.length; i++) {
 384                                         if (o2.rezultati[i] != rezultati[i]){
 385                                                 // cim je nesto razlicito nisu isti
 386                                                 return false;
 387                                         }
 388                                 }
 389                                 // ako se sve vrednosti slazu isti su
 390                                 return true;
 391                         }
 392                         return false;
 393                 } else {
 394                         // vracamo da li su oba null, tj da li su jednaki
 395                         return (rezultati == null && o2.rezultati == null);
 396                 }
 397         }
 398 ```
 399
 400 "Očigledno" rešenje je samo sabrati sve ove vrednosti i vratiti broj.
 401 Međutim ovakvo rešenje daje maksimalno 200 različitih vrednosti i dosta
 402 loše vrednosti u tabeli:
 403
 404 Elements    : 9049
 405 Percent full: 100.00
 406 Chi square  : 314.5114
 407 'Columns'   : 101
 408
 409 Elements    : 9049
 410 Percent full:  27.63
 411 Chi square  : 34841.7383
 412 'Columns'   : 503
 413
 414 Elements    : 9049
 415 Percent full:  13.94
 416 Chi square  : 77947.1553
 417 'Columns'   : 997
 418
 419 U ovakvoj strukturi, pozicija u nizu bi trebalo da bude značajna za
 420 krajnje heš vrednosti. Da bi se to postiglo jedan pristup je množenje
 421 brojeva sa svojim pozicijama ili različitim (prostim) brojevima.
 422
 423 Za ovaj primer u kome je dužina niza raznolika i ima više "početnih"
 424 elemenata je dodatno pogodno da se težine primenjuju unazad, pa recimo
 425 možemo uvesti da prvi element ima težinu 21, a poslednji u nizu od 20
 426 elemenata težinu 2. Dodatno to možemo unaprediti množenjem prostim
 427 brojem pri svakom sabiranju, tako da se ta množenja akumuliraju na
 428 prvim elementima.
 429
 430 ```Java
 431         public int hashCode() {
 432                 int rez = 0;
 433                 if (rezultati != null) {
 434                         for (int i = 0; i < rezultati.length; i++) {
 435                                 rez = (rez + rezultati[i] * (MAX_DUZ + 1 - i)) * 7;
 436                         }
 437                 }
 438                 return rez;
 439         }
 440 ```
 441
 442 Elements    : 9084
 443 Percent full: 100.00
 444 Chi square  : 101.7743
 445 'Columns'   : 101
 446
 447 Elements    : 9084
 448 Percent full: 100.00
 449 Chi square  : 415.1915
 450 'Columns'   : 503
 451
 452 Elements    : 9084
 453 Percent full: 100.00
 454 Chi square  : 981.2660
 455 'Columns'   : 997
 456
 457
 458 Tabla za igru XO
 459 ----------------
 460
 461 Zadatak nam je da efikasno čuvamo podatke o pozicijama u igri XO,
 462 odnosno matrice 3x3, u kojima su vrednosti -1 za "X", 0 za prazno
 463 polje i 1 za "O".
 464
 465 Npr:
 466 ```
 467  1 0 -1  O _ X
 468  1 1 -1  O O X
 469 -1 0  1  X _ O
 470 ```
 471 predstavlja poziciju u kojoj je ``O'' pobedio/la.
 472
 473 Polja klase bi se mogla definisati na sledeći način:
 474
 475 ```Java
 476 public class XO  {
 477         public static final int DIM = 3;
 478         private int[][] tabla = new int[DIM][DIM];
 479 ....
 480 }
 481 ```
 482
 483 Poredjenje ovakvih objekata bi naravno trebalo da pojedinačno ispituje
 484 elemente matrice, na primer:
 485
 486 ```Java
 487         public boolean equals(Object o) {
 488                 // Objekat je identican
 489                 if (this == o) {
 490                         return true;
 491                 }
 492                 // Null je uvek razlicit
 493                 if (o == null) {
 494                         return false;
 495                 }
 496                 // Ako su klase razlicite, objekti ne mogu bili jednaki
 497                 if (getClass() != o.getClass()) {
 498                         return false;
 499                 }
 500
 501                 // menjamo tip da mozemo da poredimo
 502                 XO o2 = (XO) o;
 503                 // posto je u ovoj klasi uvek inicijalizovano polje table
 504                 // i uvek je DIM x DIM ne moramo proveravati null
 505                 for (int i = 0; i < DIM; i++) {
 506                         for (int j = 0; j < DIM; j++) {
 507                                 if (o2.tabla[i][j] != tabla[i][j]) {
 508                                         return false;
 509                                 }
 510                         }
 511                 }
 512                 return true;
 513         }
 514 ```
 515
 516 Za ovaj primer vredi prvo razmotriti da neke relativno očigledne
 517 tehnike nisu efikasne: sumiranje ovakve matrice daje vrednosti do plus
 518 ili minus 9, odnosno ima samo 19 različitih vrednosti, što bi
 519 predstavljalo jako lošu pokrivenost tabele.  Dodatno, vrlo često će
 520 rezultat biti 0 i uopšteno će biti više tablica koje su bliže
 521 "sredini" rezultatom, što opet dovodi do loše ravnomernosti
 522 raspoređivanja elemenata.
 523
 524 Dakle ovako definisan metod za heš će davati dosta loše rezultate:
 525
 526 ```Java
 527         public int hashCode() {
 528                 int rez = 0;
 529                 for (int i = 0; i < DIM; i++) {
 530                         for (int j = 0; j < DIM; j++) {
 531                                 rez += tabla[i][j];
 532                         }
 533                 }
 534                 return rez;
 535         }
 536 ```
 537
 538 Elements    : 4424
 539 Percent full:   9.90
 540 Chi square  : 87664.1198
 541 'Columns'   : 101
 542
 543 Elements    : 4424
 544 Percent full:   1.99
 545 Chi square  : 454193.0719
 546 'Columns'   : 503
 547
 548 Elements    : 4424
 549 Percent full:   1.00
 550 Chi square  : 904604.2717
 551 'Columns'   : 997
 552
 553 Efikasnost se u ovakvoj strukturi dobija davanjem "težine"
 554 elementima. Odnosno ne treba gledati jednako ako je "1" u gornjem
 555 levom uglu i u sredini. Npr u jednostavnijim varijantama se može zbir
 556 iz svakog reda množiti različitim brojem. Još bolji rezultati se
 557 dobijaju uvodjenjem još detaljnijih "težina": pri sumiranju reda
 558 množiti različito, ili čak imati specijalne proste brojeve za svako
 559 polje ili uvoditi dodatne operacije.
 560
 561 Takodje treba uzeti u obzir i to da sabiranje pozitivnih i negativnih
 562 vrednosti može da dovede do "međusobnog poništavanja", te da nula
 563 vrednosti ne pomažu zbiru, naročito kad se uvedu težine koje se množe
 564 sa vrednostima polja. Jedan način da se ovo uradi u konkretnom slučaju
 565 je da se pri računanju heša vrednosti u matrici sabiraju sa 2, pa time
 566 imamo 1,2,3 umesto -1,0,1, što dovodi do veće različitosti.
 567
 568 Kombinovanjem ovih ideja se mogu napraviti `hashCode` metodi koji će
 569 rezultovati sa hi kvadrat vrednostima manjim od broja podskupova
 570 ("kolona"), što se ostavlja za samostalnu vežbu.
 571