Hashtables

21. juni 2002

Spørsmål: Når jeg bruker et objekt som en nøkkel i en Hashtable, hva må jeg overstyre i Object-klassen og hvorfor?

EN: Når du lager ditt eget nøkkelobjekt for bruk i en Hashtable, må du overstyre Object.equals () og Object.hashCode () metoder siden Hashtable bruker en kombinasjon av nøklene hashCode () og er lik() metoder for å lagre og hente oppføringene raskt. Det er også en generell regel at når du overstyrer er lik(), du overstyrer alltid hashCode ().

Mer om hvorfor

En litt mer inngående forklaring vil hjelpe deg å forstå Hashtablemekanisme for lagring og henting. EN Hashtable inneholder internt skuffer der den lagrer nøkkel / verdiparene. De Hashtable bruker nøkkelens hashkode for å bestemme hvilken bøtte nøkkel / verdiparet skal tilordnes.

Figur 1 viser a Hashtable og skuffene. Når du overfører en nøkkel / verdi til Hashtable, spør den nøkkelens hashkode. De Hashtable bruker den koden for å bestemme skuffen som nøkkelen / verdien skal plasseres i. Så hvis for eksempel hashkoden er lik null, er Hashtable plasserer verdien i Bucket 0. På samme måte, hvis hashkoden er to, vil Hashtable plasserer verdien i Bucket 2. (Dette er et forenklet eksempel; Hashtable vil massere hashkoden først så Hashtable prøver ikke å sette inn verdien utenfor bøtta.)

Ved å bruke hashkoden på denne måten, blir Hashtable kan også raskt avgjøre i hvilken bøtte den har plassert verdien når du prøver å hente den.

Hashkoder representerer imidlertid bare halvparten av bildet. Hashkoden forteller bare Hashtable i hvilken bøtte du skal slippe nøkkelen / verdien. Noen ganger kan imidlertid flere objekter tilordnes til samme bøtte, en hendelse kjent som en kollisjon. I Java er Hashtable svarer på en kollisjon ved å plassere flere verdier i samme bøtte (andre implementeringer kan håndtere kollisjoner forskjellig). Figur 2 viser hva a Hashtable kan se ut etter noen sammenstøt.

Tenk deg nå at du ringer få() med en nøkkel som kartlegges til Bucket 0. The Hashtable må nå utføre et sekvensielt søk gjennom nøkkel- / verdiparene i Bucket 0 for å finne ønsket verdi. For å utføre denne oppslaget, Hashtable utfører følgende trinn:

1. Spør nøkkelens hashkode
2. Hent listen over nøkkel / verdier som ligger i bøtta gitt av hashkoden
3. Skann gjennom hver oppføring sekvensielt til en nøkkel som tilsvarer nøkkelen som ble gitt inn få() er funnet

Et langt svar på et kort spørsmål vet jeg, men det blir verre. Skikkelig overordnet er lik() og hashCode () er en ikke-trivelig øvelse. Du må være ekstrem forsiktig for å garantere begge metoders kontrakter.

Ved implementering av like ()

Ifølge er lik() Javadoc, metoden må være i samsvar med følgende regler:

"De er lik() metoden implementerer en ekvivalensrelasjon:

• Det er refleksivt: For enhver referanseverdi x, x.equals (x) skal returnere sant
• Det er symmetrisk: For alle referanseverdier x og y, x.equals (y) skal returnere sant hvis og bare hvis y.ekvivalenter (x) returnerer sant
• Det er transitive: For alle referanseverdier x, y og z, hvis x.equals (y) returnerer sant og y.equals (z) returnerer sant, da x.equals (z) skal returnere sant
• Det er konsistent: For alle referanseverdier x og y, flere påkallinger av x.equals (y) konsekvent returner true eller konsekvent returner false, forutsatt at ingen informasjon som brukes i sammenligning med objektet er endret
• For alle ikke-null referanseverdier x, x.equals (null) skal returnere falsk "

I Effektiv Java, Joshua Bloch tilbyr en fem-trinns oppskrift for å skrive en effektiv er lik() metode. Her er oppskriften i kodeform:

