Hashtables

21. lipnja 2002

P: Kada koristim objekt kao ključ u tablici razmještaja, što u klasi Object moram nadjačati i zašto?

O: Kada stvorite svoj vlastiti objekt ključ za uporabu u Hashtable, morate poništavaju tu Object.equals()i Object.hashCode()metoda jer Hashtablekoristi kombinaciju ključ je hashCode()i equals()metoda za pohranu i dohvaćanje unosa brzo. Također je opće pravilo da kada nadjačate equals(), uvijek poništite hashCode().

Više o tome zašto

Nešto detaljnije objašnjenje pomoći će vam da razumijete Hashtablemehanizam za pohranu i pronalaženje. HashtableInterno sadrži kante u kojima se pohranjuje ključ / vrijednost parova. Na Hashtablekoristi hash broj ključ je kako bi se utvrdilo na koji kantu ključ / vrijednost par trebao mapirati.

Slika 1 prikazuje a Hashtablei njegove kante. Kada proslijedite ključ / vrijednost Hashtable, on postavlja upit hashcodeu ključa. Na Hashtablekoristi taj kod za određivanje kantu u kojoj će staviti ključ / vrijednost. Tako, na primjer, ako je hashcode jednak nuli, Hashtablevrijednost se smješta u skup 0. Isto tako, ako je hashcode dva, vrijednost se Hashtablestavlja u segment 2 (ovo je pojednostavljeni primjer; Hashtableprvo će masirati hashcode, tako da Hashtablene pokušava umetnuti vrijednost izvan segmenta.)

Koristeći hashcode na ovaj način, limenka Hashtabletakođer može brzo odrediti u koji je segment smjestio vrijednost kada je pokušate dohvatiti.

Hash kodovi, međutim, predstavljaju samo polovicu slike. Hashcode samo govori Hashtableu koji će segment izbaciti ključ / vrijednost. Međutim, ponekad se više objekata može preslikati u isti segment, događaj poznat kao sudar. U Javi Hashtableodgovor na sudar postavlja postavljanjem više vrijednosti u isti segment (druge implementacije mogu sudariti različito). Slika 2 prikazuje kako bi Hashtablemogao izgledati nakon nekoliko sudara.

Sad zamislite da zovete get()ključem koji se preslikava na segment 0. Sada Hashtableće trebati izvršiti sekvencijalno pretraživanje kroz parove ključ / vrijednost u segmentu 0 kako bi pronašli vašu traženu vrijednost. Da bi izveo ovo traženje, Hashtableizvršavaju se sljedeći koraci:

  1. Upitajte hashcode ključa
  2. Dohvatite popis ključeva / vrijednosti koji se nalaze u segmentu danom hashcodeom
  3. Skenirajte kroz svaki unos uzastopno dok get()se ne pronađe ključ jednak ključu u koji je proslijeđen

Dug odgovor na kratko pitanje znam, ali postaje još gori. Pravilno nadjačavanje equals()i hashCode()netrivijalna je vježba. Morate biti izuzetno oprezni kako biste zajamčili ugovore obje metode.

O provedbi jednakog ()

Prema equals()Javadocu, metoda mora biti u skladu sa sljedećim pravilima:

" equals()Metoda implementira odnos ekvivalencije:
  • Refleksivan je: Za bilo koju referentnu vrijednost x x.equals(x)treba vratiti true
  • Simetrično je: Za sve referentne vrijednosti x i y, x.equals(y)treba vratiti true ako i samo ako y.equals(x)vraća true
  • Prijelazno je: Za sve referentne vrijednosti x, y i z, ako x.equals(y)vraća true i y.equals(z)vraća true, tada x.equals(z)bi trebalo vratiti true
  • Dosljedan je: Za bilo koje referentne vrijednosti x i y, višestruki pozivi x.equals(y)dosljedno vraćaju true ili dosljedno vraćaju false, pod uvjetom da se ne mijenjaju podaci korišteni u jednakim usporedbama na objektu
  • Za bilo koju referentnu vrijednost koja nije null x, x.equals(null)treba vratiti false "

