Zarówno HashSet jak i HashMap są oparte o hashCode. Polegają one na hashCode w celu uporządkowania danych w tak zwanych koszykach (buckets). Po czym wewnątrz każdego koszyka, używana jest metoda equals, aby znaleźć konkretny element (jeśli jest ich więcej niż jeden w koszyku). Z takiego stanu rzeczy wynika też kontrakt equals & hashCode.
Jak zostało to przedstawione na powyższym obrazku, dane są przetrzymywane w koszykach dla konkretnych wartości zwracanych przez metodę hashCode. Każdy koszyk może zawierać jedną lub więcej wartości. Każda z wartości w koszyku powinna być rozróżnialna – metoda equals nie powinna zwrócić wartości true porównując dowolne elementy koszyka.
Przykłady (w oparciu o HashMap)
Nieprzeciążone metody hashCode i equals
static class Key {
private final int key;
public Key(int key) {
this.key = key;
}
}
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key1 = new Key(1);
Key key2 = new Key(1);
map.put(key1, "original value");
map.put(key2, "overridden value");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}Po uruchomieniu metody main dostajemy:
original value
overridden valueJak widać na powyższym przykładzie nieprzeciążenie metody hashCode powoduje, że każdy element ląduje w innym koszyku – przez co jest różną wartością (nieprzeciążenie metody equals nie ma tutaj znaczenia, zobacz też Przeciążenie tylko metody equals).
Przeciążenie tylko metody hashCode
static class Key {
private final int key;
public Key(int key) {
this.key = key;
}
@Override
public int hashCode() {
return key;
}
}
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key1 = new Key(1);
Key key2 = new Key(1);
map.put(key1, "original value");
map.put(key2, "overridden value");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}Po uruchomieniu metody main dostajemy:
original value
overridden valueJak widać przeciążenie metody hashCode także nie rozwiązuje problemu. W tym momencie wszystkie elementy są już w jednym koszyku, lecz wciąż metoda equals nie zwraca wartości true (bo operuje na porównaniu referencji), dla teoretycznie tych samych kluczy (key1 oraz key2). Przez to wartości są traktowane jako różne.
Przeciążenie zarówno hashCode jak i equals
static class Key {
private final int key;
public Key(int key) {
this.key = key;
}
@Override
public int hashCode() {
return key;
}
@Override
public boolean equals(Object obj) {
return ((Key)obj).key == key;
}
}
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key1 = new Key(1);
Key key2 = new Key(1);
map.put(key1, "original value");
map.put(key2, "overridden value");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}Po uruchomieniu metody main dostajemy:
overridden value
overridden valueJak widać przeciążenie metody hashCode powoduje, że elementy lądują w tym samym koszyku. A dzięki metodzie equals porównanie (w ramach jednego koszyka) obiektów key1 oraz key2 zwraca wartość true. Dzięki temu element w mapie został poprawnie nadpisany.
Przeciążenie tylko metody equals
static class Key {
private final int key;
public Key(int key) {
this.key = key;
}
@Override
public boolean equals(Object obj) {
return ((Key)obj).key == key;
}
}
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key1 = new Key(1);
Key key2 = new Key(1);
map.put(key1, "original value");
map.put(key2, "overridden value");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}Po uruchomieniu metody main dostajemy:
original value
overridden valuePodobnie jak w pierwszym przykładzie, jeśli już na poziomie koszyka do którego trafia element (brak metody hashCode) nie ma spójności, to przeciążenie samej metody equals nic nie daje.
Przeciążenie metody equals gdy hashCode zwraca tą samą wartość
static class Key {
private final int key;
public Key(int key) {
this.key = key;
}
@Override
public int hashCode() {
return 1;
}
@Override
public boolean equals(Object obj) {
return ((Key)obj).key == key;
}
}
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key1 = new Key(1);
Key key2 = new Key(1);
map.put(key1, "original value");
map.put(key2, "overridden value");
System.out.println(map.get(key1));
System.out.println(map.get(key2));
}Po uruchomieniu metody main dostajemy:
overridden value
overridden valueJak widać nie jest konieczne to aby w sytuacji gdy metoda hashCode zwraca te same wartości dla danych obiektów, metoda equals robiła to samo (także zwracała te same wartości). Lecz taki zabieg jest raczej nie polecany z uwagi na wydajność.
Warto zajrzeć
1. Przykłady z wpisu – https://github.com/damianradowiecki/hashmapexamples (w formie testów)
2. Wydajność przy metodzie hashCode zwracającej cały czas tą samą wartość