Preskoči na glavni sadržaj

Detaljna analiza hashCode metode u Javi

Chenmo Wang ErJava jezgroVažne Java tačke znanja1805 reči6 minuta

Danas ćemo govoriti o hashCode() metodi u Javi. Kao što je poznato, Java je objektno-orijentisani programski jezik, sve klase podrazumevano nasleđuju od Object klase, a Object na kineskom znači „objekat".

Object klasa sadrži hashCode() metodu:

public native int hashCode();

To znači da sve klase imaju hashCode() metodu, ta metoda vraća vrednost tipa int. Budući da je hashCode() metoda native metoda(metoda modifikovana sa native ključnom rečju, implementirana u C/C++ jeziku, poziva je Java), to znači da Object klasa nije dala konkretnu implementaciju.

Konkretnu implementaciju možete videti u jdk/src/hotspot/share/runtime/synchronizer.cpp (izvorni kod možete preuzeti sa GitHub repozitorijuma OpenJDK). Metoda get_next_hash() će odlučiti koju strategiju generisanja hash vrednosti koristiti na osnovu vrednosti hashCode.

Nakon Java 9, hashCode() metoda će biti modifikovana sa @HotSpotIntrinsicCandidate anotacijom, što pokazuje da u HotSpot virtuelnoj mašini ima efikasnu implementaciju zasnovanu na CPU instrukcijama.

Da li ste neko mislili na sledeće pitanje: Zašto Object klasa treba hashCode() metodu?

U Javi, glavna uloga hashCode() metode je da radi u kombinaciji sa hash tabelom.

Hash tabela (Hash Table), takođe poznata kao rasipajuća tabela, je struktura podataka koja se može direktno pristupiti kroz ključnu vrednost (key-value), njena najveća karakteristika je moći brzo ostvariti pretragu, umetanje i brisanje. Algoritam koji se koristi zove se hash, to je transformacija bilo kojeg dužeg ulaza u fiksne dužine izlaza, taj izlaz je hash vrednost. Kao MD5, SHA1 koriste hash algoritam.

Kao HashSet, Hashtable (napomena: malo t), HashMap u Javi su konkretne implementacije zasnovane na hash tabeli. HashMap je najtipičniji predstavnik, ne samo da ga često ispituju ispitaoci, već je i vrlo visoka frekvencija korišćenja u radu.

Razmisli, ako nema hash tabele, ali potreban je takva struktura podataka, podaci u njoj ne smeju se ponavljati, šta treba raditi?

Da li koristiti equals() metodu za upoređivanje jedan po jedan? Ovo rešenje je naravno moguće. Ali ako je količina podataka vrlo velika, upoređivanje jedan po jedan kroz equals() metodu će sigurno biti vrlo niskefikasno, najbolje rešenje je hash tabela.

Uzmimo HashMap za primer. Kada treba dodati objekat u njega, prvo pozovemo hashCode() metodu tog objekta, dobijemo odgovarajuću hash vrednost, zatim stavimo hash vrednost i objekat u HashMap. Kada treba dodati novi objekat:

  • Dobijamo hash vrednost objekta;
  • Upoređujemo sa prethodno postojećom hash vrednošću, ako nisu jednake, direktno smestimo;
  • Ako su jednake, pozovemo equals() metodu za upoređivanje između objekata, ako su jednake, ne smestamo;
  • Ako nisu jednake, znači da se dogodio hash konflikt, dodajemo lanac da smestimo novi objekat;
  • Ako je dužina lanca veća od 8, pretvaramo u crveno-crno stablo za obradu.

Samo kroz ovaj proces, frekvencija pozivanja equals() metode se drastično smanjuje. To znači, samo ako je hash algoritam dovoljno efikasan, smanji frekvenciju hash konflikta na minimum, efikasnost hash tabele će biti posebno visoka.

Pogledajmo hash algoritam HashMap:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Prvo poziva hashCode() metodu objekta, zatim vrši pomeranje u desno na tu vrednost, zatim vrši XOR operaciju.

Obično, String se koristi kao ključ HashMap za hash operaciju, stoga pogledajmo hashCode() metodu String:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Moguće je zamisliti, nakon ovog niza kompleksnih operacija, plus dizajn autora JDK-a, nivo majstora, verujem da je verovatnoća hash konflikta svedena na minimum (mi smo detaljno raspravljali u HashMap).

