streamalism.org

1. Áttekintés

A hasholás a számítástechnika alapvető fogalma.

A Java-ban a hatékony kivonatoló algoritmusok állnak a rendelkezésünkre álló legnépszerűbb gyűjtemények - például a HashMap (a részletes áttekintéshez HashMap, nyugodtan ellenőrizze ezt a cikket) és a HashSet.

Ebben a cikkben arra összpontosítunk, hogyan hash kód() működik, hogyan játszik gyűjteményeket és hogyan kell helyesen megvalósítani.

2. Használata hash kód() az adatstruktúrákban

A gyűjteményekkel kapcsolatos legegyszerűbb műveletek bizonyos helyzetekben hatástalanok lehetnek.

Például ez egy lineáris keresést indít el, amely rendkívül hatékony a hatalmas méretű listák esetében:

Sorolja fel a szavakat = Arrays.asList ("Welcome", "to", "Baeldung"); if (szavak.tartalmazza ("Baeldung")) {System.out.println ("Baeldung szerepel a listán"); }

A Java számos adatstruktúrát biztosít a probléma konkrét kezeléséhez - például több Térkép az interfész megvalósítások hash táblák.

Kivonat táblázat használata esetén ezek a gyűjtemények kiszámítják az adott kulcs kivonatolási értékét a hash kód() módszer és ezt az értéket belsőleg használja az adatok tárolására - így a hozzáférési műveletek sokkal hatékonyabbak.

3. A hogyan megértése hash kód() Művek

Egyszerűen fogalmazva, hash kód() egy egész értéket ad vissza, amelyet egy hash algoritmus generál.

Objektumok, amelyek egyenlőek (a egyenlő ()) ugyanazt a hash kódot kell visszaadnia. Nem szükséges, hogy a különböző objektumok különböző kivonatkódokat adjanak vissza.

A. Általános szerződése hash kód() Államok:

• Amikor egy Java alkalmazás futtatása során ugyanazon az objektumon többször is meghívják, hash kód() következetesen meg kell adnia ugyanazt az értéket, feltéve, hogy az objektum összehasonlításában használt információ nem módosul. Ennek az értéknek nem kell állandónak maradnia az alkalmazás egyik végrehajtásától az ugyanazon alkalmazás másik végrehajtásáig

• Ha két objektum egyenlő a egyenlő (Object) metódust, majd meghívja a hash kód() A két objektum metódusának ugyanazt az értéket kell előállítania

• Nem szükséges, hogy ha két objektum egyenlőtlen a egyenlő (java.lang.Object) metódust, majd meghívja a hash kód A két objektum metódusának különálló egész eredményeket kell eredményeznie. A fejlesztőknek azonban tisztában kell lenniük azzal, hogy az egyenlőtlen objektumok esetében különálló egész számok eredményezése javítja a hash táblák teljesítményét

„Bármennyire is ésszerű gyakorlat, a hash kód() osztály által meghatározott módszer Tárgy egész számokat ad vissza különálló objektumokhoz. (Ezt általában úgy hajtják végre, hogy az objektum belső címét egész számra konvertálja, de a JavaTM programozási nyelv nem igényli ezt a megvalósítási technikát.) ”

4. Egy naiv hash kód() Végrehajtás

Tulajdonképpen nagyon egyszerű, ha van egy naiv hash kód() megvalósítása, amely teljes mértékben betartja a fenti szerződést.

Ennek bemutatására meghatározunk egy mintát Felhasználó osztály, amely felülírja a módszer alapértelmezett megvalósítását:

