Java Efektivně, rada 8

JE_08: Když překrýváte equals, vždy překryjte také hashCode

Častým zdrojem chyb je nepřekrytí metody hashCode. Metodu hashCode musíte překrýt ve všech třídách, které překrývají equals. Pokud to neučiníte, porušíte tím obecný kontrakt Object.hashCode, což zabrání vaší třídě v řádném fungování ve spojení se všemi hešovanými kolekcemi včetně HashMap, HashSet a Hashtable.

Zde máme kontrakt zkopírovaný ze specifikace java.lang.Object:

Kdykoli je zavolána na témže objektu více než jednou během vykonávání aplikace, musí metoda hashCode stále vracet stejné celé číslo za předpokladu, že nebyly změněny žádné informace používané v porovnáních equals daného objektu. Toto celé číslo nemusí být stejné při různých vykonáváních téže aplikace.
Pokud jsou si dva objekty rovné podle metody equals(Object), pak volání metody hashCode s každým z těchto objektů musí vytvořit stejný celočíselný výsledek.
Není vyžadováno, aby za situace, kdy si nejsou dva objekty rovné podle metody equals(Object), volání metody hashCode s oběma objekty vytovřilo odlišné celočíselné výsledky. Programátor však musí mít na paměti, že vytvoření odlišných celočíselných výsledků u nerovných objektů může zlepšit výkonnost hešovacích tabulek.

Pokud nepřekryjete hashCode, pak bude narušeným klíčovým předpokladem ten druhý: rovné objekty musejí mít rovné hešovací kódy. Dvě odlišné instance se mohou logicky rovnat podle metody equals dané třídy, ale pro metodu hashCode třídy Object jsou to jen dva objekty, které nemají mnoho společného. proto metody hashCode objektu vrátí dvě zdánlivě náhodná čísla a nikoli dvě stejná čísla, jak vyžaduje uvedený kontrakt.

Zvažme například následující jednoduchou třídu PhoneNumber, jejíž metoda equals je zkonstruována podle receptu v radě 7:

public final class PhoneNumber {
	private final short areaCode;
	private final short exchange;
	private final short extension;

	public phoneNumber(int areaCode, int exchange, int extension) {
		rangeCheck(areaCode, 999, "kód oblasti");
		rangeCheck(exchange, 999, "ústředna");
		rangeCheck(extension, 9999, "rozšíření");
		this.areaCode = (short) areaCode;
		this.exchange = (short) exchange;
		this.extension = (short) extension;
	}

	private static void rangeCheck(int, int, String name) {
		if (arg < || arg > max)
			throw new IllegalArgumentException(name +": "+ arg);
	}

	public boolean equals(Object o) {
		if (o == this)
			return true;
		if ('(o instanceof PhoneNumber))
			return false;
		PhoneNumber pn = (PhoneNumber)o;
		return pn.extension == extension &&
			pn.exchange == exchange &&
			pn.areaCode == areaCode;
	}

	// Chybí metoda hashCode!

	. . .

}

Předpokládejme, že se pokusíte použít tuto třídu s HashMap:

	Map m = new HashMap();
	m.put(new PhoneNumber(408, 867, 5309), "Jenny");

V tomto okamžiku byste mohli očekávat, že m.get(new PhoneNumber(408, 867, 5309)) vrátí "Jenny", vrátí se však null. Všimněte si, že se tu vyskytují dvě instance PhoneNumber. Jedna se používá ke vložení do HashMap a druhá, rovná instance, se používá k (pokusu o) převzetí. Protože třída PhoneNumber nepřekryla metodu hashCode, mají dvě rovné instance nerovné hešovací kódy, což porušuje kontrakt hashCode. Proto metoda get hledá telefonní číslo v jiném hešovacím sektoru, než v jakém bylo uloženo metodou put. Náprava tohoto problému spočívá v poskytnutí řádné metody hashCode pro třídu PhoneNumber.

Jak by tedy měla metoda hashCode vypadat? Je velmi triviální napsat nějakou platnou ale nedoboru metodu. Například ta následující je vždy platná, nikdy byste ji ale neměli používat:

