Ohjelmointi

Hashtables

21. kesäkuuta 2002

K: Kun käytän objektia avaimena Hashtableissa, mitä Object-luokassa minun on ohitettava ja miksi?

A: Kun luot oman avainkohteen käytettäväksi a Hashtable, sinun on ohitettava Object.equals () ja Object.hashCode () menetelmiä Hashtable käyttää avaimen yhdistelmää hash koodin() ja on yhtä suuri () tapoja tallentaa ja hakea merkinnät nopeasti. Se on myös yleinen sääntö, joka ohitettaessa on yhtä suuri (), ohitat aina hash koodin().

Lisää miksi

Hieman syvällisempi selitys auttaa sinua ymmärtämään Hashtablemekanismi varastointiin ja hakemiseen. A Hashtable sisältää sisäisesti ämpärejä, joihin se tallentaa avain / arvo-parit. Hashtable käyttää avaimen hashcode-koodia määrittääkseen, mihin ryhmään avain / arvo-pari tulisi yhdistää.

Kuva 1 esittää a Hashtable ja sen kauhat. Kun välität avaimen / arvon Hashtable, se kysyy avaimen hashcode-koodin. Hashtable käyttää tätä koodia määrittäessään ryhmän, johon avain / arvo sijoitetaan. Joten esimerkiksi, jos hashcode on nolla, Hashtable sijoittaa arvon kauhaan 0. Vastaavasti, jos hashcode on kaksi, Hashtable sijoittaa arvon kauhaan 2. (Tämä on yksinkertaistettu esimerkki; Hashtable hieroo ensin hashcoden, joten Hashtable ei yritä lisätä arvoa ämpärin ulkopuolelle.)

Käyttämällä hajakoodia tällä tavalla, Hashtable voi myös nopeasti selvittää, mihin ryhmään se on sijoittanut arvon, kun yrität noutaa sitä.

Hashcodes edustavat kuitenkin vain puolta kuvasta. Hajakoodi kertoo vain Hashtable mihin ämpäriin pudottaa avain / arvo. Joskus kuitenkin useita objekteja voi kartoittaa samaan ryhmään, tapahtumaan, joka tunnetaan nimellä törmäys. Java-sovelluksessa Hashtable reagoi törmäykseen sijoittamalla useita arvoja samaan ämpäriin (muut toteutukset voivat käsitellä törmäyksiä eri tavalla). Kuva 2 näyttää mitä a Hashtable saattaa näyttää muutaman törmäyksen jälkeen.

Kuvittele nyt, että soitat saada() avaimella, joka kartoitetaan kauhaan 0 Hashtable on nyt suoritettava peräkkäinen haku hakusanan 0 avain / arvo-parien kautta pyydetyn arvon löytämiseksi. Suorita tämä haku, Hashtable suorittaa seuraavat vaiheet:

  1. Kysele avaimen hashcode
  2. Nouda luettelo avaimista / arvoista, jotka ovat hajautuskoodin antamassa ämpärissä
  3. Skannaa kaikki merkinnät peräkkäin, kunnes avain, joka on sama kuin avain, johon syötetään saada() on löydetty

Pitkä vastaus lyhyeen kysymykseen, jonka tiedän, mutta se pahenee. Oikein korvaava on yhtä suuri () ja hash koodin() on ei-triviaalinen harjoitus. Sinun on oltava erittäin varovainen taataksesi molempien menetelmien sopimukset.

Yhtälön () toteuttamisesta

Mukaan on yhtä suuri () Javadocin mukaan menetelmän on oltava seuraavien sääntöjen mukainen:

" on yhtä suuri () menetelmä toteuttaa vastaavuussuhteen:
  • Se on refleksiivinen: Kaikille vertailuarvoille x x. on yhtä suuri (x) pitäisi palata totta
  • Se on symmetrinen: Kaikille vertailuarvoille x ja y, x. yhtä suuri (y) pitäisi palata totta vain ja vain y. yhtäläiset (x) palauttaa arvon tosi
  • Se on transitiivinen: Kaikille viitearvoille x, y ja z, jos x. yhtä suuri (y) palauttaa true ja y. yhtäläiset (z) palauttaa totta x. on yhtä suuri (z) pitäisi palata totta
  • Se on johdonmukainen: Kaikille vertailuarvoille x ja y, useita kutsuja x. yhtä suuri (y) palauttaa jatkuvasti tosi tai johdonmukaisesti väärän, edellyttäen, ettei yhtään vertailussa käytettyä tietoa objektista muuteta
  • Kaikille ei-nolla-viitearvoille x x. yhtäläiset (null) pitäisi palauttaa väärä "

Sisään Tehokas Java, Joshua Bloch tarjoaa viisivaiheisen reseptin tehokkuuden kirjoittamiseen on yhtä suuri () menetelmä. Tässä resepti koodimuodossa:

