streamalism.org

1. Oversikt

Hashing er et grunnleggende begrep innen informatikk.

I Java står effektive hashingalgoritmer bak noen av de mest populære samlingene vi har tilgjengelig - for eksempel HashMap (for en grundig titt på HashMap, sjekk gjerne denne artikkelen) og HashSet.

I denne artikkelen vil vi fokusere på hvordan hashCode () fungerer, hvordan det spiller inn i samlinger og hvordan du implementerer det riktig.

2. Bruk av hashCode () i datastrukturer

De enkleste operasjonene på samlinger kan være ineffektive i visse situasjoner.

For eksempel utløser dette et lineært søk som er svært ineffektivt for lister med store størrelser:

Listeord = Arrays.asList ("Velkommen", "til", "Baeldung"); if (words.contains ("Baeldung")) {System.out.println ("Baeldung er i listen"); }

Java tilbyr en rekke datastrukturer for å håndtere dette problemet spesielt - for eksempel flere Kart grensesnittimplementeringer er hash-tabeller.

Når du bruker hasjbord, disse samlingene beregner hashverdien for en gitt nøkkel ved hjelp av hashCode () metode og bruke denne verdien internt til å lagre dataene - slik at tilgangsoperasjonene blir mye mer effektive.

3. Forstå hvordan hashCode () Virker

For å si det enkelt, hashCode () returnerer en heltallverdi, generert av en hashingalgoritme.

Objekter som er like (i henhold til deres er lik()) må returnere samme hash-kode. Det er ikke nødvendig at forskjellige objekter returnerer forskjellige hash-koder.

Den generelle kontrakten til hashCode () sier:

• Hver gang det påkalles det samme objektet mer enn en gang under en Java-applikasjon, hashCode () må konsekvent returnere den samme verdien, forutsatt at ingen informasjon som brukes i lik sammenligning på objektet er endret. Denne verdien 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å produsere den samme verdien

• 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 utviklere være klar over at å produsere distinkte heltallresultater for ulik objekter forbedrer ytelsen til hash-tabeller

“Så mye som er rimelig praktisk, hashCode () metode definert av klasse Gjenstand returnerer tydelige heltall for forskjellige objekter. (Dette implementeres vanligvis ved å konvertere objektets interne adresse til et helt tall, men denne implementeringsteknikken kreves ikke av JavaTM-programmeringsspråket.) "

4. En naiv hashCode () Gjennomføring

Det er faktisk ganske greit å ha en naiv hashCode () implementering som overholder kontrakten ovenfor.

For å demonstrere dette skal vi definere et utvalg Bruker klasse som overstyrer metodens standardimplementering:

offentlig klasse bruker {privat lang id; privat strengnavn; privat streng e-post; // standard getters / setters / constructors @Override public int hashCode () {retur 1; } @Override offentlige boolske lik (Objekt o) {hvis (dette == o) returnerer sant; hvis (o == null) returnerer falsk; hvis (this.getClass ()! = o.getClass ()) returnerer false; Brukerbruker = (Bruker) o; return id == user.id && (name.equals (user.name) && email.equals (user.email)); } // getters og setters her}

De Bruker klasse gir tilpassede implementeringer for begge er lik() og hashCode () som følger de respektive avtalene. Enda mer, det er ingenting ulovlig med å ha hashCode () returnerer en fast verdi.

Imidlertid forringer denne implementeringen funksjonaliteten til hash-tabeller til i utgangspunktet null, da hvert objekt vil bli lagret i den samme, enkle bøtta.

I denne sammenheng utføres en hash-tabelloppslag lineært og gir oss ingen reell fordel - mer om dette i avsnitt 7.

5. Forbedre hashCode () Gjennomføring

La oss forbedre strømmen hashCode () implementering ved å inkludere alle felt i Bruker klasse slik at den kan gi forskjellige resultater for ulik objekter:

@Override public int hashCode () {return (int) id * name.hashCode () * email.hashCode (); }

Denne grunnleggende hashingalgoritmen er definitivt mye bedre enn den forrige, da den beregner objektets hash-kode ved å bare multiplisere hash-kodene til Navn og e-post felt og id.

Generelt sett kan vi si at dette er rimelig hashCode () implementering, så lenge vi beholder er lik() implementering i samsvar med den.

6. Standard hashCode () Implementeringer

Jo bedre hashing-algoritmen vi bruker til å beregne hash-koder, jo bedre blir ytelsen til hash-tabeller.

La oss ta en titt på en "standard" implementering som bruker to primtall for å legge til enda mer unikhet til beregnede hash-koder:

@ Override public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (navn == null? 0: name.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); retur hash; }

Selv om det er viktig å forstå rollene som hashCode () og er lik() metoder spiller, trenger vi ikke implementere dem fra bunnen av hver gang, da de fleste IDEer kan generere tilpassede hashCode () og er lik() implementeringer og siden Java 7, fikk vi en Objects.hash () verktøymetode for komfortabel hashing:

Objects.hash (navn, e-postadresse)

IntelliJ IDEA genererer følgende implementering:

@Override public int hashCode () {int result = (int) (id ^ (id >>> 32)); resultat = 31 * resultat + navn.hashCode (); resultat = 31 * resultat + email.hashCode (); returresultat; }