	// Nejhorší možná platná hešovací funkce - nikdy nepoužívejte!
	public int hashCode() {
		return 42;
	}

Je platná, protože zajišťuje, že rovné objekty budou mít stejný hešovací kód. je děsivá, protože zajišťuje, že všechny objekty budou mít stejný hešovací kód. proto se každý objekt hešuje do stejného sektoru a hešovací tabulky se degenerují na propojené seznamy. Programy by měly pracovat v lineárním toku času a nikoli v kvadratickém. V případě velkých hešovacích tabulek j eto rozdíl mezi fungováním a nefungováním.

Dobrá hešovací funkce má tendenci vytvářet nerovné hešovací kódy pro nerovné objekty. Právě tohle má na mysli třetí předpoklad kontraktu hashCode. V ideálním případě by měla hešovací funkce distribuovat jakoukoli rozumnou kolekci nerovných instancí uniformně všemi možnými hešovacími hodnotami. Dosažení tohoto ideálu může být extrémně obtížné. naštěstí však není tak složité dosáhnout rozumné aproximace. Zde je jednoduchý recept:

Uložte nějakou konstantní nenulovou hodnotu, řekněme 17, v proměnné typu int nazvané result.
Pro každý významný atribut f ve svém objektu (to znamená každý atribut zvažovaný metodou equals), udělejte následující:
1. Vypočtěte hešovací kód c typu int pro daný atribut:
  1. Je-li atribut typu boolean, vypočtěte (f ? 0 : 1)
  2. Je-li atribut typu byte, char, short nebo int, vypočtěte (int)f
  3. Je-li atribut typu long, vypočtěte (int)(f ^ (f >>> 32))
  4. Je-li atribut typu float vypočtěte Float.floatToIntBits(f)
  5. Je-li atribut typu double, vypočtěte Double.doubleToLongBits(f) a pak hešujte výsledek typu long jako v kroku 2.a.iii
  6. Je-li atribut odkazem na objekt a metoda equals jeho třídy porovnává atributy rekurzivním voláním equals, pak volejte s atributem rekurzivně hashCode. Je-li požadováno složitější porovnání, vypočtěte "kanonickou reprezentaci" tohoto pole a zavolejte hashCode na této kanonické reprezentaci. Je-li hodnotou atributu null, vraťte 0 (nebo nějakou jinou konstantu, nula je však obvyklá)
  7. Je-li atribut polem, zacházejte s ním, jako by byl každý prvek samostatným atributem. To znamená, že budete počítat hešovací kód pro každý významný prvek rekurzivním aplikováním těchto pravidel a kombinováním těchto hodnot podle popisu v kroku 2.b
  Zkopírujte hešovací kód c vypočtený v jednom z kroků do proměnné result takto:
```
	result = 37 * result + c;
    
```
Vraťte result
Když konečně skončíte s vytvářením metody hashCode, zeptejte se sami sebe, zda mají rovné instance rovné hešovací kódy. Pokud ne, zjistěte proč a problém opravte.

Z výpočtu hešovacího kódu lze vypustit nadbytečné (redundantní) atributy. Jinými slovy, můžete vyloučit všechny atributy, jejichž hodnotu lze vypočítat z atributů, které jsou součástí výpočtu. Je nutné vyloučit všechny atributy, které se nepoužívají v porovnáních rovnosti. Pokud tak neučiníte, můžete porušit druhý předpoklad kontraktu hashCode.

V kroku 1 je použita nenulová počáteční hodnota, takže hešovací hodnota bude ovlivněna počátečními atributy, jejichž hešovací hodnota vypočtená v kroku 2.1 je nulová. Pokud by byla jako počáteční hodnota v kroku 1 použita nula, celková hešovací hodnota by nebyla ovlivněna žádnými z takových počátečních atributů, čímž by se zvýšil počet kolizí. Hodnota 17 je uvedena jako příklad.

Násobení v kroku 2.2 činí hešovací hodnotu závislou na pořadí atributů a výsledkem je tak mnohem lepší hešovací funkce v případě, že třída obsahuje více podobných atributů. Kdyby bylo násobení vypuštěno například z hešovací funkce třídy String vytvořené tímto postupem, pak by měly všechny anagramy identické hešovací kódy. Násobitel 37 byl vybrán proto, že se jedná o liché prvočíslo. Pokud by se jednalo o sudé číslo a násobení by způsobilo přetečení, došlo by ke ztrátě informací, jelikož násobení dvěma odpovídá posunu. Výhody používání prvočísla nejsou tak zřetelné, tradičně se však k tomuto účelu používají právě prvočísla.

Aplikujme uvedený recept na třídu PhoneNumber. Existují tu tři významné atributy, všechny typu short. Přímočará aplikace receptu nám poskytne následující hešovací funkci:

