hashCode() - do czego to jest?

Do czego służy ta funkcja? Co ona zwraca? Do czego może się przydać?

przy HashMap na przyklad
ogolna zasada jest taka, ze jesli przeslaniasz equals musisz przeslonic takze hashCode
jesli dla dwoch obiektow equals zwraca true hashCode zwraca ta sama liczbe

pozdrawiam

moze jest ktos, kto czuje sie na silach napisac 'best practices'? ;-P

Co rozumiesz przez BP? W Dokumentacji jak i w tutorialach są opisane zasady tworzenia metody hashCode i equals.

Ogólnie metoda ta zwraca Hash ( czyli w tym przypadku liczbę całkowitą ) która reprezentuje
dany obiekt klasy. Możesz poczytać oczywiście w doc. ale zasada jest taka że funkcja ta powinna
zwracać ten sam hash przy każdym wywołaniu tej metody na tym samym obiekcie.
I jeszcze jedno gdy np o1.equals(2) jest prawdą => o1.hashCode() == o2.hashCode() jest prawdziwe.

Hashtable, HashMap ( korzystające z Hashtable ) wykorzystuje metodę hashCode()
tzn liczony jest hash dla kluczy w ten sposób w stałym czasie możemy uzyskać dostęp
do elementów wyżej wspominanych kolekcji.

Widzę, że nikt tak naprawdę nie odpowiedział na pytanie.

hashCode(), to funkcja, która na podstawie wartości obiektu swojego typu zwraca liczbę całkowitą. Różne obiekty różnych typów mogą zwracać tę samą wartość, ale dwa różne obiekty tego samego typu najlepiej powinny dawać unikalne wartości (nie powtarzające się).

Teraz - do czego to służy?
Skoro różne wartości obiektów dają zawsze różne wartości, to można te wartości wykorzystać jako indeks bardzo szybkiej tablicy referencji obiektów. Dzięki takiemu podejściu teoretyczny koszt dostępu do obiektu to zawsze jedno dodawanie. Tak właśnie działa hashMap.
Oczywiście tworzenie tablic o zakresie indeksów -2mld..+2mld (32-bit) byłoby bezsensownym marnotrawstwem pamięci, więc tworzy się znacznie mniejszą tablicę (np. 8192 elementów), w której indeksy zawija się modulo jej rozmiar. Zwykle rozmiar jest potęgą dwójki, co redukuje modulo (resztę z dzielenia) do znacznie szybszej operacji binarnej AND. "Zawinięte" indeksy oraz powtarzające się indeksy różnych typów obiektów powodują, że pod ten sam indeks trafią różne obiekty (również tego samego typu). A to powoduje, że wartościami komórek tej tablicy nie mogą być referencje tych obiektów, ale listy tych obiektów o powtarzającym się "zawiniętym" hashCode. Powoduje to konieczność wyszukania na takiej liście właściwego obiektu, o który nam chodziło. I właśnie w tym miejscu potrzebne jest poprawne zdefiniowanie funkcji equal, która pozwoli wyszukać liniowo właściwy obiekt przez porównanie z szukanym wzorcem. Oczywiście kiedy dodajemy do mapy nie potrzebujemy niczego wyszukiwać, więc tylko dodajemy obiekt (referencję) do listy, co też jest bardzo szybkie.

Tak więc cała operacja na hash mapie sprowadza się do wyliczenia wartości hashCode, jednego dodawania dla wyliczenia indeksu, jednej operacji AND oraz, albo wyszukania obiektu na kilkuelementowej liście (często zdegenerowanej do jednego elementu), albo dodania do listy (często pustej). To właśnie dlatego hash mapa jest tak niesamowicie szybka i ma średnio stały koszt czasu dodawania i wyciągania obiektów.
A to wszystko opiera się tylko na koncepcji kodu hash.
Jedynym wartym uwagi kosztem jest czas obliczania samego kodu - dlatego ważne jest, żeby wyliczać go dobrze i wydajnie.

Olamagato napisał(a)

Widzę, że nikt tak naprawdę nie odpowiedział na pytanie.

Czytając twojego posta wydaje się, że coś w tym jest ;)

Olamagato napisał(a)

hashCode(), to funkcja, która na podstawie wartości obiektu swojego typu zwraca liczbę całkowitą. Różne obiekty różnych typów mogą zwracać tę samą wartość, ale dwa różne obiekty tego samego typu najlepiej powinny dawać unikalne wartości (nie powtarzające się).

Teraz - do czego to służy?
Skoro różne wartości obiektów dają zawsze różne wartości, to można te wartości wykorzystać jako indeks bardzo szybkiej tablicy referencji obiektów. Dzięki takiemu podejściu teoretyczny koszt dostępu do obiektu to zawsze jedno dodawanie. Tak właśnie działa hashMap.
Oczywiście tworzenie tablic o zakresie indeksów -2mld..+2mld (32-bit) byłoby bezsensownym marnotrawstwem pamięci, więc tworzy się znacznie mniejszą tablicę (np. 8192 elementów)

np domyślnie w HashMap'ie jest wartość 16;

Bardzo fajnie to ogólnie opisałeś.

Jeśli można, odkopię nieco temat.

1. Czy jeżeli będę miał np. dwa obiekty jTextPane o tym samym... wszystkim, to czy hashcode będzie ten sam?
2. Czy istnieje możliwość odwrócenia działania hashcode (np. z liczby całkowitej na Object, później rzutowanie i otrzymujemy obiekt pierwotny)

1. Z szybkiego rzutu okiem na dokumentację wnioskuję, że hashCode() z Objecta nie został przeładowany, a więc generalnie z bardzo dużym prawdopodobieństwem hashCode będą różne dla różnych JTextPane.
2. Nie, hashCode() jest zwykle funkcją stratną, tzn hashCode generalnie nie zawiera wszystkich informacji potrzebnych do odtworzenia obiektu.

Odświeżę nieco temat :). Nie bardzo tylko rozumiem w tym wszystkim dlaczego jeżeli przesłaniamy metodę equals(Object o) to powinniśmy również przesłonić hashCode()? Po co ta zasada, że jeżeli: o1.equals(o2) => o1.hashCode() = o2.hashCode() ? Przecież, jeżeli będziemy mieli dwa obiekty o1 i o2 dla których metoda equals zwróci true, ale z różnymi hashami to niezależnie czy trafią one do tej samej listy w hashMapie czy do różnych to i tak przy próbie ich odnalezienia zostanie znaleziony poprawny indeks i dalej po porównaniu hashy i kluczy zostanie znaleziony ten właściwy. Czy gdzieś popełniam błąd ?

Chyba, że chodzi o samą ideę aby spod danego klucza dało się wyciągnąć tylko jedną wartość? Bo inaczej możemy tworzyć obiekty dla którch equals(klucz) zwróci true ale o różnych hashach - i w ten sposób pod jeden klucz podpinać i wyciągać różne obiekty - wartości.

@Qbisiek popełniasz błąd. Z hashy korzysta na przykład HashSet<>. HashSet zapewnia że zawiera tylko unikalne obiekty. Jeśli u ciebie są dwa identyczne obiekty z różnymi hashami to ten kontrakt będzie złamany.

W takim razie proszę, kod wyciągnięty z implementacji HashMap, prześledź go i zobacz co się stanie jeśli nadpiszesz equals a nie nadpiszesz hashcode, i na odwrót:

 
public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key.hashCode());
         int i = indexFor(hash, table.length);
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }
 
         modCount++;
         addEntry(hash, key, value, i);
         return null;
}