Naravno, sa teorijskog gledišta, za dva različita objekta, njihova vrednost izračunata kroz hashCode() metodu može biti ista. Stoga, ne može koristiti hashCode() metodu da se odredi da li su dva objekta jednaka, mora koristiti equals() metodu.

To znači:

  • Ako dva objekta pozivaju equals() metodu i rezultat je true, pozivaju hashCode() metodu i rezultat mora biti jednak;
  • Ako dva objekta pozivaju hashCode() metodu i rezultat nije jednak, pozivaju equals() metodu i rezultat mora biti false;

Obrnuto:

  • Ako dva objekta pozivaju equals() metodu i rezultat je false, pozivaju hashCode() metodu i rezultat ne mora biti različit;
  • Ako dva objekta pozivaju hashCode() metodu i rezultat je jednak, pozivaju equals() metodu i rezultat ne mora biti true;

Pogledaj sledeći kod.

public class Test {
    public static void main(String[] args) {
        Student s1 = new Student(18, "Zhang San");
        Map<Student, Integer> scores = new HashMap<>();
        scores.put(s1, 98);
        System.out.println(scores.get(new Student(18, "Zhang San")));
    }
 }
 class Student {
    private int age;
    private String name;

     public Student(int age, String name) {
         this.age = age;
         this.name = name;
     }

     @Override
     public boolean equals(Object o) {
         Student student = (Student) o;
         return age == student.age &&
                 Objects.equals(name, student.name);
     }
 }

Mi smo prepisali equals() metodu klase Student, ako je starost i ime dva studenta isti, smatramo da je isti student, iako je vrlo neverovatno, mi smo tako neodlučni.

U main() metodi, 18-godišnji Zhang San je dobio 98 poena na ispitu, vrlo dobar rezultat, stavili smo Zhang San i rezultat u HashMap, zatim spremni da ispišemo rezultat Zhang San:

null

Veoma nesrećno, rezultat je null, a ne očekivani 98. Zašto?

Razlog je u tome što pri prepisivanju equals() metode nismo prepisali hashCode() metodu. Podrazumevano, hashCode() metoda je native metoda, vraća adresu skladištenja objekta, očigledno su s1 iz put() i new Student(18, "Zhang San") iz get() dva različita objekta, njihove adrese skladištenja sigurno nisu iste.

get() metoda HashMap će pozvati hash(key.hashCode()) da izračuna hash vrednost objekta, iako se dve različite hashCode() vrednosti nakon izračuna hash() metode mogu dobiti isti rezultat, ali ta verovatnoća je vrlo mala, stoga dovodi do toga da scores.get(new Student(18, "Zhang San")) ne može dobiti očekivanu vrednost 18.

Kako rešiti ovaj problem? Vrlo jednostavno, prepisati hashCode() metodu.

 @Override
 public int hashCode() {
     return Objects.hash(age, name);
 }

Objects klasa metoda hash() može generisati novu hashCode() vrednost za različit broj parametara.

public static int hashCode(Object a[]) {
 if (a == null)
     return 0;

 int result = 1;

 for (Object element : a)
     result = 31 * result + (element == null ? 0 : element.hashCode());

 return result;
}

Kod deluje vrlo jednostavno, matematička formula se može sumirati kao sledi (n je dužina stringa).

Napomena: 31 je neparan prost broj, ni veliki ni mali, opšti prosti brojevi su veoma pogodni za hash računanje, parni brojevi su ekvivalentni pomeranju, lako se prelivaju, uzrokuju gubitak podataka.

To znači da će se u slučaju iste starosti i imena dobiti ista hash vrednost. scores.get(new Student(18, "Zhang San")) će vratiti očekivani rezultat 98.

U Bibliji „Java Programming Thinking“ postoji odlomak koji opisuje hashCode() metodu.

Najvažniji faktor pri dizajniranju hashCode() je: u bilo kom trenutku, poziv hashCode() istog objekta treba generisati istu vrednost. Ako se pri dodavanju objekta u HashMap metodom put() generiše jedna hashCode() vrednost, a pri uzimanju metodom get() generiše se druga hashCode() vrednost, onda se taj objekat ne može ponovo dobiti. Stoga, ako se vaša hashCode() metoda oslanja na lako promenljive podatke objekta, korisnici treba da budu oprezni, zato što se pri promeni ovih podataka hashCode() će generisati drugačiju hash vrednost, što je ekvivalentno generisanju drugog ključa.

