Hashtables

21. junij 2002

V: Ko uporabim objekt kot ključ v tabeli Hashtable, kaj v razredu Object moram preglasiti in zakaj?

A: Ko ustvarite svoj ključni objekt za uporabo v Hashtable, morate preglasiti Object.equals () in Object.hashCode () metode od Hashtable uporablja kombinacijo tipk hashCode () in enako () metode za hitro shranjevanje in pridobivanje vnosov. Prav tako je splošno pravilo, da ko preglasite enako (), vedno preglasiš hashCode ().

Več o tem, zakaj

Nekoliko bolj poglobljena razlaga vam bo pomagala razumeti Hashtablemehanizem za shranjevanje in iskanje. A Hashtable interno vsebuje segmente, v katerih shranjuje pare ključ / vrednost. The Hashtable uporablja hashcode ključa, da določi, v kateri segment naj se preslika par ključ / vrednost.

Slika 1 prikazuje a Hashtable in vedra. Ko predate ključ / vrednost v Hashtable, vpraša hashcode ključa. The Hashtable uporablja to kodo za določitev segmenta, v katerega bo postavljen ključ / vrednost. Torej, če je hashcode na primer enak nič, bo Hashtable postavi vrednost v vedro 0. Podobno je, če je hashcode dve, Hashtable postavi vrednost v vedro 2. (To je poenostavljen primer; Hashtable bo najprej masiral hashcode, tako da Hashtable ne poskuša vstaviti vrednosti izven segmenta.)

Z uporabo hashcode na ta način, Hashtable lahko tudi hitro ugotovi, v kateri segment je dal vrednost, ko jo poskušate pridobiti.

Hashcode pa predstavljajo le polovico slike. Hashcode samo pove Hashtable v katero vedro naj spusti ključ / vrednost. Včasih pa se lahko več predmetov preslika v isto vedro, dogodek, znan kot trčenje. V Javi je Hashtable se na trk odzove tako, da v isti vedro postavi več vrednosti (druge izvedbe lahko trke obravnavajo drugače). Slika 2 prikazuje, kaj a Hashtable lahko videti kot po nekaj trkih.

Zdaj pa si predstavljajte, da ste poklicali dobili () s ključem, ki se preslika na vedro 0. The Hashtable bo zdaj moral izvesti zaporedno iskanje po parih ključ / vrednost v segmentu 0, da bo našel zahtevano vrednost. Za izvedbo tega iskanja se Hashtable izvede naslednje korake:

1. Poizvedite hashcode ključa
2. Pridobite seznam ključev / vrednosti, ki se nahajajo v vedru, ki ga daje hashcode
3. Vsak vnos pregledujte zaporedno, dokler ne pride do ključa, ki je enak ključu, v katerega ste vstopili dobili () je najdeno

Dolg odgovor na kratko vprašanje vem, vendar se poslabša. Pravilno preglasitev enako () in hashCode () je netrivialna vaja. Bodite zelo previdni, da zagotovite pogodbe obeh metod.

O izvajanju enakih ()

Glede na enako () Javadoc, mora biti metoda v skladu z naslednjimi pravili:

"The enako () metoda izvaja razmerje enakovrednosti:

• Je refleksiven: za katero koli referenčno vrednost x x.equals (x) naj se vrne res
• Simetrična je: za vse referenčne vrednosti x in y, x.equals (y) mora vrniti true, če in samo če y.equals (x) vrne true
• Je prehoden: Za vse referenčne vrednosti x, y in z, če x.equals (y) vrne true in y.equals (z) vrne true, torej x.equals (z) naj se vrne res
• Dosledno je: za vse referenčne vrednosti x in y večkratni klic x.equals (y) dosledno vrne true ali dosledno vrne false, pod pogojem, da ni spremenjena nobena informacija, uporabljena v enakih primerjavah predmeta
• Za katero koli ničelno referenčno vrednost x, x.equals (null) naj vrne false "

V Učinkovita Java, Joshua Bloch ponuja petstopenjski recept za pisanje učinkovitega enako () metoda. Tu je recept v obliki kode:

