streamalism.org

1. Prehľad

Hashing je základný pojem počítačovej vedy.

V Jave stoja efektívne hašovacie algoritmy za niektorými z najpopulárnejších kolekcií, ktoré máme k dispozícii - napríklad HashMap (pre podrobný pohľad na HashMap, neváhajte skontrolovať tento článok) a HashSet.

V tomto článku sa zameriame na to, ako hashCode () funguje, ako hrá do zbierok a ako ju správne implementovať.

2. Použitie hashCode () v dátových štruktúrach

Najjednoduchšie operácie so zbierkami môžu byť v určitých situáciách neúčinné.

Napríklad to spustí lineárne vyhľadávanie, ktoré je veľmi neúčinné pre zoznamy obrovských veľkostí:

Zoznam slov = Arrays.asList ("Vitajte", "do", "Baeldung"); if (words.contains ("Baeldung")) {System.out.println ("Baeldung je v zozname"); }

Java poskytuje množstvo dátových štruktúr na konkrétne riešenie tejto problematiky - napríklad niekoľko Mapa implementácie rozhrania sú hash tabuľky.

Pri použití hashovacej tabuľky tieto kolekcie vypočítajú hodnotu hash pre daný kľúč pomocou súboru hashCode () metóda a túto hodnotu používajte interne na ukladanie údajov - aby boli operácie prístupu oveľa efektívnejšie.

3. Pochopenie ako hashCode () Tvorba

Jednoducho povedané, hashCode () vráti celočíselnú hodnotu vygenerovanú algoritmom hash.

Predmety, ktoré sú si rovné (podľa ich rovná sa ()) musí vrátiť rovnaký hash kód. Nie je potrebné, aby rôzne objekty vracali rôzne hash kódy.

Rámcová zmluva z hashCode () uvádza:

• Kedykoľvek je vyvolaný na rovnakom objekte viackrát počas vykonávania aplikácie Java, hashCode () musí dôsledne vracať rovnakú hodnotu za predpokladu, že sa nezmenia žiadne informácie použité pri rovnocennom porovnaní na objekte. Táto hodnota nemusí zostať konzistentná od jedného spustenia aplikácie k druhému spusteniu tej istej aplikácie

• Ak sú dva objekty rovnaké podľa rovná sa (Objekt) metóda, potom volanie hashCode () metóda na každom z dvoch objektov musí produkovať rovnakú hodnotu

• Nie je potrebné, aby ak sú dva objekty nerovné podľa rovná sa (java.lang.Object) metóda, potom volanie hashCode metóda na každom z dvoch objektov musí vyprodukovať odlišné celočíselné výsledky. Vývojári by si však mali uvedomiť, že vytváranie zreteľných celočíselných výsledkov pre nerovnaké objekty zlepšuje výkon hash tabuliek

"Pokiaľ je to primerane praktické, hashCode () metóda definovaná triedou Objekt vráti odlišné celé čísla pre odlišné objekty. (Toto sa zvyčajne implementuje prevedením internej adresy objektu na celé číslo, ale programovací jazyk JavaTM túto techniku ​​implementácie nevyžaduje.) “

4. Naivný hashCode () Implementácia

Je vlastne celkom jednoduché mať naivného hashCode () implementácia, ktorá plne dodržiava vyššie uvedenú zmluvu.

Aby sme to demonštrovali, ideme definovať vzorku Používateľ trieda, ktorá prepíše predvolenú implementáciu metódy:

