Hashtables

21. června 2002

Otázka: Když používám objekt jako klíč v Hashtable, co ve třídě Object musím přepsat a proč?

A: Když vytvoříte vlastní klíčový objekt pro použití v a Hashtable, musíte přepsat Object.equals () a Object.hashCode () metody od Hashtable používá kombinaci klíčů hashCode () a se rovná() metody rychlého ukládání a načítání jeho záznamů. Je také obecným pravidlem, že když přepíšete se rovná(), vždy přepíšete hashCode ().

Více o tom proč

Trochu podrobnější vysvětlení vám pomůže pochopit HashtableMechanismus pro ukládání a načítání. A Hashtable interně obsahuje segmenty, do kterých ukládá páry klíč / hodnota. The Hashtable používá hashcode klíče k určení, ke kterému segmentu by měl pár klíč / hodnota mapovat.

Obrázek 1 ukazuje a Hashtable a jeho vědra. Když předáte klíč / hodnotu do Hashtable, dotazuje se na hashcode klíče. The Hashtable používá tento kód k určení segmentu, do kterého se má klíč / hodnota umístit. Například pokud se hashcode rovná nule, pak Hashtable umístí hodnotu do bloku 0. Podobně, pokud je hashcode dva, pak Hashtable umístí hodnotu do kbelíku 2. (Toto je zjednodušující příklad; Hashtable nejdříve masíruje hashcode, takže Hashtable nezkouší vložit hodnotu mimo kbelík.)

Tímto způsobem se použije hashcode Hashtable při pokusu o načtení také rychle určí, do kterého segmentu umístil hodnotu.

Hashcodes však představují pouze polovinu obrázku. Hash kód říká pouze Hashtable do kterého kbelíku odhodit klíč / hodnotu. Někdy však může více objektů mapovat do stejného segmentu, což je událost známá jako srážka. V Javě je Hashtable reaguje na kolizi umístěním více hodnot do stejného kbelíku (jiné implementace mohou kolize zpracovávat odlišně). Obrázek 2 ukazuje, co a Hashtable může vypadat jako po několika srážkách.

Nyní si představte, že zavoláte dostat() s klíčem, který se mapuje na Bucket 0. The Hashtable nyní budete muset provést sekvenční vyhledávání pomocí párů klíč / hodnota v segmentu 0, abyste našli požadovanou hodnotu. Chcete-li provést toto vyhledávání, Hashtable provede následující kroky:

1. Dotaz na hashcode klíče
2. Načíst seznam klíčů / hodnot, které se nacházejí v segmentu daném hashcode
3. Procházejte postupně každou položku, dokud se nevyrovná klíč, který se rovná klíči předanému do dostat() je nalezeno

Dlouhou odpověď na krátkou otázku vím, ale zhoršuje se to. Správně převažující se rovná() a hashCode () je netriviální cvičení. Musíte být velmi opatrní, abyste zajistili smlouvy obou metod.

O implementaci equals ()

Podle se rovná() Javadoc, metoda musí splňovat následující pravidla:

„The se rovná() metoda implementuje vztah ekvivalence:

• Je reflexivní: Pro jakoukoli referenční hodnotu x, x.equals (x) by se měl vrátit true
• Je symetrický: Pro jakékoli referenční hodnoty xay x.equals (y) by se měl vrátit true právě tehdy y.equals (x) vrací true
• Je to tranzitivní: Pro jakékoli referenční hodnoty x, yaz, pokud x.equals (y) vrací true a y.equals (z) pak se vrátí true x.equals (z) by se měl vrátit true
• Je to konzistentní: U všech referenčních hodnot xay platí několik vyvolání x.equals (y) důsledně vrátí true nebo důsledně vrátí false, za předpokladu, že se nezmění žádné informace použité při srovnávání rovnosti objektu
• Pro jakoukoli nenulovou referenční hodnotu x, x.equals (null) by měl vrátit false “

v Efektivní Java, Joshua Bloch nabízí pětistupňový recept na efektivní psaní se rovná() metoda. Zde je recept ve formě kódu:

