streamalism.org

1. Oversigt

Hashing er et grundlæggende begreb inden for datalogi.

I Java står effektive hashingalgoritmer bag nogle af de mest populære samlinger, vi har til rådighed - som f.eks HashMap (for et dybtgående kig på HashMap, er du velkommen til at tjekke denne artikel) og HashSet.

I denne artikel vil vi fokusere på hvordan hashCode () fungerer, hvordan det spiller i samlinger, og hvordan man implementerer det korrekt.

2. Anvendelse af hashCode () i datastrukturer

De enkleste operationer på samlinger kan være ineffektive i visse situationer.

For eksempel udløser dette en lineær søgning, der er meget ineffektiv for lister med enorme størrelser:

Listeord = Arrays.asList ("Velkommen", "til", "Baeldung"); hvis (ord. indeholder ("Baeldung")) {System.out.println ("Baeldung er på listen"); }

Java leverer en række datastrukturer til specifikt at håndtere dette problem - for eksempel flere Kort interface implementeringer er hash-tabeller.

Når du bruger et hashbord, disse samlinger beregner hashværdien for en given nøgle ved hjælp af hashCode () metode og bruge denne værdi internt til at gemme dataene - så adgangsoperationer er meget mere effektive.

3. Forstå hvordan hashCode () Arbejder

Kort fortalt, hashCode () returnerer en heltalværdi, genereret af en hashingalgoritme.

Objekter, der er lige (i henhold til deres lige med()) skal returnere den samme hash-kode. Det er ikke nødvendigt, at forskellige objekter returnerer forskellige hash-koder.

Den generelle kontrakt for hashCode () hedder:

• Hver gang det påberåbes det samme objekt mere end én gang under en udførelse af en Java-applikation, hashCode () skal konsekvent returnere den samme værdi, forudsat at ingen information, der bruges i lig sammenligninger af objektet, ændres. Denne værdi behøver ikke at være konsistent fra en udførelse af en applikation til en anden udførelse af den samme applikation

• Hvis to objekter er ens i henhold til er lig med (Objekt) metode og derefter kalde hashCode () metode på hvert af de to objekter skal producere den samme værdi

• Det kræves ikke, at hvis to objekter er ulige i henhold til er lig med (java.lang.Object) metode og derefter kalde hashCode metode på hvert af de to objekter skal producere forskellige heltalresultater. Udviklere skal dog være opmærksomme på, at produktion af forskellige heltalresultater til ulige objekter forbedrer ydeevnen for hash-tabeller

”Så meget som det med rimelighed er praktisk, hashCode () metode defineret efter klasse Objekt returnerer forskellige heltal for forskellige objekter. (Dette implementeres typisk ved at konvertere objektets interne adresse til et heltal, men denne implementeringsteknik kræves ikke af JavaTM-programmeringssproget.) ”

4. En naiv hashCode () Implementering

Det er faktisk ret ligetil at have en naiv hashCode () implementering, der fuldt ud overholder ovenstående kontrakt.

For at demonstrere dette skal vi definere en prøve Bruger klasse, der tilsidesætter metodens standardimplementering:

offentlig klasse bruger {privat lang id; privat strengnavn; privat streng e-mail; // standard getters / setters / constructors @Override public int hashCode () {return 1; } @ Override offentlige boolske lig (Objekt o) {hvis (dette == o) returnerer sandt; hvis (o == null) returnerer false; hvis (this.getClass ()! = o.getClass ()) returnerer false; Brugerbruger = (Bruger) o; return id == user.id && (name.equals (user.name) && email.equals (user.email)); } // getters og settere her}

Det Bruger klasse giver brugerdefinerede implementeringer for begge lige med() og hashCode () der fuldt ud overholder de respektive kontrakter. Endnu mere er der intet ulovligt med at have hashCode () returnerer enhver fast værdi.

Imidlertid nedbryder denne implementering funktionaliteten af ​​hash-tabeller til stort set nul, da hvert objekt vil blive gemt i den samme, enkelt spand.

I denne sammenhæng udføres en hash-tabelopslag lineært og giver os ingen reel fordel - mere om dette i afsnit 7.

5. Forbedring af hashCode () Implementering

Lad os forbedre den aktuelle strøm hashCode () implementering ved at inkludere alle felter i Bruger klasse, så den kan producere forskellige resultater for ulige objekter:

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

Denne grundlæggende hashingalgoritme er definitivt meget bedre end den forrige, da den beregner objektets hash-kode ved blot at multiplicere hash-koder for navn og e-mail felter og id.

Generelt kan vi sige, at dette er rimeligt hashCode () implementering, så længe vi beholder lige med() implementering i overensstemmelse med det.

6. Standard hashCode () Implementeringer

Jo bedre hashing-algoritmen, som vi bruger til at beregne hash-koder, jo bedre bliver ydeevnen for hash-tabeller.

Lad os se på en "standard" implementering, der bruger to primtal for at tilføje endnu mere unikhed 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 + (e-mail == null? 0: email.hashCode ()); retur hash; }