julkinen luokka EffectiveEquals {private int valueA; yksityinen int-arvoB; . . . public boolean on yhtä suuri (Object o) {if (this == o) {// Vaihe 1: Suorita == test return return true; } if (! (o instanceof EffectiveEquals)) {// Vaihe 2: Tarkastuksen palautus false false; } TehollinenEquals ee = (EffectiveEquals) o; // Vaihe 3: Cast-argumentti // Vaihe 4: Tarkista jokaisen tärkeän kentän kohdalla, ovatko ne yhtä suuria // Primitiivien kohdalla == // Objektien tapauksessa käytä equals (), mutta muista myös // käsitellä null-tapausta ensimmäinen paluu ee.arvoA == arvoA && ee.arvoB == arvoB; }. . . } 

merkintä: Sinun ei tarvitse suorittaa tyhjää tarkistusta tyhjä EffectiveEquals-esimerkki arvioi vääräksi.

Lopuksi, palaa vaiheeseen 5 on yhtä suuri ()ja kysy itseltäsi, onko on yhtä suuri () menetelmä on refleksiivinen, symmetrinen ja transitiivinen. Jos ei, korjaa se!

HashCode () -sovelluksen käyttöönotossa

Sillä hash koodin()Yleissopimuksessa Javadoc sanoo:

  • "Aina kun sitä kutsutaan samalle objektille useammin kuin kerran Java - sovelluksen suorituksen aikana, hash koodin() method -menetelmän on johdonmukaisesti palautettava sama kokonaisluku, mikäli yhtään objektin vertailussa käytettyä tietoa ei muuteta. Tämän kokonaisluvun ei tarvitse pysyä yhdenmukaisena sovelluksen yhdestä suorituksesta toiseen saman sovelluksen suoritukseen.
  • Jos kaksi objektia on yhtä suuri on yhtä suuri (objekti) -menetelmää, soittamalla sitten hash koodin() menetelmän on tuotettava sama kokonaislukutulos.
  • Ei vaadita, että jos kaksi objektia ovat eriarvoiset on yhtä suuri (java.lang.Object -menetelmää, soittamalla sitten hash koodin() menetelmän on tuotettava erilliset kokonaislukutulokset. Ohjelmoijan tulisi kuitenkin olla tietoinen siitä, että erillisten kokonaislukutulosten tuottaminen epätasa-arvoisille kohteille voi parantaa hashtabeleiden suorituskykyä. "

Oikein toimivan toiminnan luominen hash koodin() menetelmä osoittautuu vaikeaksi; siitä tulee vielä vaikeampaa, jos kyseinen esine ei ole muuttumaton. Voit laskea hajakoodin tietylle objektille monin tavoin. Tehokkain menetelmä perustaa luvun objektin kenttiin. Lisäksi voit yhdistää nämä arvot eri tavoin. Tässä on kaksi suosittua lähestymistapaa:

  • Voit muuttaa objektin kentät merkkijonoksi, ketjuttaa merkkijonot ja palauttaa tuloksena olevan hajautuskoodin
  • Voit lisätä kunkin kentän hashcode-koodin ja palauttaa tuloksen

Muita, perusteellisempia lähestymistapoja on olemassa, mutta kaksi edellä mainittua lähestymistapaa osoittautuvat helpoimmaksi ymmärtää ja toteuttaa.

Tony Sintes on riippumaton konsultti ja perustaja First Class Consulting -yritykselle, joka on erikoistunut erilaisten yritysjärjestelmien ja koulutuksen yhdistämiseen. Ensiluokkaisen konsultoinnin ulkopuolella Tony on aktiivinen freelance-kirjailija, samoin kuin kirjan Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092) kirjoittaja.

Lisätietoja tästä aiheesta

  • Mene Hashtable Javadoc -sivulle

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

  • Vipan Singlan "Equal () ja hashCode ()" -toiminnot tarjoavat perusteellisen keskustelun yhtäläisten () ja hashCode () -menetelmien ohittamisesta

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

  • Object.quals () 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 ()

  • Joshua Blochin puolesta Tehokas Java-ohjelmointikieliopas (Addison Wesley Professional, 2001; ISBN0201310058), siirry kohtaan

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

  • Saat lisää Java-luokkia ja -menetelmiä koskevia artikkeleita selaamalla Sovellusliittymät osa JavaWorld 's Ajankohtainen hakemisto

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

  • Haluta lisää? Katso Java-kysymykset ja vastaukset hakemistosivu täydelliseen Q & A-luetteloon

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

  • Jos haluat saada yli 100 oivaltavaa Java-vinkkiä yrityksen parhailta mieliltä, ​​käy osoitteessa JavaWorld 's Java-vinkkejä hakemistosivu

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

  • Opi Java-perusteet meidän Java-aloittelija keskustelu

    //forums.idg.net/[email protected]@.ee6b804

  • Ilmottautua JavaWorldon ilmainen viikoittain Java-ydin sähköpostiuutiskirje

    //www.javaworld.com/subscribe

  • Löydät runsaasti tietotekniikkaan liittyviä artikkeleita sisarjulkaisuistamme .net

Tämän tarinan "Hashtables" julkaisi alun perin JavaWorld.