Hashtables

21. juni 2002

Spørgsmål: Når jeg bruger et objekt som en nøgle i en Hashtable, hvad i objektklassen skal jeg tilsidesætte, og hvorfor?

EN: Når du opretter dit eget nøgleobjekt til brug i en Hashtable, skal du tilsidesætte Objekt. Ligestilling () og Object.hashCode () metoder siden Hashtable bruger en kombination af nøglerne hashCode () og lige med() metoder til at gemme og hente sine poster hurtigt. Det er også en generel regel, at når du tilsidesætter lige med(), du tilsidesætter altid hashCode ().

Mere om hvorfor

En lidt mere dybtgående forklaring hjælper dig med at forstå Hashtable's mekanisme til opbevaring og hentning. EN Hashtable indeholder internt spande, hvor det gemmer nøgle / værdiparene. Det Hashtable bruger nøglens hashkode til at bestemme, til hvilken bucket nøgle / værdipar skal kortlægges.

Figur 1 viser a Hashtable og dens spande. Når du sender en nøgle / værdi til Hashtable, spørger den nøglens hashkode. Det Hashtable bruger denne kode til at bestemme den skovl, hvor nøglen / værdien skal placeres. Så hvis f.eks. Hashkoden er lig med nul, er Hashtable placerer værdien i Bucket 0. Ligeledes, hvis hashkoden er to, er Hashtable placerer værdien i Bucket 2. (Dette er et forenklet eksempel; Hashtable vil massere hashkoden først, så Hashtable forsøger ikke at indsætte værdien uden for skovlen.)

Ved at bruge hashkoden på denne måde, Hashtable kan også hurtigt bestemme i hvilken spand den har placeret værdien, når du prøver at hente den.

Hashkoder repræsenterer dog kun halvdelen af ​​billedet. Hashkoden fortæller kun Hashtable i hvilken spand nøglen / værdien skal slippes. Nogle gange kan flere objekter dog kortlægges til den samme spand, en begivenhed kendt som en kollision. I Java er Hashtable reagerer på en kollision ved at placere flere værdier i den samme spand (andre implementeringer kan håndtere kollisioner forskelligt). Figur 2 viser, hvad en Hashtable kan se ud efter et par sammenstød.

Forestil dig nu, at du ringer få() med en nøgle, der kortlægges til Bucket 0. Hashtable bliver nu nødt til at udforme en sekventiel søgning gennem nøgle / værdiparene i Bucket 0 for at finde den ønskede værdi. For at udføre denne opslag skal Hashtable udfører følgende trin:

1. Forespørg nøglens hashkode
2. Hent listen over nøgle / værdier, der findes i spanden givet af hashkoden
3. Scan igennem hver post i rækkefølge, indtil en nøgle, der svarer til nøglen, sendes ind få() er fundet

Et langt svar på et kort spørgsmål ved jeg, men det bliver værre. Korrekt tilsidesættelse lige med() og hashCode () er en ikke-privat øvelse. Du skal være yderst forsigtig for at garantere begge metoders kontrakter.

Ved implementering af lig ()

Ifølge lige med() Javadoc, metoden skal være i overensstemmelse med følgende regler:

"Det lige med() metoden implementerer en ækvivalensrelation:

• Det er refleksivt: For enhver referenceværdi x, x.equals (x) skal vende tilbage sandt
• Det er symmetrisk: For alle referenceværdier x og y, x.equals (y) skal returnere sandt, hvis og kun hvis y.equals (x) returnerer sandt
• Det er forbigående: For alle referenceværdier x, y og z, hvis x.equals (y) returnerer sandt og y.equals (z) returnerer derefter sandt x.equals (z) skal vende tilbage sandt
• Det er konsistent: For alle referenceværdier x og y, flere påkald af x.equals (y) konsekvent returnere sandt eller konsekvent returnere falsk, forudsat at ingen information, der bruges i sammenligning med objektet, er ændret
• For enhver ikke-nul referenceværdi x, x.equals (null) skal returnere falsk "

I Effektiv Java, Joshua Bloch tilbyder en fem-trins opskrift til at skrive en effektiv lige med() metode. Her er opskriften i kodeform:

