streamalism.org

1. Overzicht

Hashing is een fundamenteel concept van informatica.

In Java staan ​​efficiënte hash-algoritmen achter enkele van de meest populaire collecties die we beschikbaar hebben - zoals de Hash kaart (voor een diepgaande blik op Hash kaart, voel je vrij om dit artikel te bekijken) en de HashSet.

In dit artikel zullen we ons concentreren op hoe hashCode () werkt, hoe het in collecties speelt en hoe het correct kan worden geïmplementeerd.

2. Gebruik van hashCode () in gegevensstructuren

De eenvoudigste bewerkingen op verzamelingen kunnen in bepaalde situaties inefficiënt zijn.

Dit activeert bijvoorbeeld een lineaire zoekopdracht die zeer ineffectief is voor lijsten met grote afmetingen:

Lijstwoorden = Arrays.asList ("Welkom", "naar", "Baeldung"); if (words.contains ("Baeldung")) {System.out.println ("Baeldung staat in de lijst"); }

Java biedt een aantal datastructuren om specifiek met dit probleem om te gaan, bijvoorbeeld verschillende Kaart interface-implementaties zijn hashtabellen.

Als je een hashtabel gebruikt, deze verzamelingen berekenen de hash-waarde voor een bepaalde sleutel met behulp van de hashCode () methode en gebruik deze waarde intern om de gegevens op te slaan - zodat de toegangsbewerkingen veel efficiënter zijn.

3. Begrijpen hoe hashCode () Werken

Simpel gezegd, hashCode () geeft een geheel getal terug, gegenereerd door een hash-algoritme.

Objecten die gelijk zijn (volgens hun is gelijk aan ()) moet dezelfde hashcode retourneren. Het is niet vereist dat verschillende objecten verschillende hashcodes retourneren.

Het algemene contract van hashCode () staten:

• Telkens wanneer het meer dan eens op hetzelfde object wordt aangeroepen tijdens het uitvoeren van een Java-applicatie, hashCode () moet consistent dezelfde waarde retourneren, op voorwaarde dat er geen informatie wordt gewijzigd die wordt gebruikt in gelijken-vergelijkingen voor het object. Deze waarde hoeft niet consistent te blijven van de ene uitvoering van een applicatie naar de andere uitvoering van dezelfde applicatie

• Als twee objecten gelijk zijn volgens de is gelijk aan (Object) methode en vervolgens de hashCode () methode op elk van de twee objecten moet dezelfde waarde opleveren

• Het is niet vereist dat als twee objecten ongelijk zijn volgens de is gelijk aan (java.lang.Object) methode, en vervolgens de hashCode methode voor elk van de twee objecten moet verschillende resultaten met gehele getallen opleveren. Ontwikkelaars moeten zich er echter van bewust zijn dat het produceren van verschillende integer-resultaten voor ongelijke objecten de prestaties van hashtabellen verbetert

“Zoveel als redelijk praktisch is, de hashCode () methode gedefinieerd door klasse Voorwerp retourneert unieke gehele getallen voor verschillende objecten. (Dit wordt meestal geïmplementeerd door het interne adres van het object om te zetten in een geheel getal, maar deze implementatietechniek is niet vereist voor de programmeertaal JavaTM.) "

4. Een naïef hashCode () Implementatie

Het is eigenlijk vrij eenvoudig om naïef te zijn hashCode () uitvoering die volledig in overeenstemming is met het bovenstaande contract.

Om dit aan te tonen, gaan we een voorbeeld definiëren Gebruiker klasse die de standaardimplementatie van de methode overschrijft:

