Zasada haszowania
Przede wszystkim, zanim zdefiniujemy hashcode w Javie, musimy zrozumieć, czym jest haszowanie i do czego ono służy. Haszowanie to proces polegający na użyciu funkcji na pewnych danych w określonym celu. Funkcja haszująca to po prostu funkcja matematyczna. Nie martw się o to! „Matematyczny” nie zawsze oznacza „skomplikowany”. Tutaj znaczy to tylko tyle, że mamy pewne dane i pewną regułę, która odwzorowuje te dane na zestaw znaków (kod).
Na przykład może to być szyfr szesnastkowy. Jako wejście mamy pewne dane o dowolnym rozmiarze i stosujemy do nich funkcję haszującą. Jako wyjście otrzymujemy dane o stałym rozmiarze, powiedzmy 32 znaki. Zwykle tego rodzaju funkcja konwertuje duży fragment danych na niewielką wartość całkowitą. Wynik działania tej funkcji nazywany jest kodem haszującym (hashcode) Funkcje haszujące są szeroko stosowane w kryptografii, a także w niektórych innych dziedzinach.
Funkcje haszujące mogą być różne, ale wszystkie mają określone właściwości:
- Określony obiekt ma konkretny hashcode.
- Jeśli dwa obiekty są równe, ich hashcody są takie same. Odwrotna sytuacja nie jest prawdą.
- Jeśli dwa kody haszowania są różne, obiekty na pewno takie nie są.
- Różne obiekty mogą mieć ten sam kod haszowania. Jest to jednak zdarzenie bardzo mało prawdopodobne. W tym momencie mamy kolizję, tj. sytuację, w której możemy stracić dane.
„Właściwa” funkcja haszująca minimalizuje prawdopodobieństwo wystąpienia kolizji.
Hashcode w Javie
W Javie funkcja haszująca jest zwykle połączona z metodą
hashCode(). Dokładnie rzecz biorąc, wynikiem zastosowania funkcji haszującej do Object jest hashcode. Każdy obiekt w Javie ma swój kod haszujący. Ogólnie mówąc, hashcode to liczba obliczona przez metodę
hashCode() klasy
Object
Zazwyczaj programiści nadpisują tę metodę dla swoich obiektów, jak również powiązaną z
hashCode() metodę
equals() dla bardziej efektywnego przetwarzania określonych danych.
Metoda
hashCode() zwraca wartość int (4 bajty), która jest liczbową reprezentacją obiektu. Ten hashcode jest używany na przykład przez kolekcje do bardziej efektywnego przechowywania danych i szybszego dostępu do nich.
Domyślnie funkcja
hashCode() dla obiektu zwraca numer komórki pamięci, w której obiekt jest przechowywany. Dlatego jeśli w kodzie aplikacji nie zostaną wprowadzone żadne zmiany, to funkcja powinna zwrócić tę samą wartość. Jeśli kod nieznacznie się zmieni, zmianie ulegnie również wartość hashcode.
Do czego służy hashcode w Javie? Przede wszystkim hashcode Java pomaga programom działać szybciej. Na przykład, jeśli porównujemy dwa obiekty
o1
i
o2
jakiegoś typu, to operacja
o1.equals(o2)
zajmuje około 20 razy więcej czasu niż
o1.hashCode() == o2.hashCode()
.
Java equals()
W klasie nadrzędnej
Object
, oprócz metody
hashCode() znajduje się również
equals(), funkcja, która służy do sprawdzania równości dwóch obiektów. Domyślna implementacja tej funkcji po prostu sprawdza powiązania dwóch obiektów pod kątem ich równoważności.
equals() i
hashCode() mają swój kontrakt, więc przy nadpisywaniu jednego z nich, należy nadpisać również drugi, aby tego kontraktu nie zerwać.
Implementacja metody hashCode()
Przykład
Utwórzmy klasę
Character z jednym polem —
name. Następnie stwórzmy dwa obiekty klasy
Character,
character1, oraz
character2 i nadajmy im tę samą nazwę. Jeśli użyjemy domyślnych metod
hashCode() i
equals() klasy
Object, na pewno otrzymamy różne, nierówne obiekty. Tak właśnie działa hashcode w Javie. Będą one miały różne kody haszujące, ponieważ znajdują się w różnych komórkach pamięci i wynikiem operacji
equals() będzie false.
import java.util.Objects;
public class Character {
private String Name;
public Character(String name) {
Name = name;
}
public String getName() {
return Name;
}
public void setName(String name) {
Name = name;
}
public static void main(String[] args) {
Character character1 = new Character("Arnold");
System.out.println(character1.getName());
System.out.println(character1.hashCode());
Character character2 = new Character("Arnold");
System.out.println(character2.getName());
System.out.println(character2.hashCode());
System.out.println(character2.equals(character1));
}
}
Wynikiem działania programu jest:
Arnold
1595428806
Arnold
1072408673
false
Dwie 10-cyfrowe liczby w konsoli to kody haszujące. Co jeśli chcemy otrzymać równe obiekty, jeżeli mają one te same nazwy? Co powinniśmy zrobić?
Odpowiedź: powinniśmy nadpisać metody
hashCode() i
equals() klasy
Object dla naszej klasy
Character. Możemy to zrobić automatycznie w IDEA IDE, wystarczy nacisnąć na klawiaturze
alt + insert i wybrać
Generuj -> equals() i hashCode().
W przypadku naszego przykładu mamy kolejny kod:
import java.util.Objects;
public class Character {
private String Name;
public Character(String name) {
Name = name;
}
public String getName() {
return Name;
}
public void setName(String name) {
Name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Character)) return false;
Character character = (Character) o;
return getName() != null ? getName().equals(character.getName()) : character.getName() == null;
}
@Override
public int hashCode() {
return getName() != null ? getName().hashCode() : 0;
}
public static void main(String[] args) {
Character character1 = new Character("Arnold");
System.out.println(character1.getName());
System.out.println(character1.hashCode());
Character character2 = new Character("Arnold");
System.out.println(character2.getName());
System.out.println(character2.hashCode());
System.out.println(character2.equals(character1));
}
}
Wynik odpalenia tego kodu to:
Arnold
1969563338
Arnold
1969563338
true
Więc teraz program identyfikuje nasze obiekty jako równe i mają one te same kody haszujące.
Przykładowy hashcode w Javie:
Twoje własne funkcje hashCode() i equals()
Możesz także tworzyć własne realizacje
equals() i
hashCode(), lecz zachowaj ostrożność oraz pamiętaj, aby zminimalizować kolizje kodu haszującego. Oto przykład naszych własnych metod
hashCode() i
equals() w klasie
Student:
import java.util.Date;
public class Student {
String surname;
String name;
String secondName;
Long birthday; // Long instead of long is used by Gson/Jackson json parsers and various orm databases
public Student(String surname, String name, String secondName, Date birthday ){
this.surname = surname;
this.name = name;
this.secondName = secondName;
this.birthday = birthday == null ? 0 : birthday.getTime();
}
//Java hashcode example
@Override
public int hashCode(){
//TODO: check for nulls
//return surname.hashCode() ^ name.hashCode() ^ secondName.hashCode() ^ (birthday.hashCode());
return (surname + name + secondName + birthday).hashCode();
}
@Override
public boolean equals(Object other_) {
Student other = (Student)other_;
return (surname == null || surname.equals(other.surname) )
&& (name == null || name.equals(other.name))
&& (secondName == null || secondName.equals(other.secondName))
&& (birthday == null || birthday.equals(other.birthday));
}
}
A teraz dopiszmy klasę
Main, aby dodać informacje o ich zatrudnieniu.
import java.util.Date;
import java.util.HashMap;
import java.util.Hashtable;
public class Main {
static HashMap<Student, Integer> cache = new HashMap<Student, Integer>(); // <person, targetPriority>
public static void main(String[] args) {
Student sarah1 = new Student("Sarah","Connor", "Jane", null);
Student sarah2 = new Student("Sarah","Connor", "Jane", new Date(1970, 01-1, 01));
Student sarah3 = new Student("Sarah","Connor", "Jane", new Date(1959, 02-1, 28)); // date not exists
Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
Student johnny = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
System.out.println(john.hashCode());
System.out.println(johnny.hashCode());
System.out.println(sarah1.hashCode());
System.out.println();
cache.put(sarah1, 1);
cache.put(sarah2, 2);
cache.put(sarah3, 3);
System.out.println(new Date(sarah1.birthday));
System.out.println();
cache.put(john, 5);
System.out.println(cache.get(john));
System.out.println(cache.get(johnny));
cache.put(johnny, 7);
System.out.println(cache.get(john));
System.out.println(cache.get(johnny));
}
}
Do czego służy hashcode?
Przede wszystkim kody haszujące pomagają programom działać szybciej. Na przykład, jeśli porównujemy dwa obiekty
o1
i
o2
jakiegoś typu, to operacja
o1.equals(o2)
zajmuje około 20 razy więcej czasu niż o1.hashCode() == o2.hashCode(). W Javie zasada haszowania stoi za niektórymi popularnymi kolekcjami, takimi jak
HashMap,
HashSet i
HashTable.
Wniosek
Każdy obiekt Javy ma metody
hashCode() i
equals() odziedziczone z klasy
Object. Aby otzzymać sprawniej działający mechanizm do porównywania, lepiej jest nadpisać metody
hashcode() i
equals() dla klas w twoim własnym kodzie. Używanie kodów haszujących przyspiesza działanie programów.
GO TO FULL VERSION