Zašto pri pisanju equals metode mora pisati hashCode metodu?
„Erge, čitam knjigu „Effective Java“, u 11. pravilu piše da pri pisanju equals metode mora pisati hashCode metodu, zašto je to?“ Sanmej je otvoreno pitala.
„Sanmej, ovo je vrlo dobro pitanje, jer je to takođe tačka znanja koja se često ispituje na intervjuima. Danas ću ti objasniti.“ rekao sam.
Java je objektno-orijentisani programski jezik, sve klase podrazumevano nasleđuju od Object klase, a Object na kineskom znači „objekat“.
Object klasa ima dve metode:
public native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}1) hashCode metoda
Ovo je nativna metoda, koristi se za vraćanje heš vrednosti objekta (ceo broj). Za vreme izvršavanja Java programa, višestruko pozivanje ove metode na isti objekat mora vratiti istu heš vrednost.
2) equals metoda
Za bilo koja ne-null referenca x i y, equals metoda vraća true samo ako i samo ako x i y referišu na isti objekat.
„Erge, izgleda da nema nikakve veze između ove dve metode?“ Sanmej je sumnjičavo upitala.
„Samo iz ova dva objašnjenja, zaista je tako.“ objasnio sam, „ali u dokumentacije ove dve metode postoje još dve informacije.“
Prvo, ako dva objekta pozivaju equals metodu i rezultat je true, onda dva objekta pozivaju hashCode metodu i rezultat je nužno isti — iz dokumentacije hashCode metode.
Drugo, kad god se prepisuje equals metoda, hashCode metoda takođe treba prepisati, kako bi se održalo prethodno pravilo.
„Oh, ako tako kažeš, onda su dve metode zaista povezane, ali zašto je to?“ Sanmej je postavila konačno pitanje.
„Funkcija hashCode metode je dobijanje heš vrednosti, a funkcija te heš vrednosti je određivanje indeksne pozicije objekta u heš tabeli (pričeći o HashMap-u).“ rekao sam.
Tipičan predstavnik heš tabele je HashMap, ona čuva parove ključ-vrednost, može brzo dobiti odgovarajuću vrednost na osnovu ključa.
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}Ovo je HashMap get metoda, metoda za dobavljanje vrednosti na osnovu ključa. Ona će pozvati getNode metodu:
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
// proverava da li je HashMap table null i da li je dužina table veća od 0
if ((tab = table) != null && (n = tab.length) > 0 &&
// na osnovu heš vrednosti izračunava indeksnu poziciju u table i dobija prvi čvor
(first = tab[(n - 1) & hash]) != null) {
// proverava da li je heš vrednost prvog čvora jednaka datom hešu, ako jeste, proverava da li je ključ jednak
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// ako nije jednako, dobija sledeći čvor trenutnog čvora
if ((e = first.next) != null) {
// ako je trenutni čvor TreeNode tipa (crveno-crno stablo), poziva TreeNode getTreeNode metodu za pretragu
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
// ako nije čvor crveno-crnog stabla, prolazi kroz vezanu listu za pretragu
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// ako nije pronašao odgovarajući čvor, vraća null
return null;
}Uobičajeno (bez heš kolizije), first = tab[(n - 1) & hash] je vrednost koja odgovara ključu. Prema vremenskoj kompleksnosti, može se izraziti kao O(1).
Ako se desi heš kolizija, to jest u if ((e = first.next) != null) {} klauzuli, može se videti da ako čvor nije crveno-crno stablo, kroz do-while petlju se proverava da li je ključ jednak vraćajući odgovarajuću vrednost. Prema vremenskoj kompleksnosti, može se izraziti kao O(n).
HashMap rešava heš koliziju metom povlačenja lanca (chaining), to jest ako se desi heš kolizija, više vrednosti će biti stavljeno na isto mesto ključa, nakon više od 8 vrednosti menja se u crveno-crno stablo, kako bi se povećala efikasnost pretrage.
Očigledno, sa gledišta vremenske kompleksnosti O(n) je lošije od O(1), upravo to i je vrednost heš tabele.
„Šta su O(n) i O(1)?“ Sanmej je malo zbunjeno.
„Ovo je način prikaza vremenske kompleksnosti, kasnije ću ti Erge posebno objasniti. Jednostavno kažem šta n i 1 znače, očigledno, n i 1 predstavljaju broj izvršenja koda, ako je veličina podataka n, n znači da treba izvršiti n puta, 1 znači da treba izvršiti samo jednom.“ objasnio sam.
„Sanmej, razmisli, ako nema heš tabele, a treba ovakva struktura podataka, podaci u njoj ne smeju se ponavljati, šta raditi?“ sam pitao.
„Možda koristiti equals metodu za poređenje jedan po jedan?“ Sanmej je malo nesigurno.
„Ovaj način je naravno izvodljiv, kao u if ((e = first.next) != null) {} klauzuli, ali ako je količina podataka stvarno velika, performanse će biti vrlo loše, najbolje rešenje je ipak HashMap.“
HashMap je u suštini implementiran pomoću niza, kada želimo da dobavimo određenu vrednost iz HashMap-a, u suštini trebamo da dobavimo element na određenoj poziciji u nizu, a pozicija je određena ključem.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}Ovo je HashMap put metoda, stavlja par ključ-vrednost u niz. Ona će pozvati putVal metodu:
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
// proverava da li je HashMap table null i da li je dužina table veća od 0
if ((tab = table) != null && (n = tab.length) > 0 &&
// na osnovu heš vrednosti izračunava indeksnu poziciju u table i dobija prvi čvor
(first = tab[(n - 1) & hash]) != null) {
// proverava da li je heš vrednost prvog čvora jednaka datom hešu, ako jeste, proverava da li je ključ jednak
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// ako nije jednako, dobija sledeći čvor trenutnog čvora
if ((e = first.next) != null) {
// ako je trenutni čvor TreeNode tipa (crveno-crno stablo), poziva TreeNode getTreeNode metodu za pretragu
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
// ako nije čvor crveno-crnog stabla, prolazi kroz vezanu listu za pretragu
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// ako nije pronašao odgovarajući čvor, vraća null
return null;
}Uobičajeno, p = tab[i = (n - 1) & hash]) je vrednost koja odgovara ključu. A indeks niza (n - 1) & hash je upravo na osnovu hashCode metode izračunat.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}„Erge, izgleda da još uvek nisi rekao zašto pri pisanju equals metode treba pisati hashCode metodu?“ Sanmej nije mogla da odolí.
„Pogledaj sledeći kod.“ rekao sam.
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);
Student s2 = new Student(18, "Zhang San");
System.out.println(scores.get(s2));
}
}
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);
}
}Prepisali smo equals metodu Student klase, ako su godine dva studenta i ime isto, smatramo da je to isti student, mada je vrlo čudno, mi smo upravo ovako neobrezni.
U main metodi, 18-godišnji Zhang San je dobio 98 poena na ispitu, vrlo dobar rezultat, stavili smo Zhang San-a i njegove rezultate u HashMap, zatim smo spremni da izvučemo:
null„Erge, zašto je izlaz null, a ne očekivani 98?“ Sanmej se čudi.
„Razlog je što pri pisanju equals metode nismo prepisali hashCode metodu.“ odgovorio sam, „equals metoda iako smatra da je isto ime i godine isti student, ali su u suštini dva objekta, hashCode nije isti.“
„Kako prepisati hashCode metodu?“ Sanmej je pitala.
„Možeš direktno pozvati hash metodu Objects klase.“ odgovorio sam.
@Override
public int hashCode() {
return Objects.hash(age, name);
}hash metoda Objects klase može generisati novu heš vrednost za različit broj parametara, hash metoda poziva hashCode metodu Arrays klase, izvorni kod te metode je sledeći:
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;
}Prva iteracija:
result = 31*1 + Integer(18).hashCode();Druga iteracija:
result = (31*1 + Integer(18).hashCode()) * 31 + String("Zhang San").hashCode();Za objekte sa različitim imenima i godinama, nakon ovakvog izračunavanja heš vrednost je vrlo vrlo vrlo teško ponoviti; za objekte sa istim imenom i godinama, heš vrednost ostaje ista.
Ponovno izvrši main metodu, rezultat je sledeći:
98Budući da su u ovom trenutku heš vrednosti i s1 i s2 objekata 776408.
„Kad god se prepisuje equals metoda, hashCode metoda takođe treba prepisati, razlog je da bi se garantovalo: ako dva objekta pozivaju equals metodu i rezultat je true, onda dva objekta pozivaju hashCode metodu i rezultat je nužno isti.“ zaključio sam.
„OK, shvatio sam.“ Sanmej je srećno klimnula glavom, videlo se da je danas naučila dosta.