veřejná třída EffectiveEquals {private int valueA; soukromá int hodnota B; . . . public boolean equals (Object o) {if (this == o) {// Krok 1: Proveďte == testovací návrat true; } if (! (o instanceof EffectiveEquals)) {// Krok 2: Instance šeku return false; } EffectiveEquals ee = (EffectiveEquals) o; // Krok 3: Cast argument // Krok 4: U každého důležitého pole zkontrolujte, zda jsou stejná // U primitiv použijte == // U objektů použijte equals (), ale nezapomeňte také // zpracovat nulový případ první návrat ee.valueA == hodnotaA && ee.valueB == hodnotaB; }. . . } 

Poznámka: Od té doby nemusíte provádět nulovou kontrolu nulová instance EffectiveEquals vyhodnotí jako nepravdivé.

Nakonec se v kroku 5 vraťte zpět k se rovná()smlouva a zeptejte se sami sebe, zda se rovná() metoda je reflexivní, symetrická a tranzitivní. Pokud ne, opravte to!

Při implementaci hashCode ()

Pro hashCode ()Generální smlouva, Javadoc říká:

• "Kdykoli je vyvolán na stejném objektu vícekrát během provádění aplikace Java, hashCode () metoda musí důsledně vracet stejné celé číslo za předpokladu, že se nezmění žádná informace použitá při srovnávání rovnosti objektu. Toto celé číslo nemusí zůstat konzistentní z jednoho spuštění aplikace na jiné spuštění stejné aplikace.
• Pokud jsou dva objekty stejné podle rovná se (Objekt) metoda, pak volání hashCode () metoda na každém ze dvou objektů musí vyprodukovat stejný celočíselný výsledek.
• Není nutné, aby pokud jsou dva objekty nerovné podle rovná se (java.lang.Object metoda, pak volání hashCode () metoda na každém ze dvou objektů musí vyprodukovat odlišné celočíselné výsledky. Programátor by si však měl být vědom, že vytváření odlišných celočíselných výsledků pro nerovné objekty může zlepšit výkon hashtable. "

Vytváření správně fungujícího hashCode () metoda se ukazuje jako obtížná; je to ještě obtížnější, pokud dotyčný objekt není neměnný. Můžete vypočítat hashcode pro daný objekt mnoha způsoby. Nejúčinnější metoda založí číslo na polích objektu. Kromě toho můžete tyto hodnoty kombinovat různými způsoby. Zde jsou dva populární přístupy:

• Můžete změnit pole objektu na řetězec, zřetězit řetězce a vrátit výsledný hashcode
• Můžete přidat hashcode každého pole a vrátit výsledek

Zatímco existují další, důkladnější přístupy, dva výše uvedené přístupy se ukázaly jako nejsnadnější pro pochopení a implementaci.

Tony Sintes je nezávislý konzultant a zakladatel poradenské firmy First Class Consulting, která se specializuje na přemostění různorodých podnikových systémů a školení. Mimo First Class Consulting je Tony aktivním spisovatelem na volné noze a autorem Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Další informace o tomto tématu

• Hashtable Javadoc najdete na

  //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

• „Implementace equals () a hashCode ()“ od Vipana Singly poskytuje podrobnou diskusi o přepsání metod equals () a hashCode ()

  //www.vipan.com/htdocs/hashcode_help.html

• Object.equals () Javadoc

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

• Javadoc Object.hashCode ()

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode ()

• Pro Joshuu Blocha Efektivní průvodce programovacím jazykem Java (Addison Wesley Professional, 2001; ISBN0201310058), přejděte na

  //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

• Další články o třídách a metodách Java najdete na webu API část JavaWorld 's Aktuální rejstřík

  //www.javaworld.com/channel_content/jw-apis-index.shtml

• Chcete více? Viz Java Q&A indexová stránka pro úplný katalog otázek a odpovědí

  //www.javaworld.com/columns/jw-qna-index.shtml

• Více než 100 užitečných tipů pro prostředí Java od nejlepších odborníků v oboru najdete na webu JavaWorld 's Tipy pro Java indexová stránka

  //www.javaworld.com/columns/jw-tips-index.shtml

• Naučte se základy Java v našem Java začátečník diskuse

  //forums.idg.net/[email protected]@.ee6b804

• Přihlásit se JavaWorldje týdně zdarma Core Java e-mailový zpravodaj

  //www.javaworld.com/subscribe

• Spoustu článků o IT z našich sesterských publikací najdete na .net

Tento příběh „Hashtables“ původně publikoval JavaWorld.