Hvad er en hash-funktion i java?

Wikipedia-artiklen vil have en masse tekniske oplysninger, men et forenklet syn på hashing er noget i stil med følgende.

Forestil dig, at der er en magisk funktion, der kan give et tal til ethvert objekt. Givet det samme objekt, returnerer det altid det samme tal.

Umiddelbart nu har du en hurtig måde at teste, om to objekter er ens:Bed denne funktion om deres tal og sammenlign. Hvis de er forskellige, så er de ikke ens.

Men hvad hvis de har det samme nummer? Kan to forskellige objekter have det samme nummer?

Ja, dette er muligt i de fleste scenarier. Lad os sige, at funktionen for eksempel kun kan give tal mellem 1..10, og der er 100 forskellige objekter. Så skal nogle forskellige objekter selvfølgelig have samme nummer. Det er det, man kalder en "kollision". En "kollision" gør vores hurtige lighedstest ikke så nyttig, så så meget som muligt ønsker vi at minimere, at det sker. En god magisk funktion er en, der ville forsøge at minimere antallet af "kollisioner".

Så hvad kan du ellers gøre med dette nummer? Nå, du kan bruge det til at indeksere et array. Givet et objekt, kan du sætte det ved indekset givet af tallet fra denne magiske funktion. Dette array er i bund og grund, hvad en hashtabel er; denne magiske funktion er en hash-funktion.

En hash-funktion er en måde at skabe en kompakt repræsentation af en vilkårlig stor mængde data. I java med hashcode-metoden betyder dette på en eller anden måde at beskrive tilstanden af ​​dit objekt (uanset hvor stort det er) i en int (4 bytes). Og er normalt skrevet til at være en ret hurtig som forklaret nedenfor.

For at forenkle i hashtabeller/hashmaps fungerer hashkoden som en slags billig lig. Tag to objekter a og b af typen Foo lads siger for at finde ud af, om a.equals(b) tager 500 ms, hvor det kun tager 10 ms at beregne en (effektiv) hashkode. Så hvis vi vil vide, om a.equals(b) i stedet for at gøre det direkte først, vil vi se på hashkoderne og spørge gør a.hashCode() ==b.hashCode(). Bemærk, at dette kun vil tage 20 ms i vores eksempel.

På grund af API-definitionen af ​​hashcode ved vi, at hvis hashkoden for a ikke er lig med b, så burde a.equals(b) aldrig være sand. Så i vores ovenstående test, hvis vi ser, at hashkoderne er ulige, behøver vi aldrig at udføre den længere .equals() test, det er derfor du altid bør tilsidesætte hashCode og lig sammen .

Du kan også se referencer om at skrive "gode" eller "velfordelte" hashkoder. Dette har at gøre med det faktum, at det omvendte af de tidligere udsagn om hashcode og lig ikke er sandt. Mere specifikt betyder a.hashCode() ==b.hashCode() ikke nødvendigvis a.equals(b) Så ideen med en god hashkode er, at du reducerer sandsynligheden for a.hashCode() ==b.hashCode() når a.equals(b) er falsk. Du har måske set dette omtalt som en kollision af en hash-funktion.

Tilbage til hashmaps/tabeller. Disse er baseret på nøgle/værdi-par. Så når du tilføjer eller henter en værdi, giver du en nøgle. Så den første ting, kortet skal gøre, er at lede efter nøglen, hvilket betyder at finde noget, der .equals() den nøgle, du giver. Men som vi diskuterede ovenfor, kan .equals() være utrolig langsom, hvilket betyder, at sammenligninger kan fremskyndes kraftigt ved først at tjekke hashkoder. Siden når hashkoderne er godt fordelt, bør du hurtigt vide, hvornår x helt sikkert er !=y.

Ud over sammenligningen bruger hashmaps/tabeller faktisk hashkoderne til at organisere deres interne lagring af dataene, men jeg tror, ​​det er uden for rækkevidden af, hvad du søger at forstå på dette tidspunkt.

HASH-FUNKTION:- En hash-funktion tager en gruppe af tegn (kaldet en nøgle) og knytter den til en værdi af en bestemt længde (kaldet en hash-værdi eller hash). Hashværdien er repræsentativ for den oprindelige streng af tegn, men er normalt mindre end originalen. Hashing udføres for at indeksere og lokalisere elementer i databaser, fordi det er lettere at finde den kortere hashværdi end den længere streng. Hashing bruges også til kryptering. Dette udtryk er også kendt som en hashingalgoritme eller meddelelsessammenslutningsfunktion.

HASH MAP:- HashMap er en samlingsklasse, der er designet til at gemme elementer som nøgleværdi-par. Kort giver en måde at slå én ting op baseret på værdien af ​​en anden.

En opslagstabel, der er designet til effektivt at gemme ikke-sammenhængende nøgler (kontonumre, varenumre osv.), som kan have store huller i deres alfabetiske eller numeriske sekvenser.

HASH-TABEL:- Hash-tabeller oprettes med en algoritme, der gemmer nøglerne i hash-buckets, som indeholder nøgleværdi-par. Da forskellige nøgler kan hash til den samme bucket, er målet med hash-tabeldesign at sprede nøgleværdi-parrene jævnt ud, idet hver bucket indeholder så få nøgleværdi-par som muligt. Når en vare slås op, hashes dens nøgle for at finde den passende bucket, og bucket sammenlignes derefter for at finde det rigtige nøgle-værdi-par.