U Effective Java Joshua Bloch nudi recept u pet koraka za pisanje učinkovite equals()metode. Evo recepta u obliku koda:

javna klasa EffectiveEquals {private int valueA; privatna int vrijednostB; . . . javna logička vrijednost jednako (Objekt o) {if (this == o) {// 1. korak: Izvršite == test return true; } if (! (o instanceof EffectiveEquals)) {// 2. korak: Instanca check return false; } EffectiveEquals ee = (EffectiveEquals) o; // Korak 3: Argument za emitiranje // Korak 4: Za svako važno polje provjerite jesu li jednaka // Za primitive koristite == // Za objekte koristite jednako (), ali svakako i // obradite null slučaj prvi povratak ee.valueA == valueA && ee.valueB == valueB; }. . . }

Napomena: Ne morate provesti null provjeru jer null instanceof EffectiveEqualsće vrijednost biti lažna.

Konačno, za korak 5, vratite se na equals()ugovor i zapitajte se je li equals()metoda refleksna, simetrična i prijelazna. Ako ne, popravite!

O primjeni hashCode ()

Za hashCode()opći ugovor, Javadoc kaže:

  • "Kad god se na isti objekt pozove više puta tijekom izvršavanja Java aplikacije, hashCode()metoda mora dosljedno vraćati isti cijeli broj, pod uvjetom da nije promijenjena nijedna informacija koja se koristi u jednakim usporedbama na objektu. Ova cjelobrojna vrijednost ne mora ostati dosljedna jednom izvršavanje aplikacije na drugo izvršenje iste aplikacije.
  • Ako su dva objekta jednaka prema equals(Object)metodi, tada pozivanje hashCode()metode na svakom od dva objekta mora dati isti cijeli broj.
  • Nije potrebno da ako su dva objekta nejednaka prema equals(java.lang.Objectmetodi, tada pozivanje hashCode()metode na svakom od dva objekta mora dati različite cjelovite rezultate. Međutim, programer bi trebao biti svjestan da stvaranje različitih cjelovitih rezultata za nejednake objekte može poboljšati izvedbu hashtablea. "

Stvaranje ispravne hashCode()metode rada pokazuje se teškim; postaje još teže ako predmetni predmet nije nepromjenjiv. Hashcode za izračun datog objekta možete izračunati na više načina. Najučinkovitija metoda temelji broj na poljima objekta. Štoviše, ove vrijednosti možete kombinirati na razne načine. Evo dva popularna pristupa:

  • Možete pretvoriti polja objekta u niz, spojiti nizove i vratiti rezultirajući hashcode
  • Možete dodati hashcode svakog polja i vratiti rezultat

Iako postoje drugi, temeljitiji pristupi, dva gore navedena pristupa pokazuju se najlakšima za razumijevanje i provedbu.

Tony Sintes neovisni je savjetnik i osnivač First Class Consultinga, konzultantske tvrtke koja je specijalizirana za premošćivanje različitih poslovnih sustava i obuke. Izvan prve klase savjetovanja, Tony je aktivni slobodnjak, kao i autor knjige Sams Teach Yourself Objekt-Oriented Programming za 21 dan (Sams, 2001; ISBN: 0672321092).

Saznajte više o ovoj temi

  • Za Hashtable Javadoc idite na

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

  • Vipan Singla "Implementacija jednakosti () i hashCode ()" pruža detaljnu raspravu o nadjačavanju metoda equals () i hashCode ()

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

  • The Object.equals() Javadoc

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

  • The Object.hashCode() Javadoc

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

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

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

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

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

  • Want more? See the Java Q&A index page for the full Q&A catalog

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

  • Za više od 100 uvida Java savjete iz neke od najboljih umova u poslovanju, posjet JavaWorld” s Java Savjet indeks stranica

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

  • Naučite osnove Java u našoj raspravi o početnicima Java

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

  • Prijavite se za besplatni tjedni bilten Core Java e-pošte za JavaWorld

    //www.javaworld.com/subscribe

  • Mnoštvo članaka vezanih uz IT iz naših sestrinskih publikacija pronaći ćete na .net

Ovu je priču "Hashtables" izvorno objavio JavaWorld.