Og Eclipse produserer denne:

@ Override public int hashCode () {final int prime = 31; int resultat = 1; resultat = prime * resultat + ((email == null)? 0: email.hashCode ()); resultat = prim * resultat + (int) (id ^ (id >>> 32)); resultat = prime * resultat + ((navn == null)? 0: name.hashCode ()); returresultat; }

I tillegg til de ovennevnte IDE-baserte hashCode () implementeringer, er det også mulig å automatisk generere en effektiv implementering, for eksempel ved å bruke Lombok. I dette tilfellet må avhengigheten av lombok-maven legges til pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

Det er nå nok å kommentere Bruker klasse med @EqualsAndHashCode:

@EqualsAndHashCode offentlig klasse bruker {// felt og metoder her}

Tilsvarende hvis vi vil ha Apache Commons Lang HashCodeBuilder klasse for å generere en hashCode () implementering for oss, må commons-lang Maven avhengighet inkluderes i pom-filen:

 commons-lang commons-lang 2.6 

Og hashCode () kan implementeres slik:

public class User {public int hashCode () {return new HashCodeBuilder (17, 37). legg til (id). legg til (navn). legg til (e-post). toHashCode (); }}

Generelt er det ingen universell oppskrift å holde seg til når det gjelder implementering hashCode (). Vi anbefaler på det sterkeste å lese Joshua Blochs effektive Java, som gir en liste over grundige retningslinjer for implementering av effektive hashingalgoritmer.

Det som kan legges merke til her er at alle disse implementeringene bruker nummer 31 i en eller annen form - dette er fordi 31 har en fin egenskap - multiplikasjonen kan erstattes av et bitvis skift som er raskere enn standard multiplikasjon:

31 * i == (i << 5) - i

7. Håndtering av hasjkollisjoner

Den iboende oppførselen til hash-tabeller øker et relevant aspekt av disse datastrukturene: selv med en effektiv hashingalgoritme kan to eller flere objekter ha samme hash-kode, selv om de er ulik. Så deres hash-koder vil peke på samme bøtte, selv om de ville ha forskjellige hash-nøkler.

Denne situasjonen er ofte kjent som en hash-kollisjon, og det finnes forskjellige metoder for å håndtere den, og hver har sine fordeler og ulemper. Java HashMap bruker den separate kjedemetoden for håndtering av kollisjoner:

“Når to eller flere objekter peker på samme bøtte, lagres de ganske enkelt i en koblet liste. I et slikt tilfelle er hash-tabellen en matrise med lenkede lister, og hvert objekt med samme hash blir lagt til den lenkede listen ved bøtteindeksen i matrisen.

I verste fall ville flere bøtter ha en koblet liste bundet til seg, og henting av et objekt i listen ville bli utført lineært.”

Metoder for hasjkollisjon viser i et nøtteskall hvorfor det er så viktig å implementere hashCode () effektivt.

Java 8 brakte en interessant forbedring til HashMap implementering - hvis en skuffestørrelse går utover den bestemte terskelen, blir den koblede listen erstattet med et trekart. Dette gjør det mulig å oppnå O (logn) se opp i stedet for pessimistisk På).

8. Opprette en Trivial-applikasjon

Å teste funksjonaliteten til en standard hashCode () implementering, la oss lage en enkel Java-applikasjon som legger til noen Bruker gjenstander mot en HashMap og bruker SLF4J for å logge en melding til konsollen hver gang metoden kalles.

Her er prøveprogrammets inngangspunkt:

public class Application {public static void main (String [] args) {Map users = new HashMap (); User user1 = new User (1L, "John", "[email protected]"); Bruker bruker2 = ny bruker (2L, "Jennifer", "[e-postbeskyttet]"); Brukerbruker3 = ny bruker (3L, "Mary", "[e-postbeskyttet]"); users.put (bruker1, bruker1); users.put (user2, user2); users.put (user3, user3); hvis (users.containsKey (user1)) {System.out.print ("Bruker funnet i samlingen"); }}} 

Og dette er hashCode () gjennomføring:

public class User {// ... public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (navn == null? 0: name.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); logger.info ("hashCode () kalt - Beregnet hash:" + hash); retur hash; }}

Den eneste detaljene som er verdt å understreke her er at hver gang et objekt lagres i hash-kartet og sjekkes med inneholderKey () metode, hashCode () blir påkalt og den beregnede hashkoden skrives ut til konsollen:

[main] INFO com.baeldung.entities.User - hashCode () called - Computed hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode () called - Computed hash: -282948472 [main] INFO com.baeldung .entities.User - hashCode () called - Computed hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode () called - Computed hash: 1255477819 Bruker funnet i samlingen

9. Konklusjon

Det er klart at det å produsere effektivt hashCode () implementeringer krever ofte en blanding av noen få matematiske begreper, (dvs. primære og vilkårlige tall), logiske og grunnleggende matematiske operasjoner.

Uansett er det fullt mulig å implementere hashCode () effektivt uten å ty til disse teknikkene i det hele tatt, så lenge vi sørger for at hashingalgoritmen produserer forskjellige hash-koder for ulike objekter og er i samsvar med implementeringen av er lik().

Som alltid er alle kodeeksemplene vist i denne artikkelen tilgjengelig på GitHub.