Hashtables

21. júna 2002

Otázka: Keď používam objekt ako kľúč v Hashtable, čo v triede Object musím prepísať a prečo?

A: Keď vytvárate vlastný kľúčový objekt na použitie v a Hashtable, musíte prepísať Object.equals () a Object.hashCode () metódy od Hashtable používa kombináciu kľúčov hashCode () a rovná sa () metódy na rýchle ukladanie a načítanie jeho záznamov. Všeobecným pravidlom je tiež to, že keď prepíšete rovná sa (), vždy prepíšete hashCode ().

Viac o tom prečo

Trochu podrobnejšie vysvetlenie vám pomôže pochopiť HashtableMechanizmus ukladania a vyhľadávania. A Hashtable interne obsahuje segmenty, do ktorých ukladá páry kľúč / hodnota. The Hashtable používa hašovací kód kľúča na určenie toho, do ktorého segmentu má byť pár kľúč / hodnota namapovaný.

Obrázok 1 zobrazuje a Hashtable a jeho vedrá. Keď odovzdáte kľúč / hodnotu do Hashtable, vyhľadá hašovací kód kľúča. The Hashtable používa tento kód na určenie segmentu, do ktorého sa má vložiť kľúč / hodnota. Napríklad, ak sa hashcode rovná nule, znak Hashtable umiestni hodnotu do vedra 0. Rovnako, ak je hashcode dva, potom znak Hashtable umiestni hodnotu do vedra 2. (Toto je zjednodušujúci príklad; Hashtable najskôr vymasíruje hashcode, takže Hashtable neskúša vložiť hodnotu mimo segment.)

Použitím hashcode týmto spôsobom Hashtable môže tiež rýchlo určiť, do ktorého segmentu umiestnil hodnotu, keď sa ju pokúsite načítať.

Hashcodes však predstavuje iba polovicu obrázka. Hašovací kód povie iba znaku Hashtable do ktorého vedra odhodiť kľúč / hodnotu. Niekedy sa však môže do rovnakého segmentu namapovať viac objektov, čo je udalosť známa ako a Zrážka. V Jave sa Hashtable reaguje na kolíziu umiestnením viacerých hodnôt do toho istého vedra (iné implementácie môžu kolízie spracovávať odlišne). Obrázok 2 zobrazuje, čo a Hashtable môže vyzerať ako po niekoľkých kolíziách.

Teraz si predstavte, že voláte dostať () s kľúčom, ktorý sa mapuje na vedro 0. The Hashtable teraz budete musieť vykonať postupné vyhľadávanie prostredníctvom párov kľúč / hodnota v segmente 0, aby ste našli požadovanú hodnotu. Ak chcete vykonať toto vyhľadávanie, Hashtable vykoná nasledujúce kroky:

1. Dotaz na hashcode kľúča
2. Vyhľadajte zoznam kľúčov / hodnôt nachádzajúcich sa v segmente daných hašovacím kódom
3. Skenujte postupne každú položku, kým nenájdete kľúč, ktorý sa rovná kľúču vloženému do dostať () je nájdený

Viem, že je to dlhá odpoveď na krátku otázku, ale zhoršuje sa to. Správne prvoradé rovná sa () a hashCode () je netriviálne cvičenie. Musíte byť veľmi opatrní, aby ste zaručili kontrakty oboch metód.

Pri implementácii equals ()

Podľa rovná sa () Javadoc, metóda musí vyhovovať nasledujúcim pravidlám:

„ rovná sa () metóda implementuje vzťah ekvivalencie:

• Je reflexívne: Pre každú referenčnú hodnotu x, x.equals (x) by sa mala vrátiť pravda
• Je to symetrické: Pre akékoľvek referenčné hodnoty x a y, x.equals (y) by sa mala vrátiť pravda vtedy a len vtedy y.equals (x) vracia sa pravda
• Je to tranzitívne: Pre akékoľvek referenčné hodnoty x, yaz, ak x.equals (y) vráti pravdivé a y.equals (z) potom sa vráti pravda x.equals (z) by sa mala vrátiť pravda
• Je to konzistentné: Pre akékoľvek referenčné hodnoty xay viacnásobné vyvolanie hodnoty x.equals (y) dôsledne vracia hodnotu true alebo dôsledne vracia hodnotu false, ak sa nezmenia žiadne informácie použité pri rovnakých porovnaniach na objekte
• Pre akúkoľvek nenulovú referenčnú hodnotu x, x.equals (null) by mal vrátiť false “

V Efektívna Java, Joshua Bloch ponúka päťstupňový recept na efektívne napísanie rovná sa () metóda. Tu je recept vo forme kódu:

verejná trieda EffectiveEquals {private int hodnotaA; private int hodnotaB; . . . public boolean equals (Object o) {if (this == o) {// Krok 1: Vykonajte == testovací návrat true; } if (! (o instanceof EffectiveEquals)) {// Krok 2: inštancia kontroly return false; } EffectiveEquals ee = (EffectiveEquals) o; // Krok 3: Argument Cast // Krok 4: Pre každé dôležité pole skontrolujte, či sú rovnaké // Pre primitívy použite == // Pre objekty použite equals (), nezabudnite však tiež // manipulovať s prázdnymi písmenami prvý návrat ee.valueA == hodnotaA && ee.valueB == hodnotaB; }. . . } 

Poznámka: Odvtedy nemusíte vykonávať nulovú kontrolu nulová inštancia EffectiveEquals vyhodnotí ako nepravdivé.

Nakoniec sa v kroku 5 vráťte späť na rovná sa ()zmluva a opýtajte sa sami seba, či rovná sa () metóda je reflexívna, symetrická a tranzitívna. Ak nie, opravte to!

Pri implementácii hashCode ()

Pre hashCode ()rámcová zmluva, Javadoc hovorí:

• "Kedykoľvek je vyvolaný na rovnakom objekte viackrát počas vykonávania aplikácie Java, hashCode () metóda musí dôsledne vracať to isté celé číslo za predpokladu, že sa nezmenia žiadne informácie použité pri rovnakom porovnaní s objektom. Toto celé číslo nemusí zostať konzistentné od jedného spustenia aplikácie k druhému spusteniu tej istej aplikácie.
• Ak sú dva objekty rovnaké podľa rovná sa (Objekt) metóda, potom volanie hashCode () metóda na každom z dvoch objektov musí vyprodukovať rovnaký celočíselný výsledok.
• Nie je potrebné, aby ak sú dva objekty nerovné podľa rovná sa (java.lang.Object metóda, potom volanie hashCode () metóda na každom z dvoch objektov musí vyprodukovať odlišné celočíselné výsledky. Programátor by si však mal uvedomiť, že vytváranie zreteľných celočíselných výsledkov pre nerovnaké objekty môže zlepšiť výkon hashtable. “

Vytváranie správne fungujúceho hashCode () metóda sa ukazuje ako ťažká; stáva sa to ešte ťažšie, ak predmetný objekt nie je nemenný. Hash kód pre daný objekt môžete vypočítať mnohými spôsobmi. Najefektívnejšia metóda zakladá číslo na poliach objektu. Tieto hodnoty môžete navyše kombinovať rôznymi spôsobmi. Tu sú dva populárne prístupy:

• Polia objektu môžete premeniť na reťazec, reťazce zreťaziť a výsledný hashcode vrátiť
• Môžete pridať hašovací kód každého poľa a vrátiť výsledok

Zatiaľ čo existujú ďalšie, dôkladnejšie prístupy, tieto dva prístupy sa ukazujú ako najľahšie pochopiteľné a implementovateľné.

Tony Sintes je nezávislý konzultant a zakladateľ konzultačnej spoločnosti First Class Consulting, ktorá sa špecializuje na premosťovanie rozdielnych podnikových systémov a školení. Mimo First Class Consulting je Tony aktívnym spisovateľom na voľnej nohe a tiež autorom Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Získajte viac informácií o tejto téme

• Hashtable Javadoc nájdete na

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

• „Implementácia pravidiel equals () a hashCode ()“ spoločnosti Vipan Singla poskytuje podrobnú diskusiu o prepísaní metód 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 ()

• Pre Joshua Blocha Sprievodca efektívnym programovacím jazykom Java (Addison Wesley Professional, 2001; ISBN0201310058), choďte na

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

• Viac článkov o triedach a metódach Java nájdete na webe API časť JavaWorld 's Aktuálny index

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

• Chcieť viac? Viď Java Q&A indexová stránka pre úplný katalóg otázok a odpovedí

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

• Viac ako 100 bystrých tipov pre jazyk Java od najlepších odborníkov v odbore nájdete na webovej stránke JavaWorld 's Tipy pre Java indexová stránka

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

• Naučte sa základy jazyka Java v našom Java začiatočník diskusia

  //forums.idg.net/webx?50@@.ee6b804

• Zaregistrovať JavaWorldje týždenne zadarmo Core Java e-mailový spravodaj

  //www.javaworld.com/subscribe

• Množstvo článkov týkajúcich sa IT z našich sesterských publikácií nájdete na .net

Tento príbeh, „Hashtables“, bol pôvodne publikovaný spoločnosťou JavaWorld.