public class Felhasználó {private long id; privát karakterlánc neve; privát karakterlánc e-mail; // standard getters / setters / konstruktorok @Orride public int hashCode () {return 1; } @Orride public boolean egyenlő (Object o) {if (this == o) return true; if (o == null) false értéket ad vissza; if (this.getClass ()! = o.getClass ()) hamis értéket ad vissza; Felhasználó felhasználó = (Felhasználó) o; return id == felhasználó.azonosító && (név.egyenlő (felhasználónév) && e-mail.egyenlő (felhasználó.email)); } // getterek és beállítók itt}

A Felhasználó osztály egyedi megvalósításokat biztosít mindkettőhöz egyenlő () és hash kód() amelyek teljes mértékben betartják a vonatkozó szerződéseket. Sőt, nincs semmi törvénytelen a birtoklással hash kód() bármilyen fix értéket visszaadva.

Ez a megvalósítás azonban alapvetően nullára bontja a hash táblák funkcionalitását, mivel minden objektum ugyanabban az egyetlen sávban lenne tárolva.

Ebben az összefüggésben a hash-tábla kikeresése lineárisan történik, és nem jelent számunkra semmilyen valós előnyt - erről a 7. szakaszban olvashat bővebben.

5. A hash kód() Végrehajtás

Javítsuk egy kicsit az áramot hash kód() - a végrehajtás a Felhasználó osztály, hogy különböző eredményeket tudjon produkálni egyenlőtlen objektumok esetén:

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

Ez az alap kivonatoló algoritmus egyértelműen sokkal jobb, mint az előző, mivel kiszámítja az objektum kivonatkódját, csak szorozva a név és email mezők és a id.

Általánosságban elmondhatjuk, hogy ez ésszerű hash kód() megvalósítását, mindaddig, amíg a egyenlő () végrehajtása összhangban van vele.

6. Standard hash kód() Végrehajtások

Minél jobb a hash-algoritmus, amelyet a hash-kódok kiszámításához használunk, annál jobb lesz a hash-táblák teljesítménye.

Vessünk egy pillantást egy „standard” megvalósításra, amely két prímszámot használ, hogy még több egyediséget adjon a számított kivonatkódokhoz:

@Orride public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (név == null? 0: név.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); return hash; }

Bár elengedhetetlen megérteni azokat a szerepeket hash kód() és egyenlő () a módszerek játszanak, nem kell minden alkalommal a semmiből megvalósítanunk, mivel a legtöbb IDE képes egyedi létrehozására hash kód() és egyenlő () implementációk és a Java 7 óta kaptunk egy Objects.hash () segédprogram a kényelmes hasholáshoz:

Objects.hash (név, e-mail cím)

Az IntelliJ IDEA a következő megvalósítást generálja:

@Orride public int hashCode () {int result = (int) (id ^ (id >>> 32)); eredmény = 31 * eredmény + név.hashCode (); eredmény = 31 * eredmény + e-mail.hashCode (); visszatérési eredmény; }

Az Eclipse pedig ezt állítja elő:

@Orride public int hashCode () {final int prime = 31; int eredmény = 1; eredmény = fő * eredmény + ((e-mail == null)? 0: email.hashCode ()); eredmény = elsődleges * eredmény + (int) (id ^ (id >>> 32)); eredmény = elsődleges * eredmény + ((név == null)? 0: név.hashCode ()); visszatérési eredmény; }

A fenti IDE-alapú mellett hash kód() megvalósítások esetén a hatékony megvalósítás automatikus generálása is lehetséges, például a Lombok használatával. Ebben az esetben hozzá kell adni a lombok-maven függőséget pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

Most már elég megjegyezni a Felhasználó osztályban @EqualsAndHashCode:

@EqualsAndHashCode public class User {// mezők és módszerek itt}

Hasonlóképpen, ha az Apache Commons Lang-t akarjuk HashCodeBuilder osztály létrehozásához hash kód() A számunkra a commons-lang Maven függőséget be kell építeni a pom fájlba:

