Wydajne porównywanie obiektów przez wykorzystaniu funkcji hashCode

W tym artykule postaram się opisać ideę wykorzystania kontraktu metody Object.hashCode do przyśpieszenia porównywania obiektów. Stosując regułę transpozycji do kontraktu metody hashCode

A.equals(B) ⇒ A.hashCode() == B.hashCode()

otrzymujemy

A.hashCode() != B.hashCode() ⇒  !A.equals(B)

Dzięki temu przy założeniu poprawnego rozkładu funkcji haszującej możemy w większości przypadków sprowadzić porównywanie obiektów do porównywania dwóch liczb całkowitych.

boolean equals(Object o) {
   if(o == null) return false
   if(this == o) return true
   if(getClass() != o.getClass()) return false;
   if(hashCode() != o.hashCode()) return false;
   // funkcje hashujące się zgadzają. Porównujemy obiekty
}

Oczywiście, wyliczenie wartości funkcji haszującej jest często bardziej kosztowne od porównania obiektów. Problem ten można łatwo rozwiązać przy założeniu, że obiekty które porównujemy są niezmienne (immutable). W takiej sytuacji możemy wyliczoną wartość po prostu zapamiętać tak jak robi klasa java.lang.String. Ważne jest, żeby zrobić to uważnie – z jednej strony chcemy uniknąć jakiejkolwiek synchronizacji z a drugiej strony kod powinien być bezpieczny dla wątków. Rozwiązanie tego problemu prezentuje Jeremy Manson w swoim artykule. Date-Race-Ful Lazy Initialization for Performance. W skrócie sprowadza się ono do wykorzystania idiomu pojedyńczego sprawdzenia z wyścigiem opisanego m.in w książce Java. Efektywne programowanie której autorem jest Joshua Blocha – szczerze polegam.

Oczywiście, proponowane rozwiązanie to optymalizacja która znajduje zastosowanie tylko w specyficznych przypadkach. Nie przyspiesza np. w żaden sposób działania klasy HashMap ponieważ obiekty o takiej same wartości funkcji haszującej trafiają to tego samego kubełka więc w procesie wyszukiwania wartości dla podanego klucza w przypadku kolizji metoda equals wywoływana jest na obiektach które mają taką samą wartość funkcji haszującej.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s