	public int hashCode() {
		int result = 17;
		result = 37 * result + areaCode;
		result = 37 * result + exchange;
		result = 37 * result + extension;
		return result;
	}

Protože tato metoda vrací výsledek jenoduchého deterministického výpočtu, jehož jedinými vstupy jsou ony tři významné atributy v instanci PhoneNumber, mělo by být zřejmé, že rovné instance PhoneNumber mají rovné hešovací kódy. Tato metoda je ve skutečnosti velmi rozumnou implementací hashCode pro PhoneNumber, která odpovídá těm v knihovnách plaformy Java verze 1.4. Je jednoduchá, rozumně rychlá a šikovně rozděluje nerovná telefonní čísla do různých hešovacích sektorů.

Je-li nějaká třída neměnitelná a náklady na výpočet hešovacího kódu jsou významné, pak zvažte uložení hešovacího kódu do objektu a nikoli jeho přepočítávání, kdykoli je zapotřebí. Věříte-li, že většina objektů tohoto typu se bude používat jako hešovací klíče, pak byste měli počítat hešovací kód v okamžiku vytvoření instance. Jinak můžete zvolit jeho odloženou inicializaci při prvním volání hashCode (rada 48). Není zřejmé, že by z tohoto přístupu naše třída PhoneNumber nějak těžila, přesto si ukážeme, jak to lze učinit:

	// Odloženě inicializovaná, uložená hodnota hashcode
	public int hashCode() {
		if (hashCode == 0) {
			int result = 17;
			result = 37 * result + areaCode;
			result = 37 * result + exchange;
			result = 37 * result + extension;
			hashCode = result;
		}
		return hashCode;
	}

Třebaže recept v této radě poskytuje rozumně dobré hešovací funkce, nepředstavuje ty nejslepší možné, které neposkytují ve verzi 1.4 ani knihovny platformy Java. Vytváření tkových hešovacích funkcí je cílem probíhajícího výzkumu a je to činnost, kterou je nejlepší ponechat matematikům a teoretikům počítačových věd. Další verze platformy Java budou třeba obsahovat vynikající hešovací funkce pro své třídy a pomocné metody umož�ující průměrným programátorům takové hešovací funkce konstruovat. Zatím by však měly techniky popsané v této radě postačovat většině aplikací.

Nesnažte se zvýšit výkonnost tak, že z výpočtu hešovacího kódu odstraníte nějaké významné části objektu. Třebaže může výsledná hešovací funkce běžet rychleji, její kvalita se může zhoršit natolik, že hešovací tabulky budou nepoužitelně pomalé. Taková hešovací funkce se může v praxi stkat zejména s velkou kolekcí instancí, které se liší převážně v oblastech, jež jste se rozhodli ignorovat. Dojde-li k tomu, pak bude hešovací funkce mapovat všechny instance jen k několika málo hešovacím kódům a kolekce používající tyto kódy budou projevovat kvadratickou výkonnost. Není to jen teoretický problém. Hešovací funkce třídy String implementované ve všech verzích platformy Java před verzí 1.2 zkoumaly nejvýše 16 znaků rovnoměrně rozložených v řetězci s počátkem v prvním zanku. V případě rozsáhlých kolekcí hierarchických názvů, například URL adres, se tato hešovací funkce projevovala přesně právě zmíněným patologickým chováním.

Mnoho tříd v knihovnách platformy Java, jako jsou String, Integer a Date, specifikuje přesnou hodnotu vrácenou jejich metodou hashCode jako funkci hodntoy instance. Obecně to však není výhodné, protože to výrazně omezuje vaši schopnost vylepšit danou hešovací funkci v dalších verzích. Ponecháte-li podrobnosti hešovací funkce nespecifikované a najdete-li v ní chybu, pak můžete v další verzi hešovací funkci opravit a přitom se nemusíte starat o zachování kompatibility s klienty závisejícími na přesných hodnotách vrácených danou hešovací funkcí.