openbare klasse Gebruiker {lange privé-ID; private String naam; privé String-e-mail; // standaard getters / setters / constructors @Override public int hashCode () {return 1; } @Override public boolean equals (Object o) {if (this == o) return true; if (o == null) return false; if (this.getClass ()! = o.getClass ()) return false; Gebruiker gebruiker = (Gebruiker) o; return id == user.id && (name.equals (user.name) && email.equals (user.email)); } // getters en setters hier}

De Gebruiker class biedt aangepaste implementaties voor beide is gelijk aan () en hashCode () die volledig voldoen aan de respectievelijke contracten. Sterker nog, er is niets onwettigs aan het hebben hashCode () het retourneren van een vaste waarde.

Deze implementatie degradeert echter de functionaliteit van hashtabellen tot in wezen nul, aangezien elk object in dezelfde, enkele bucket zou worden opgeslagen.

In deze context wordt het opzoeken van een hashtabel lineair uitgevoerd en levert dit ons geen echt voordeel op - meer hierover in sectie 7.

5. Verbetering van het hashCode () Implementatie

Laten we de stroming een beetje verbeteren hashCode () implementatie door alle velden van de Gebruiker klasse zodat het verschillende resultaten kan produceren voor ongelijke objecten:

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

Dit basale hash-algoritme is beslist veel beter dan het vorige, omdat het de hashcode van het object berekent door de hashcodes van de naam en e-mail velden en de ID kaart.

In algemene termen kunnen we zeggen dat dit redelijk is hashCode () implementatie, zolang we de is gelijk aan () implementatie consistent ermee.

6. Standaard hashCode () Implementaties

Hoe beter het hash-algoritme dat we gebruiken om hash-codes te berekenen, des te beter zullen de prestaties van hashtabellen zijn.

Laten we eens kijken naar een "standaard" -implementatie die twee priemgetallen gebruikt om nog meer uniekheid toe te voegen aan berekende hashcodes:

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

Hoewel het essentieel is om de rollen te begrijpen hashCode () en is gelijk aan () methodes spelen, hoeven we ze niet elke keer vanaf nul te implementeren, aangezien de meeste IDE's custom kunnen genereren hashCode () en is gelijk aan () implementaties en sinds Java 7 hebben we een Objects.hash () utility-methode voor comfortabel hashen:

Objects.hash (naam, e-mail)

IntelliJ IDEA genereert de volgende implementatie:

@Override public int hashCode () {int resultaat = (int) (id ^ (id >>> 32)); resultaat = 31 * resultaat + naam.hashCode (); resultaat = 31 * resultaat + email.hashCode (); resultaat teruggeven; }

En Eclipse produceert deze:

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

Naast de bovenstaande IDE-gebaseerde hashCode () implementaties is het ook mogelijk om automatisch een efficiënte implementatie te genereren, bijvoorbeeld met Lombok. In dit geval moet de afhankelijkheid van lombok-maven worden toegevoegd pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

Het is nu voldoende om de Gebruiker les met @EqualsAndHashCode:

@EqualsAndHashCode openbare klasse Gebruiker {// velden en methoden hier}

Evenzo, als we Apache Commons Lang's willen HashCodeBuilder class om een hashCode () implementatie voor ons, moet de commons-lang Maven-afhankelijkheid worden opgenomen in het pom-bestand:

 commons-lang commons-lang 2.6 

En hashCode () kan als volgt worden geïmplementeerd:

openbare klasse Gebruiker {public int hashCode () {retourneer nieuwe HashCodeBuilder (17, 37). toevoegen (id). voeg (naam) toe. append (e-mail). toHashCode (); }}

Over het algemeen is er geen universeel recept om aan vast te houden als het gaat om implementatie hashCode (). We raden ten zeerste aan om Joshua Bloch's Effective Java te lezen, die een lijst met grondige richtlijnen biedt voor het implementeren van efficiënte hash-algoritmen.

Wat hier kan worden opgemerkt, is dat al die implementaties nummer 31 in een of andere vorm gebruiken - dit komt omdat 31 een mooie eigenschap heeft - de vermenigvuldiging kan worden vervangen door een bitsgewijze verschuiving die sneller is dan de standaardvermenigvuldiging:

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

7. Hash-botsingen afhandelen

Het intrinsieke gedrag van hashtabellen werpt een relevant aspect van deze datastructuren op: zelfs met een efficiënt hash-algoritme kunnen twee of meer objecten dezelfde hashcode hebben, zelfs als ze ongelijk zijn. Hun hashcodes zouden dus naar dezelfde bucket verwijzen, ook al zouden ze verschillende hash-tabeltoetsen hebben.

Deze situatie staat algemeen bekend als een hash-botsing, en er bestaan ​​verschillende methodologieën om ermee om te gaan, waarbij elk hun voor- en nadelen heeft. Java's Hash kaart gebruikt de aparte kettingmethode voor het afhandelen van botsingen:

“Als twee of meer objecten naar dezelfde bucket wijzen, worden ze gewoon opgeslagen in een gekoppelde lijst. In dat geval is de hashtabel een array van gekoppelde lijsten en wordt elk object met dezelfde hash toegevoegd aan de gekoppelde lijst bij de bucketindex in de array.

In het ergste geval zou aan meerdere buckets een gekoppelde lijst zijn gekoppeld en zou het ophalen van een object in de lijst lineair worden uitgevoerd.”

Hash-collision-methodologieën laten in een notendop zien waarom het zo belangrijk is om te implementeren hashCode () efficiënt.

Java 8 bracht een interessante verbetering met zich mee Hash kaart implementatie - als de grootte van een bucket de bepaalde drempel overschrijdt, wordt de gekoppelde lijst vervangen door een boomstructuur. Dit maakt het mogelijk om te bereiken O(logn) opkijken in plaats van pessimistisch Aan).

8. Een triviale applicatie maken

Om de functionaliteit van een standaard te testen hashCode () implementatie, laten we een eenvoudige Java-applicatie maken die wat toevoegt Gebruiker bezwaar tegen een Hash kaart en gebruikt SLF4J voor het loggen van een bericht op de console elke keer dat de methode wordt aangeroepen.

Hier is het startpunt van de voorbeeldtoepassing:

openbare klasse Application {public static void main (String [] args) {Map users = new HashMap (); Gebruiker user1 = nieuwe gebruiker (1L, "John", "[email protected]"); Gebruiker user2 = nieuwe gebruiker (2L, "Jennifer", "[email protected]"); Gebruiker user3 = nieuwe gebruiker (3L, "Mary", "[email protected]"); users.put (gebruiker1, gebruiker1); users.put (user2, user2); users.put (user3, user3); if (users.containsKey (user1)) {System.out.print ("Gebruiker gevonden in de collectie"); }}} 

En dit is de hashCode () implementatie:

openbare klasse Gebruiker {// ... openbare int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (naam == null? 0: naam.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); logger.info ("hashCode () genaamd - Berekende hash:" + hash); hash teruggeven; }}

Het enige detail dat hier moet worden benadrukt, is dat elke keer dat een object wordt opgeslagen in de hash-kaart en gecontroleerd met de bevatKey () methode, hashCode () wordt aangeroepen en de berekende hash-code wordt naar de console afgedrukt:

[hoofd] INFO com.baeldung.entities.User - hashCode () genaamd - Berekende hash: 1255477819 [hoofd] INFO com.baeldung.entities.User - hashCode () genaamd - Berekende hash: -282948472 [hoofd] INFO com.baeldung .entities.User - hashCode () called - Berekende hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode () genaamd - Berekende hash: 1255477819 Gebruiker gevonden in de verzameling

9. Conclusie

Het is duidelijk dat produceren efficiënt hashCode () implementaties vereisen vaak een combinatie van een paar wiskundige concepten (d.w.z. priemgetallen en willekeurige getallen), logische en elementaire wiskundige bewerkingen.

Hoe dan ook, het is heel goed mogelijk om te implementeren hashCode () effectief zonder toevlucht te nemen tot deze technieken, zolang we ervoor zorgen dat het hash-algoritme verschillende hashcodes produceert voor ongelijke objecten en consistent is met de implementatie van is gelijk aan ().

Zoals altijd zijn alle codevoorbeelden die in dit artikel worden getoond, beschikbaar op GitHub.