Hashtables

2002. gada 21. jūnijs

J: Kas objekta klasē Object tiek izmantots kā atslēga, kas man ir jāpārzina Object klasē un kāpēc?

A: Kad izveidojat pats savu galveno objektu lietošanai a Hashtable, jums ir jāatskaita Object.equals () un Object.hashCode () metodes kopš Hashtable izmanto atslēgu kombināciju hashCode () un vienāds () metodes, lai ātri saglabātu un izgūtu ierakstus. Tas ir arī vispārējs noteikums, kas tiek ignorēts vienāds (), jūs vienmēr ignorējat hashCode ().

Vairāk par to, kāpēc

Nedaudz padziļināts skaidrojums palīdzēs jums saprast Hashtableglabāšanas un izguves mehānisms. A Hashtable iekšēji satur segmentus, kuros tā saglabā atslēgu / vērtību pārus. The Hashtable izmanto atslēgas jaukšanas kodu, lai noteiktu, kurā segmentā atslēgu / vērtību pārim vajadzētu kartēt.

1. attēlā parādīts a Hashtable un tās spaiņi. Kad nodosiet atslēgu / vērtību Hashtable, tā vaicā atslēgas hashcode. The Hashtable izmanto šo kodu, lai noteiktu grupu, kurā ievietot atslēgu / vērtību. Tā, piemēram, ja hashcode ir vienāds ar nulli, Hashtable vērtību ievieto spainī 0. Tāpat, ja hashcode ir divi, Hashtable ievieto vērtību 2. segmentā. (Šis ir vienkāršots piemērs; Hashtable vispirms iemasēs hashcode, tāpēc Hashtable nemēģina ievietot vērtību ārpus grupas.)

Izmantojot šādā veidā hashcode, Hashtable var arī ātri noteikt, kurā segmentā tā ir ievietojusi vērtību, mēģinot to izgūt.

Hashcodes tomēr attēlo tikai pusi no attēla. Hashcode tikai norāda Hashtable kurā spainī nomest atslēgu / vērtību. Dažreiz tomēr vairāki objekti var kartēt uz vienu un to pašu grupu, notikumu, kas pazīstams kā a sadursme. Java valodā Hashtable reaģē uz sadursmi, vienā spainī ievietojot vairākas vērtības (citas realizācijas sadursmes var apstrādāt atšķirīgi). 2. attēlā parādīts, kas a Hashtable varētu izskatīties pēc dažām sadursmēm.

Tagad iedomājieties, ka zvanāt gūt() ar atslēgu, kas kartē uz Bucket 0. The Hashtable tagad jums būs jāveic secīga meklēšana, izmantojot atslēgu / vērtību pārus 0 kopā, lai atrastu jūsu pieprasīto vērtību. Lai veiktu šo meklēšanu, Hashtable veic šādas darbības:

1. Vaicājiet atslēgas hashcode
2. Iegūstiet atslēgas / vērtību sarakstu, kas atrodas segmentā, kuru piešķir hashcode
3. Skenējiet katru ierakstu secīgi, līdz tiek ievadīts atslēga, kas ir vienāda ar atslēgu gūt() ir atrasts

Gara atbilde uz īsu jautājumu, kuru es zinu, bet tas pasliktinās. Pareizi ignorē vienāds () un hashCode () ir neaktīvs vingrinājums. Jums jāpievērš īpaša piesardzība, lai garantētu abas metodes.

Īstenojot vienādu ()

Saskaņā ar vienāds () Javadoc metodei jāatbilst šādiem noteikumiem:

" vienāds () metode ievieš ekvivalences saistību:

• Tas ir refleksīvs: jebkurai atsauces vērtībai x, x. vienāds (x) vajadzētu atgriezties patiesībā
• Tas ir simetrisks: visām atsauces vērtībām x un y x. vienāds ar (y) jāatgriežas patiesi tikai tad, ja y. vienāds ar (x) atgriež patiesu
• Tas ir tranzitīvs: jebkurām atsauces vērtībām x, y un z, ja x. vienāds ar (y) atgriež patieso un y. vienāds ar (z) atgriež patiesu x. vienāds (z) vajadzētu atgriezties patiesībā
• Tā ir konsekventa: jebkurām atsauces vērtībām x un y ir vairākas reizes x. vienāds ar (y) konsekventi atgriezt patiesu vai konsekventi atgriezt nepatiesu, ja vien netiek mainīta informācija, kas tiek izmantota vienādos salīdzinājumos ar objektu
• Jebkurai nulles atsauces vērtībai x, x. vienāds (null) vajadzētu atgriezties nepatiesa "

In Efektīva Java, Džošua Blohs piedāvā piecu posmu recepti, kā uzrakstīt efektīvu vienāds () metodi. Lūk, recepte koda formā:

publiskā klase EffectiveEquals {private int valueA; privātā int vērtībaB; . . . publiskais būla skaitlis ir vienāds (Object o) {if (this == o) {// 1. darbība: veiciet == testa atgriešanās taisnība; } if (! (o EffectiveEquals instance)) {// 2. solis: Pārbaudes atgriešanās gadījums false; } EfektīvieEquals ee = (EfektīvieEquals) o; // 3. solis: Lieto arguments // 4. solis: Pārbaudiet, vai katram nozīmīgajam laukam tie ir vienādi pirmā atgriešanās ee.valueA == vērtībaA && ee.valueB == vērtībaB; }. . . } 

Piezīme: Kopš tā laika jums nav jāveic nulles pārbaude nulles EffectiveEquals gadījums novērtēs nepatiesu.

Visbeidzot, veicot 5. darbību, atgriezieties pie vienāds ()līgumu un pajautājiet sev, vai vienāds () metode ir refleksīva, simetriska un tranzitīva. Ja nē, salabojiet!

Par hashCode () ieviešanu

Priekš hashCode ()Javadoc saka par galveno līgumu:

• "Ikreiz, kad Java lietojumprogrammas izpildes laikā tas tiek izsaukts uz to pašu objektu vairāk nekā vienu reizi, hashCode () Metodei konsekventi jāatgriež viens un tas pats vesels skaitlis, ja vien netiek mainīta informācija, kas tiek izmantota vienādos salīdzinājumos ar objektu. Šis vesels skaitlis nav jāsaglabā nemainīgs no vienas lietojumprogrammas izpildes uz citu tās pašas lietojumprogrammas izpildi.
• Ja divi objekti ir vienādi saskaņā ar vienāds (objekts) metodi, pēc tam izsaucot hashCode () metode katram no diviem objektiem rada tādu pašu vesela skaitļa rezultātu.
• Tas nav nepieciešams, ja divi objekti ir nevienlīdzīgi saskaņā ar ir vienāds (java.lang.Object metodi, pēc tam izsaucot hashCode () metode katram no diviem objektiem rada atšķirīgus veselā skaitļa rezultātus. Tomēr programmētājam ir jāapzinās, ka atšķirīgu veselu skaitļu rezultātu iegūšana nevienlīdzīgiem objektiem var uzlabot hashtable darbību. "

Pareiza darba radīšana hashCode () metode izrādās grūta; tas kļūst vēl grūtāk, ja attiecīgais objekts nav maināms. Konkrētam objektam daudzējādā ziņā var aprēķināt hashcode. Visefektīvākā metode balstās uz objekta laukiem. Turklāt jūs varat apvienot šīs vērtības dažādos veidos. Šeit ir divas populāras pieejas:

• Jūs varat pārvērst objekta laukus virknē, sasaistīt virknes un atgriezt iegūto hashcode
• Jūs varat pievienot katra lauka jaukšanas kodu un atgriezt rezultātu

Lai gan pastāv citas, rūpīgākas pieejas, abas iepriekš minētās pieejas ir visvieglāk saprotamas un īstenojamas.

Tonijs Sintess ir neatkarīgs konsultants un First Class Consulting, konsultāciju firmas dibinātājs, kas specializējas dažādu uzņēmumu sistēmu un apmācības mazināšanā. Ārpus pirmās klases konsultācijām Tonijs ir aktīvs ārštata rakstnieks, kā arī grāmatas Sams autors uz objektorientētu programmēšanu 21 dienas laikā autors (Sams, 2001; ISBN: 0672321092).

Uzziniet vairāk par šo tēmu

• Lai uzzinātu Hashtable Javadoc, dodieties uz

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

• Vipana Singlas "Vienādo () un hashCode () ieviešana" sniedz padziļinātu diskusiju par vienādu () un hashCode () metožu ignorēšanu

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

• Objekts.vienāds () 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 ()

• Džošua Bloka Efektīva Java programmēšanas valodas rokasgrāmata (Addison Wesley Professional, 2001; ISBN0201310058), dodieties uz

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

• Lai iegūtu vairāk rakstu par Java klasēm un metodēm, pārlūkojiet API sadaļa JavaWorld 's Aktuālais rādītājs

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

• Vēlas vairāk? Skatīt Java jautājumi un atbildes rādītāja lapa pilnam jautājumu un atbilžu katalogam

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

• Lai iegūtu vairāk nekā 100 ieskatīgus Java padomus no labākajiem biznesa prātiem, apmeklējiet vietni JavaWorld 's Java padomi rādītāja lapa

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

• Uzziniet Java pamatus mūsu vietnē Java iesācējs diskusija

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

• Pierakstieties JavaWorldkatru nedēļu ir bezmaksas Java kodols e-pasta biļetens

  //www.javaworld.com/subscribe

• Jūs atradīsit daudz ar IT saistītu rakstu no mūsu māsas publikācijām vietnē .net

Šo stāstu "Hashtables" sākotnēji publicēja JavaWorld.