offentlig klasse EffectiveEquals {private int valueA; privat int værdiB; . . . offentlige boolske er lig med (Objekt o) {hvis (dette == o) {// Trin 1: Udfør en == testretur sand; } if (! (o eksempel of EffectiveEquals)) {// Trin 2: Forekomst af check returnerer false; } EffectiveEquals ee = (EffectiveEquals) o; // Trin 3: Cast-argument // Trin 4: Kontroller for hvert vigtigt felt, om de er lige // For primitive brug == // For objekter skal du bruge lig med (), men sørg også for at // håndtere null-sagen første retur ee.valueA == værdi A && ee.valueB == værdi B; }. . . } 

Bemærk: Du behøver ikke udføre en nulcheck siden null forekomst af EffectiveEquals vil evaluere til falsk.

Endelig går du tilbage til til trin 5 lige med()kontrakt og spørg dig selv, om lige med() metoden er refleksiv, symmetrisk og transitiv. Hvis ikke, ordne det!

Ved implementering af hashCode ()

Til hashCode ()'s generelle kontrakt, siger Javadoc:

• "Hver gang det påberåbes det samme objekt mere end en gang under en udførelse af en Java - applikation, hashCode () metoden skal konsekvent returnere det samme heltal, forudsat at ingen information, der bruges i lig med sammenligninger på objektet, ændres. Dette heltal behøver ikke at være konsistent fra en udførelse af en applikation til en anden udførelse af den samme applikation.
• Hvis to objekter er ens i henhold til er lig med (Objekt) metode og derefter kalde hashCode () metode på hvert af de to objekter skal producere det samme heltal resultat.
• Det kræves ikke, at hvis to objekter er ulige i henhold til er lig med (java.lang.Object metode og derefter kalde hashCode () metode på hvert af de to objekter skal producere forskellige heltalresultater. Programmøren skal dog være opmærksom på, at frembringelse af forskellige heltalresultater til ulige objekter kan forbedre ydeevnen for hashtables. "

Oprettelse af en korrekt fungerende hashCode () metoden viser sig vanskelig; det bliver endnu vanskeligere, hvis det pågældende objekt ikke er uforanderligt. Du kan beregne en hashcode for et givet objekt på mange måder. Den mest effektive metode baserer antallet på objektets felter. Desuden kan du kombinere disse værdier på forskellige måder. Her er to populære tilgange:

• Du kan omdanne objektets felter til en streng, sammenkæde strengene og returnere den resulterende hashkode
• Du kan tilføje hvert felts hashkode og returnere resultatet

Mens der findes andre, mere grundige tilgange, viser de to førnævnte tilgange sig at være den letteste at forstå og implementere.

Tony Sintes er en uafhængig konsulent og grundlægger af First Class Consulting, et konsulentfirma, der har specialiseret sig i at bygge bro over forskellige virksomhedssystemer og træning. Uden for førsteklasses rådgivning er Tony en aktiv freelance skribent samt forfatter af Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Lær mere om dette emne

• Gå til. For Hashtable Javadoc

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

• Vipan Singlas "Implementering er lig med () og hashCode ()" giver en grundig diskussion om tilsidesættelse af metoderne lig () og hashCode ()

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

• Objektet. Er lig med () 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 ()

• Til Joshua Blochs Effektiv Java-programmeringssprogguide (Addison Wesley Professional, 2001; ISBN0201310058), gå til

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

• Du kan finde flere artikler om Java-klasser og -metoder i API'er sektion af JavaWorld 's Aktuelt indeks

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

• Ønsker mere? Se Java Q&A indeksside for det fulde Q & A-katalog

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

• For mere end 100 indsigtsfulde Java-tip fra nogle af de bedste sind i branchen, besøg JavaWorld 's Java-tip indeksside

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

• Lær grundlæggende om Java i vores Java Nybegynder diskussion

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

• Tilmeld dig JavaWorlder gratis ugentligt Core Java e-mail-nyhedsbrev

  //www.javaworld.com/subscribe

• Du finder et væld af it-relaterede artikler fra vores søsterpublikationer på .net

Denne historie, "Hashtables" blev oprindeligt udgivet af JavaWorld.