verejná trieda Používateľ {private long id; súkromné ​​meno reťazca; súkromný reťazcový e-mail; // štandardné getre / setre / konštruktory @Override public int hashCode () {návrat 1; } @Override public boolean equals (Object o) {if (this == o) return true; if (o == null) return false; if (this.getClass ()! = o.getClass ()) vráti hodnotu false; Užívateľ užívateľ = (Užívateľ) o; návrat id == user.id && (name.equals (user.name) && email.equals (user.email)); } // zakladatelia a zakladatelia tu}

The Používateľ trieda poskytuje vlastné implementácie pre oba typy rovná sa () a hashCode () ktoré plne zodpovedajú príslušným zmluvám. Ba čo viac, na tom nie je nič nelegitímneho hashCode () vrátenie akejkoľvek pevnej hodnoty.

Táto implementácia však degraduje funkčnosť hašovacích tabuliek na v podstate nulu, pretože každý objekt by bol uložený v rovnakom jednom vedre.

V tejto súvislosti sa vyhľadávanie hašovacích tabuliek vykonáva lineárne a neprináša nám žiadnu skutočnú výhodu - viac v časti 7.

5. Zlepšenie hashCode () Implementácia

Poďme trochu vylepšiť prúd hashCode () implementácia zahrnutím všetkých oblastí Používateľ triedy, aby mohla produkovať rôzne výsledky pre nerovné objekty:

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

Tento základný hashovací algoritmus je definitívne oveľa lepší ako predchádzajúci, pretože počíta hashový kód objektu iba vynásobením hashových kódov názov a e-mail polia a id.

Všeobecne možno povedať, že je to rozumné hashCode () implementáciu, pokiaľ ponecháme rovná sa () s tým v súlade.

6. Štandardné hashCode () Implementácie

Čím lepší bude hashový algoritmus, ktorý používame na výpočet hašovacích kódov, tým lepšia bude výkonnosť hash tabuliek.

Pozrime sa na „štandardnú“ implementáciu, ktorá používa dve prvočísla na pridanie ešte väčšej jedinečnosti vypočítaným hašovacím kódom:

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

Aj keď je nevyhnutné pochopiť roly, ktoré hashCode () a rovná sa () metódy hrajú, nemusíme ich zakaždým implementovať od nuly, pretože väčšina IDE dokáže generovať vlastné hashCode () a rovná sa () implementácií a od Javy 7 sme dostali Objects.hash () užitočná metóda pre pohodlné hashovanie:

Objects.hash (meno, e-mail)

IntelliJ IDEA generuje nasledujúcu implementáciu:

@Override public int hashCode () {int result = (int) (id ^ (id >>> 32)); výsledok = 31 * výsledok + meno.hashCode (); výsledok = 31 * výsledok + email.hashCode (); návratový výsledok; }

A Eclipse vyrába tento:

@Override public int hashCode () {final int prime = 31; int výsledok = 1; result = prime * result + ((email == null)? 0: email.hashCode ()); result = prime * result + (int) (id ^ (id >>> 32)); result = prime * result + ((name == null)? 0: name.hashCode ()); návratový výsledok; }

Okrem vyššie uvedeného založené na IDE hashCode () implementácie, je tiež možné automaticky vygenerovať efektívnu implementáciu, napríklad pomocou Lomboku. V takom prípade je potrebné pridať závislosť lombok-maven pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

Teraz stačí anotovať Používateľ trieda s @EqualsAndHashCode:

@EqualsAndHashCode verejná trieda Používateľ {// polia a metódy tu}

Podobne, ak chceme Apache Commons Lang HashCodeBuilder trieda na vygenerovanie a hashCode () implementácia pre nás musí byť v súbore pom zahrnutá závislosť Commons-lang Maven:

 commons-lang commons-lang 2.6 

A hashCode () je možné implementovať takto:

verejná trieda Používateľ {public int hashCode () {vrátiť nový HashCodeBuilder (17, 37). append (id). pripojiť (meno). pripojiť (e-mail). toHashCode (); }}

Pokiaľ ide o implementáciu, všeobecne neexistuje žiadny univerzálny recept hashCode (). Dôrazne odporúčame prečítať si knihu Effective Java od Joshua Blocha, ktorá obsahuje zoznam dôkladných pokynov pre implementáciu efektívnych hashovacích algoritmov.

Tu si môžeme všimnúť, že všetky tieto implementácie využívajú číslo 31 v nejakej podobe - je to preto, lebo 31 má peknú vlastnosť - jeho násobenie je možné nahradiť bitovým posunom, ktorý je rýchlejší ako štandardné násobenie:

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

7. Riešenie zrážok s hashmi

Vnútorné správanie hašovacích tabuliek zvyšuje relevantný aspekt týchto dátových štruktúr: dokonca aj pri efektívnom hashovom algoritme môžu mať dva alebo viac objektov rovnaký hashový kód, aj keď sú nerovnaké. Ich hašovacie kódy by teda smerovali do rovnakého segmentu, aj keď by mali rôzne kľúče od hash tabuľky.

Táto situácia sa bežne nazýva hashova zrážka a na jej riešenie existujú rôzne metodiky, pričom každá z nich má svoje klady a zápory. Java HashMap používa samostatnú metódu reťazenia na riešenie kolízií:

"Keď dva alebo viac objektov ukazuje na to isté vedro, sú jednoducho uložené v prepojenom zozname." V takom prípade je hašovacia tabuľka pole prepojených zoznamov a každý objekt s rovnakým hašovaním je pripojený k prepojenému zoznamu v indexe segmentu v poli.

V najhoršom prípade by niekoľko segmentov malo viazaný prepojený zoznam a načítanie objektu v zozname by sa vykonávalo lineárne.”

Metódy hašovacích kolízií v skratke ukazujú, prečo je také dôležité ich implementovať hashCode () efektívne.

Java 8 priniesla zaujímavé vylepšenie pre HashMap implementácia - ak veľkosť segmentu presahuje určitú prahovú hodnotu, prepojený zoznam sa nahradí stromovou mapou. To umožňuje dosiahnuť O (logn) vzhliadnuť namiesto pesimizmu O (n).

8. Vytvorenie triviálnej aplikácie

Vyskúšať funkčnosť normy hashCode () implementácia, vytvorme jednoduchú aplikáciu Java, ktorá niektoré pridá Používateľ predmety do a HashMap a používa SLF4J na prihlásenie správy do konzoly pri každom volaní metódy.

Tu je vstupný bod vzorovej aplikácie:

public class Aplikácia {public static void main (String [] args) {Map users = new HashMap (); Používateľ user1 = nový Používateľ (1L, "John", "[chránený e-mailom]"); Používateľ user2 = nový používateľ (2L, "Jennifer", "[chránený e-mailom]"); Používateľ user3 = nový používateľ (3L, "Mary", "[chránený e-mailom]"); users.put (user1, user1); users.put (user2, user2); users.put (user3, user3); if (users.containsKey (user1)) {System.out.print ("Používateľ sa našiel v zbierke"); }}} 

A toto je hashCode () implementácia:

verejná trieda Používateľ {// ... public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null? 0: name.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); logger.info (volaný "hashCode () - vypočítaný hash:" + hash); návratový hash; }}

Jediný detail, ktorý tu stojí za zdôraznenie, je ten, že zakaždým, keď je objekt uložený v hašovacej mape a skontrolovaný pomocou containsKey () metóda, hashCode () je vyvolané a vypočítaný hash kód je vytlačený na konzolu:

[hlavný] INFO com.baeldung.entities.User - volaný hashCode () - vypočítaný hash: 1255477819 [hlavný] INFO com.baeldung.entities.User - volaný hashCode () - vypočítaný hash: -282948472 [hlavný] INFO com.baeldung .entities.User - volá sa hashCode () - Vypočítaný hash: -1540702691 [hlavný] INFO com.baeldung.entities.User - volá sa hashCode () - Vypočítaný hash: 1255477819 Používateľ sa našiel v zbierke

9. Záver

Je zrejmé, že výroba je efektívna hashCode () implementácie často vyžaduje kombináciu niekoľkých matematických konceptov (t.j. prvočíselných a ľubovoľných čísel), logických a základných matematických operácií.

Bez ohľadu na to je úplne možné implementovať hashCode () efektívne bez toho, aby sme sa k týmto technikám vôbec uchýlili, pokiaľ sa uistíme, že algoritmus hašovania vytvára rôzne hašovacie kódy pre nerovné objekty a je v súlade s implementáciou rovná sa ().

Všetky príklady kódov zobrazené v tomto článku sú ako vždy k dispozícii na GitHub.