javni razred EffectiveEquals {private int valueA; zasebna int vrednostB; . . . javna logična vrednost je enako (Objekt o) {if (this == o) {// 1. korak: izvedite == test return true; } if (! (o instanceof EffectiveEquals)) {// 2. korak: Primerek check return false; } EffectiveEquals ee = (EffectiveEquals) o; // 3. korak: Argument za predvajanje // 4. korak: Za vsako pomembno polje preverite, ali so enaka // Za primitive uporabite == // Za predmete uporabite enako (), vendar se prepričajte tudi, da // obravnavate ničelno črko prvi vrne ee.valueA == valueA && ee.valueB == valueB; }. . . } 

Opomba: Ni vam treba izvesti ničelnega preverjanja od ničen primerek EffectiveEquals bo ocenil na false.

Končno se za korak 5 vrnite na enako ()in se vprašajte, če je enako () metoda je refleksna, simetrična in prehodna. Če ne, popravite!

O izvajanju hashCode ()

Za hashCode ()je splošna pogodba, Javadoc pravi:

• "Kadar koli se med izvajanjem aplikacije Java na isti objekt prikliče večkrat, se hashCode () metoda mora dosledno vrniti isto celo število, pod pogojem, da se ne spremeni nobena informacija, uporabljena v enakih primerjavah predmeta. Tega števila ni treba ostati skladno od ene izvedbe aplikacije do druge izvedbe iste aplikacije.
• Če sta dva predmeta enaka glede na je enako (objekt) , nato pa pokličete hashCode () metoda na obeh objektih mora dati enak celoštevilski rezultat.
• Če sta dva predmeta neenaka glede na je enako (java.lang.Object , nato pa pokličete hashCode () metoda na obeh objektih mora ustvariti različne celoštevilske rezultate. Programer pa se mora zavedati, da lahko ustvarjanje ločenih celoštevilskih rezultatov za neenake predmete izboljša zmogljivost hashtables. "

Ustvarjanje pravilno delujočega hashCode () metoda izkaže za težko; postane še težje, če zadevni predmet ni nespremenljiv. Razpršilno kodo za dani objekt lahko izračunate na več načinov. Najučinkovitejša metoda temelji na številu na poljih predmeta. Poleg tega lahko te vrednosti kombinirate na različne načine. Tu sta dva priljubljena pristopa:

• Polja predmeta lahko pretvorite v niz, združite nize in vrnete nastalo hashcode
• Vsakemu polju lahko dodate hashcode in vrnete rezultat

Medtem ko obstajajo drugi, bolj temeljiti pristopi, sta se dva omenjena pristopa najlažje razumeti in izvajati.

Tony Sintes je neodvisni svetovalec in ustanovitelj svetovalnega podjetja First Class Consulting, ki je specializirano za premostitev različnih podjetniških sistemov in usposabljanja. Zunaj prvovrstnega svetovanja je Tony aktivni samostojni pisec in avtor knjige Sams Teach Yourself Objekt-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Preberite več o tej temi

• Za Hashtable Javadoc pojdite na

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

• Vipan Singla v "Implementacija equals () in hashCode ()" ponuja poglobljeno razpravo o preglasitvi metod equals () in 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)

• Object.hashCode () Javadoc

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

• Za Joshua Blocha Učinkovit vodnik po programskem jeziku Java (Addison Wesley Professional, 2001; ISBN0201310058), pojdite na

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

• Za več člankov o razredih in metodah Java poiščite API-ji odsek JavaWorld 's Aktualni indeks

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

• Želijo več? Glej Vprašanja in odgovori o Javi indeksna stran za celoten katalog Vprašanj

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

• Obiščite več kot 100 vpoglednih nasvetov Java nekaterih najboljših mož v poslu JavaWorld 's Java Nasveti indeksna stran

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

• Spoznajte osnove Java v našem Začetnik Java diskusija

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

• Prijavite se za JavaWorldje brezplačen tedensko Jedro Java e-novice

  //www.javaworld.com/subscribe

• Na naslovu .net boste našli ogromno člankov, povezanih z IT, iz naših sestrskih publikacij

To zgodbo "Hashtables" je prvotno objavil JavaWorld.