 commons-lang commons-lang 2.6 

És hash kód() így lehet megvalósítani:

public class Felhasználó {public int hashCode () {return new HashCodeBuilder (17, 37). függelék (id). függelék (név). melléklet (e-mail). toHashCode (); }}

Általánosságban elmondható, hogy nincs univerzális recept, amelyhez ragaszkodni kellene a megvalósítás során hash kód(). Javasoljuk, hogy olvassa el Joshua Bloch Effective Java című cikkét, amely átfogó útmutatásokat tartalmaz a hatékony hash algoritmusok megvalósításához.

Itt észrevehető, hogy mindezek a megvalósítások valamilyen formában felhasználják a 31-es számot - ez azért van, mert a 31-nek szép tulajdonsága van - szorzása helyettesíthető egy bitenkénti eltolással, amely gyorsabb, mint a szokásos szorzás:

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

7. Hash ütközések kezelése

A hash táblák belső viselkedése felveti ezeknek az adatstruktúráknak a releváns szempontját: még hatékony hash algoritmus esetén is két vagy több objektumnak azonos hash kódja lehet, még akkor is, ha egyenlőtlenek. Tehát a kivonatkódjaik ugyanarra a vödörre mutatnak, annak ellenére, hogy különböző hash-tábla kulcsokkal rendelkeznek.

Ez a helyzet közismert nevén hash ütközés, és ennek kezelésére különféle módszertanok léteznek, mindegyiknek megvannak az előnyei és hátrányai. Java HashMap az ütközések kezeléséhez külön láncolási módszert alkalmaz:

„Ha két vagy több objektum ugyanarra a vödörre mutat, akkor egyszerűen egy összekapcsolt listában tárolódnak. Ilyen esetben a hash tábla összekapcsolt listák tömbje, és minden azonos hashszal rendelkező objektumot hozzá kell fűzni a csatolt listához a tömb tömbindexében.

A legrosszabb esetben több vödörhöz kapcsolódik egy összekapcsolt lista, és a listában lévő objektum visszakeresése lineárisan történik.”

A hash ütközés módszertanai dióhéjban megmutatják, miért olyan fontos a megvalósítás hash kód() hatékonyan.

A Java 8 érdekes továbbfejlesztést hozott HashMap megvalósítás - ha a vödör mérete meghaladja a bizonyos küszöbértéket, akkor a csatolt lista fatérképre cserélődik. Ez lehetővé teszi az elérést O (logn) nézz fel pesszimista helyett Tovább).

8. Triviális alkalmazás létrehozása

Egy szabvány működésének tesztelése hash kód() hozzunk létre egy egyszerű Java alkalmazást, amely hozzáad néhányat Felhasználó kifogásolja a HashMap és az SLF4J segítségével naplózza az üzenetet a konzolra a módszer meghívásakor.

Itt található a minta alkalmazás belépési pontja:

public class Alkalmazás {public static void main (String [] args) {Map users = new HashMap (); User1 felhasználó = új felhasználó (1L, "John", "[email protected]"); User2 felhasználó = új felhasználó (2L, "Jennifer", "[email protected]"); User3 = új felhasználó (3L, "Mary", "[email protected]"); users.put (user1, user1); users.put (user2, user2); users.put (user3, user3); if (users.containsKey (user1)) {System.out.print ("Felhasználó megtalálható a gyűjteményben"); }}} 

És ez az hash kód() végrehajtás:

public class Felhasználó {// ... public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (név == null? 0: név.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); logger.info ("hashCode () nevű - Számított hash:" + hash); return hash; }}

Az egyetlen részlet, amelyet érdemes hangsúlyozni, az az, hogy minden alkalommal, amikor egy objektumot tárolnak a hash térképen, és ellenőrizzük a tartalmazzaKey () módszer, hash kód() meghívásra kerül, és a számított kivonatkód kinyomtatásra kerül a konzolra:

[main] INFO com.baeldung.entities.User - hashCode () hívott - Számított hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode () hívott - Computed hash: -282948472 [main] INFO com.baeldung .entities.User - hashCode () nevű - Számított hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode () hívva - Computed hash: 1255477819 Felhasználó megtalálható a gyűjteményben

9. Következtetés

Egyértelmű, hogy hatékonyan termel hash kód() a megvalósításokhoz gyakran szükség van néhány matematikai fogalom (azaz prím és tetszőleges szám), logikai és alapvető matematikai műveletek keverékére.

Ettől függetlenül teljesen megvalósítható hash kód() hatékonyan, anélkül, hogy egyáltalán igénybe venné ezeket a technikákat, mindaddig, amíg megbizonyosodunk arról, hogy a hash algoritmus különböző kivonatkódokat állít elő egyenlőtlen objektumokhoz, és összhangban van a egyenlő ().

Mint mindig, a cikkben bemutatott összes kódpélda elérhető a GitHubon.