Mens det er vigtigt at forstå de roller, der hashCode () og lige med() metoder spiller, behøver vi ikke implementere dem fra bunden hver gang, da de fleste IDE'er kan generere brugerdefinerede hashCode () og lige med() implementeringer og siden Java 7, fik vi en Objects.hash () hjælpemetode til behagelig hashing:

Objects.hash (navn, e-mail)

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 producerer denne:

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

Ud over ovenstående IDE-baserede hashCode () implementeringer, er det også muligt automatisk at generere en effektiv implementering, for eksempel ved hjælp af Lombok. I dette tilfælde skal lombok-maven-afhængigheden føjes til pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

Det er nu nok til at kommentere Bruger klasse med @EqualsAndHashCode:

@EqualsAndHashCode offentlig klasse bruger {// felter og metoder her}

Tilsvarende, hvis vi vil have Apache Commons Lang's HashCodeBuilder klasse til at generere en hashCode () implementering for os, commons-lang Maven afhængighed skal inkluderes i pom-filen:

 commons-lang commons-lang 2.6 

Og hashCode () kan implementeres således:

public class User {public int hashCode () {returner ny HashCodeBuilder (17, 37). tilføj (id). tilføj (navn). tilføj (e-mail). toHashCode (); }}

Generelt er der ingen universel opskrift at holde sig til, når det kommer til implementering hashCode (). Vi anbefaler stærkt at læse Joshua Blochs effektive Java, som giver en liste over grundige retningslinjer til implementering af effektive hashingalgoritmer.

Hvad der kan bemærkes her er, at alle disse implementeringer bruger nummer 31 i en eller anden form - det er fordi 31 har en dejlig egenskab - dens multiplikation kan erstattes af et bitvis skift, der er hurtigere end standardmultiplikationen:

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

7. Håndtering af hasjkollisioner

Den iboende opførsel af hash-tabeller hæver et relevant aspekt af disse datastrukturer: selv med en effektiv hashingalgoritme kan to eller flere objekter have den samme hash-kode, selvom de er ulige. Så deres hash-koder vil pege på den samme spand, selvom de ville have forskellige hash-tabelnøgler.

Denne situation er almindeligt kendt som en hashkollision, og der findes forskellige metoder til håndtering af den, hvor hver enkelt har deres fordele og ulemper. Java'er HashMap bruger den separate kædemetode til håndtering af kollisioner:

”Når to eller flere objekter peger på den samme spand, gemmes de simpelthen på en sammenkædet liste. I et sådant tilfælde er hash-tabellen en matrix af sammenkædede lister, og hvert objekt med den samme hash føjes til den sammenkædede liste ved bucket-indekset i arrayet.

I værste fald ville flere skovle have en linket liste bundet til sig, og hentning af et objekt på listen ville blive udført lineært.”

Metoder til kollision med hasj viser i en nøddeskal, hvorfor det er så vigtigt at implementere hashCode () effektivt.

Java 8 bragte en interessant forbedring til HashMap implementering - hvis en skovstørrelse overskrider den bestemte tærskel, erstattes den linkede liste med et trækort. Dette gør det muligt at opnå O (logn) se op i stedet for pessimistisk På).

8. Oprettelse af en trivial applikation

At teste funktionaliteten af ​​en standard hashCode () implementering, lad os oprette en simpel Java-applikation, der tilføjer nogle Bruger genstande mod en HashMap og bruger SLF4J til at logge en besked til konsollen hver gang metoden kaldes.

Her er prøveapplikationens startpunkt:

public class Application {public static void main (String [] args) {Map users = new HashMap (); Brugerbruger1 = ny bruger (1L, "John", "[e-mailbeskyttet]"); Brugerbruger2 = ny bruger (2L, "Jennifer", "[e-mailbeskyttet]"); Brugerbruger3 = ny bruger (3L, "Mary", "[e-mailbeskyttet]"); users.put (bruger1, bruger1); users.put (bruger2, bruger2); users.put (user3, user3); hvis (users.containsKey (user1)) {System.out.print ("Bruger fundet i samlingen"); }}} 

Og det er dette hashCode () implementering:

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 () kaldet - Beregnet hash:" + hash); retur hash; }}

Den eneste detalje, der er værd at understrege her, er at hver gang et objekt gemmes på hash-kortet og kontrolleres med indeholderKey () metode, hashCode () påberåbes, og den beregnede hash-kode udskrives til konsollen:

[main] INFO com.baeldung.entities.User - hashCode () kaldet - Beregnet hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode () kaldet - Computed hash: -282948472 [main] INFO com.baeldung .entities.User - hashCode () kaldet - Beregnet hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode () kaldet - Computert hash: 1255477819 Bruger fundet i samlingen

9. Konklusion

Det er klart at producere effektiv hashCode () implementeringer kræver ofte en blanding af et par matematiske begreber (dvs. primære og vilkårlige tal), logiske og grundlæggende matematiske operationer.

Uanset hvad er det fuldt ud muligt at implementere hashCode () effektivt uden at bruge disse teknikker overhovedet, så længe vi sørger for, at hashing-algoritmen producerer forskellige hash-koder for ulige objekter og er i overensstemmelse med implementeringen af lige med().

Som altid er alle kodeeksemplerne vist i denne artikel tilgængelige på GitHub.