To znači, ako pri prepisivanju hashCode() i equals() metoda određeno polje objekta lako se menja, najbolje je napustiti ta polja, kako bi se izbegle nepredviđene posledice.

Dobro. Sa ovim sadržajem kao osnovom, vratimo se da pogledamo C++ izvorni kod native metode hashCode().

static inline intptr_t get_next_hash(Thread* current, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // Ovaj oblik koristi globalni generator slučajnih brojeva Park-Miller.
    // Na MP sistemu, vršićemo mnogo učitavanja i pisanja globalnih promenljivih, stoga će ovaj mehanizam izazvati mnogo komunikacije konzistencije.
    value = os::random();
  } else if (hashCode == 1) {
    // Ova varijanta ima stabilnu (idempotentnu) karakteristiku između STW (Stop The World) operacija.
    // U nekim shemama 1-0 sinhronizacije ovo može biti korisno.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;           // Za testiranje osetljivosti
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    // Marsaglijeva shema xor-pomeranja, sa stanjem specifičnim za nit
    // Ovo je možda najbolja opšta implementacija -- možemo je u budućnosti postaviti za podrazumevanu.
    unsigned t = current->_hashStateX;
    t ^= (t << 11);
    current->_hashStateX = current->_hashStateY;
    current->_hashStateY = current->_hashStateZ;
    current->_hashStateZ = current->_hashStateW;
    unsigned v = current->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    current->_hashStateW = v;
    value = v;
  }

  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

Ako nemate osnovu C++, nemojte detaljno gledati svaku liniju koda, samo pogledajte površinu da biste razumeli metodu get_next_hash(). Promenljiva hashCode je globalni parametar pri pokretanju JVM-a, kroz nju može se promeniti strategija generisanja hash vrednosti.

  • hashCode==0, poziva operativni sistem OS metodu random() za vraćanje slučajnog broja.
  • hashCode == 1, u STW (stop-the-world) operacijama, ova strategija se obično koristi u šemama sinhronizacije. Koristi adresu objekta za računanje, koristi se retko ažurirani slučajni broj (GVars.stw_random) učestvuje u tome.
  • hashCode == 2, koristi povratnu vrednost 1, za određene situacije testiranja.
  • hashCode == 3, počinje od 0 za računanje hash vrednosti, nije bezbedno za niti, više niti može dobiti istu hash vrednost.
  • hashCode == 4, povezano je sa memorijom lokacijom kreiranog objekta, izlaz u originalnom obliku.
  • hashCode == 5, podrazumevana vrednost, podržava više niti, koristi Marsaglia xor-shift algoritam za generisanje pseudo-slučajnih brojeva. Takozvani xor-shift algoritam, jednostavno rečeno, izgleda kao registar pomeranja, svaki put se pomeraju biti čiji se generišu iz XOR nekoliko bitova registru. Takozvani pseudo-slučajni brojevi nisu potpuno slučajni, ali pravo slučajno generisanje je teško, stoga samo može proći određene statističke testove slučajnosti, može se koristiti kao pravo slučajno.

Ovaj jednostavan zaključak.

U Javi, hashCode() metoda je definisana u klasi java.lang.Object, ova klasa je nadklasa svih Java klasa. Stoga svaki Java objekat može pozvati hashCode() metodu. Glavna svrha hashCode() metode je podrška za hash tabele (kao java.util.HashMap), ove strukture podataka koriste hash algoritam da ostvare brze operacije pretrage, umetanja i brisanja.

Glavni cilj hashCode() metode je vratiti jedan ceo broj, ovaj ceo broj se zove hash kod, on predstavlja jednu vrstu približnog predstavljanja objekta u memoriji. Hash kod se koristi za mapiranje objekta na specifičnu lokaciju u hash tabeli. Dva jednaka objekta (prema equals() metodi treba da imaju isti hash kod. Međutim, dva objekta sa istim hash kodom ne moraju biti jednaka.

Kada kreirate prilagođenu klasu i prepisujete equals() metodu, obično treba i prepisati hashCode() metodu da bi osigurali da jednaki objekti imaju isti hash kod. To pomaže poboljšanju tačnosti hash tabele pri korišćenju objekata prilagođene klase kao ključeva.