offentlig klasse EffectiveEquals {private int valueA; privat int verdiB; . . . offentlig boolsk er lik (Objekt o) {if (dette == o) {// Trinn 1: Utfør en == test return true; } if (! (o eksempel of EffectiveEquals)) {// Trinn 2: Forekomst av sjekk returner falsk; } EffectiveEquals ee = (EffectiveEquals) o; // Trinn 3: Cast argument // Trinn 4: For hvert viktige felt, sjekk om de er like // For primitiver bruk == // For objekter bruk lik () men sørg for å også // håndtere nullsaken første retur ee.valueA == verdi A && ee.valueB == verdi B; }. . . } 

Merk: Du trenger ikke å utføre en nullkontroll siden null forekomst av EffectiveEquals vil evaluere til falsk.

Til slutt, for trinn 5, gå tilbake til er lik()sin kontrakt og spør deg selv om er lik() metoden er refleksiv, symmetrisk og transitiv. Hvis ikke, fikser du det!

Ved implementering av hashCode ()

Til hashCode ()sin generelle kontrakt, sier Javadoc:

• "Hver gang det påberopes på det samme objektet mer enn en gang under en kjøring av et Java - program, blir" hashCode () metoden må konsekvent returnere det samme heltallet, forutsatt at ingen informasjon som brukes i sammenligning med objektet er endret. Dette heltallet trenger ikke å være konsistent fra en kjøring av en applikasjon til en annen kjøring av den samme applikasjonen.
• Hvis to objekter er like i henhold til er lik (Objekt) metode, og deretter kalle hashCode () metoden på hvert av de to objektene må gi det samme heltallresultatet.
• Det er ikke påkrevd at hvis to objekter er forskjellige i henhold til er lik (java.lang.Object metode, og deretter kalle hashCode () metoden på hvert av de to objektene må gi forskjellige heltalresultater. Imidlertid bør programmereren være klar over at å produsere distinkte heltallresultater for ulike objekter kan forbedre ytelsen til hashtables. "

Å skape en riktig fungerende hashCode () metoden viser seg vanskelig; det blir enda vanskeligere hvis det aktuelle objektet ikke er uforanderlig. Du kan beregne en hashcode for et gitt objekt på mange måter. Den mest effektive metoden baserer tallet på objektets felt. Videre kan du kombinere disse verdiene på forskjellige måter. Her er to populære tilnærminger:

• Du kan gjøre objektets felt til en streng, sammenkoble strengene og returnere den resulterende hashkoden
• Du kan legge til hvert felts hashkode og returnere resultatet

Mens det finnes andre, grundigere tilnærminger, viser de to nevnte tilnærmingene seg å være lettest å forstå og implementere.

Tony Sintes er en uavhengig konsulent og grunnlegger av First Class Consulting, et konsulentselskap som spesialiserer seg på å bygge bro over ulike virksomhetssystemer og opplæring. Utenom førsteklasses rådgivning er Tony en aktiv frilansskribent, samt forfatter av Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Lær mer om dette emnet

• For Hashtable Javadoc, gå til

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

• Vipan Singlas "Implementing equals () and hashCode ()" gir en grundig diskusjon om å overstyre lik () og hashCode () -metodene

  //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 ()

• For Joshua Bloch Effektiv Java-programmeringsspråkguide (Addison Wesley Professional, 2001; ISBN0201310058), gå til

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

• For flere artikler om Java-klasser og -metoder, bla gjennom APIer seksjon av JavaWorld 's Aktuell indeks

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

• Ønsker mer? Se Java Q&A indeksside for den fullstendige spørsmål og svar-katalogen

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

• For mer enn 100 innsiktsfulle Java-tips fra noen av de beste hodene i virksomheten, besøk JavaWorld 's Java-tips indeksside

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

• Lær det grunnleggende om Java i vår Java Nybegynner diskusjon

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

• Melde seg på JavaWorlder gratis ukentlig Core Java e-post nyhetsbrev

  //www.javaworld.com/subscribe

• Du finner et vell av IT-relaterte artikler fra søsterpublikasjonene våre på .net

Denne historien, "Hashtables" ble opprinnelig utgitt av JavaWorld.