Vodič za Java HashMap

1. Pregled

U ovom ćemo članku vidjeti kako se koristi HashMap u Javi, a mi ćemo pogledati kako to interno funkcionira.

Razred vrlo sličan HashMap je Hashtable. Pogledajte nekoliko naših drugih članaka da biste saznali više o java.util.Hashtable klase i razlike između HashMap i Hashtable.

2. Osnovna upotreba

Pogledajmo prvo što to znači HashMap je karta. Karta je mapiranje ključ / vrijednost, što znači da se svaki ključ preslikava na točno jednu vrijednost i da pomoću ključa možemo dohvatiti odgovarajuću vrijednost s karte.

Moglo bi se postaviti pitanje zašto vrijednost jednostavno ne dodati na popis. Zašto nam treba HashMap? Jednostavan razlog je izvedba. Ako želimo pronaći određeni element na popisu, vremenska je složenost Na) i ako je popis sortiran, bit će O (zapisnik n) koristeći, na primjer, binarno pretraživanje.

Prednost a HashMap je da je vremenska složenost umetanja i dohvaćanja vrijednosti O (1) U prosjeku. Kasnije ćemo pogledati kako se to može postići. Pogledajmo prvo kako koristiti HashMap.

2.1. Postaviti

Stvorimo jednostavnu klasu koju ćemo koristiti u cijelom članku:

proizvod javne klase {naziv privatnog niza; opis privatnog niza; oznake privatnog popisa; // standardni getteri / postavljači / konstruktori public Product addTagsOfOtherProdcut (Product product) {this.tags.addAll (product.getTags ()); vrati ovo; }}

2.2. Staviti

Sada možemo stvoriti HashMap s tipkom tipa Niz i elementi tipa Proizvod:

Karta proizvodaByName = novi HashMap (); 

I dodajte proizvode u naše HashMap:

Product eBike = novi proizvod ("E-Bike", "Bicikl s baterijom"); Product roadBike = novi proizvod ("Cestovni bicikl", "Bicikl za natjecanje"); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 

2.3. Dobiti

Vrijednost s karte možemo dohvatiti njezinim ključem:

Proizvod nextPurchase = productsByName.get ("E-bicikl"); assertEquals ("Bicikl s baterijom", nextPurchase.getDescription ());

Ako pokušamo pronaći vrijednost za ključ koji ne postoji na karti, dobit ćemo null vrijednost:

Proizvod nextPurchase = productsByName.get ("Automobil"); assertNull (nextPurchase);

A ako umetnemo drugu vrijednost s istim ključem, dobit ćemo samo zadnju umetnutu vrijednost za taj ključ:

Proizvod newEBike = novi proizvod ("E-bicikl", "Bicikl s boljom baterijom"); productsByName.put (newEBike.getName (), newEBike); assertEquals ("Bicikl s boljom baterijom", productsByName.get ("E-Bike"). getDescription ());

2.4. Ništav kao Ključ

HashMap također nam omogućuje da imamo null kao ključ:

Product defaultProduct = novi proizvod ("Čokolada", "Barem kupite čokoladu"); productsByName.put (null, defaultProduct); Proizvod nextPurchase = productsByName.get (null); assertEquals ("Barem kupite čokoladu", nextPurchase.getDescription ());

2.5. Vrijednosti s istim ključem

Nadalje, isti objekt možemo umetnuti dva puta različitim ključem:

productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("Chocolate"));

2.6. Uklonite vrijednost

Mapiranje ključ / vrijednost možemo ukloniti iz HashMap:

productsByName.remove ("E-bicikl"); assertNull (productsByName.get ("E-Bike"));

2.7. Provjerite postoji li na karti ključ ili vrijednost

Da bismo provjerili je li ključ prisutan na karti, možemo upotrijebiti containsKey () metoda:

productsByName.containsKey ("E-bicikl");

Ili da provjerimo je li vrijednost prisutna na karti, možemo upotrijebiti sadržiVrijednost () metoda:

productsByName.containsValue (eBike);

Vratit će se oba poziva metode pravi u našem primjeru. Iako izgledaju vrlo slično, postoji važna razlika u performansama između ova dva poziva metode. Složenost provjere postoji li ključ je O (1), dok je složenost provjere elementa Na), jer je potrebno petlju nad svim elementima na karti.

2.8. Iteriranje preko a HashMap

Tri su osnovna načina za itiriranje svih parova ključ / vrijednost u a HashMap.

Možemo ponoviti niz svih tipki:

for (Ključ niza: productsByName.keySet ()) {Product product = productsByName.get (key); }

Ili možemo ponoviti niz svih unosa:

for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Ključ niza = entry.getKey (); // učiniti nešto s ključem i vrijednošću}

Konačno, možemo ponoviti sve vrijednosti:

Popis proizvoda = novi ArrayList (productsByName.values ​​());

3. Ključ

Bilo koju klasu možemo koristiti kao ključ u našoj HashMap. Međutim, da bi karta ispravno radila, moramo osigurati implementaciju za jednako () i hashCode ().Recimo da želimo imati kartu s proizvodom kao ključem i cijenom kao vrijednošću:

HashMap priceByProduct = novi HashMap (); priceByProduct.put (eBike, 900);

Provedimo jednako () i hashCode () metode:

@Override public boolean equals (Objekt o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Proizvod proizvoda = (Proizvod) o; vratiti Objects.equals (ime, proizvod.ime) && Objects.equals (opis, product.description); } @Override public int hashCode () {return Objects.hash (ime, opis); }

Imajte na umu da hashCode () i jednako () treba nadjačati samo za razrede koje želimo koristiti kao ključeve karte, a ne za razrede koji se koriste samo kao vrijednosti na karti. Zašto je to potrebno vidjet ćemo u odjeljku 5 ovog članka.

4. Dodatne metode od Jave 8

Java 8 dodala je nekoliko metoda u funkcionalnom stilu HashMap. U ovom ćemo odjeljku pogledati neke od ovih metoda.

Za svaku ćemo metodu pogledati dva primjera. Prvi primjer pokazuje kako se koristi nova metoda, a drugi primjer kako se to postiže u ranijim verzijama Jave.

Budući da su ove metode prilično jednostavne, nećemo razmatrati detaljnije primjere.

4.1. za svakoga()

The za svakoga metoda je način ponavljanja svih elemenata na karti u funkcionalnom stilu:

productsByName.forEach ((ključ, proizvod) -> {System.out.println ("Ključ:" + ključ + "Proizvod:" + proizvod.getDescription ()); // napravite nešto s ključem i vrijednošću}); 

Prije Java 8:

for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Ključ niza = entry.getKey (); // učiniti nešto s ključem i vrijednošću}

Naš članak Vodič za Javu 8 za svakoga pokriva za svakoga petlja detaljnije.

4.2. getOrDefault ()

Koristiti getOrDefault () metodom, možemo dobiti vrijednost s karte ili vratiti zadani element u slučaju da nema mapiranja za zadani ključ:

Proizvod čokolada = novi proizvod ("čokolada", "nešto slatko"); Product defaultProduct = productsByName.getOrDefault ("konjska zaprega", čokolada); Product bike = productsByName.getOrDefault ("E-Bike", čokolada);

Prije Java 8:

Proizvod bike2 = productsByName.containsKey ("E-bicikl")? productsByName.get ("E-Bike"): čokolada; Product defaultProduct2 = productsByName.containsKey ("konjska zaprega")? productsByName.get ("konjska zaprega"): čokolada; 

4.3. putIfAbsent ()

Ovom metodom možemo dodati novo mapiranje, ali samo ako još nema mapiranja za zadani ključ:

productsByName.putIfAbsent ("E-Bike", čokolada); 

Prije Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.put ("E-Bike", čokolada); }

Naš članak Spajanje dviju karata s Javom 8 bliže proučava ovu metodu.

4.4. sjediniti()

I sa sjediniti(), možemo izmijeniti vrijednost za zadani ključ ako postoji mapiranje ili dodati novu vrijednost u suprotnom:

Proizvod eBike2 = novi proizvod ("E-bicikl", "Bicikl s baterijom"); eBike2.getTags (). add ("sport"); productsByName.merge ("E-bicikl", eBike2, Product :: addTagsOfOtherProdcut);

Prije Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } else {productsByName.put ("E-bicikl", eBike2); } 

4.5. izračunati ()

Uz izračunati () metodom možemo izračunati vrijednost za zadani ključ:

productsByName.compute ("E-Bike", (k, v) -> {if (v! = null) {return v.addTagsOfOtherProdcut (eBike2);} else {return eBike2;}});

Prije Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } else {productsByName.put ("E-bicikl", eBike2); } 

Vrijedno je napomenuti da metode sjediniti() i izračunati () prilično su slični. The compute () metoda prihvaća dva argumenta: ključ i a BiFunction za remapiranje. I sjediniti() prihvaća tri parametra: ključ, a zadana vrijednost za dodavanje na kartu ako ključ još ne postoji, a BiFunction za remapiranje.

5. HashMap Unutarnji dijelovi

U ovom ćemo odjeljku pogledati kako HashMap radi interno i koje su prednosti korištenja HashMap umjesto jednostavnog popisa, na primjer.

Kao što smo vidjeli, element možemo dohvatiti iz datoteke HashMap po svom ključu. Jedan od pristupa bio bi korištenje popisa, prelistavanje svih elemenata i povratak kada pronađemo element za koji se ključ podudara. Složenost ovog pristupa bila bi i vremenska i prostorna Na).

S HashMap, možemo postići prosječnu vremensku složenost od O (1) za staviti i dobiti složenost operacija i prostora Na). Da vidimo kako to funkcionira.

5.1. Hash-ov kod i jednako

Umjesto ponavljanja svih njegovih elemenata, HashMap pokušava izračunati položaj vrijednosti na temelju njezinog ključa.

Naivni pristup bio bi imati popis koji može sadržavati onoliko elemenata koliko je moguće ključeva. Kao primjer, recimo da je naš ključ malo slovo. Tada je dovoljno imati popis veličine 26, a ako želimo pristupiti elementu s tipkom 'c', znali bismo da je to onaj na položaju 3 i mogli bismo ga izravno dohvatiti.

Međutim, ovaj pristup ne bi bio vrlo učinkovit ako imamo puno veći prostor tipki. Na primjer, recimo da je naš ključ bio cijeli broj. U ovom bi slučaju veličina popisa trebala biti 2.147.483.647. U većini slučajeva imali bismo i mnogo manje elemenata, pa bi velik dio dodijeljene memorije ostao neiskorišten.

HashMap pohranjuje elemente u takozvane segmente i naziva se broj segmenata kapacitet.

Kad na kartu stavimo vrijednost, ključ hashCode () metoda koristi se za određivanje segmenta u kojem će se vrijednost pohraniti.

Da biste dohvatili vrijednost, HashMap izračunava skup na isti način - koristeći hashCode (). Zatim prelazi kroz objekte pronađene u toj skupini i koristi ključeve jednako () metoda za pronalaženje točnog podudaranja.

5.2. Nepromjenjivost tipki

U većini slučajeva trebali bismo koristiti nepromjenjive ključeve. Ili barem moramo biti svjesni posljedica upotrebe promjenjivih tipki.

Pogledajmo što se događa kada se naš ključ promijeni nakon što smo ga koristili za pohranu vrijednosti na kartu.

Za ovaj primjer ćemo stvoriti MutableKey:

javna klasa MutableKey {naziv privatnog niza; // standardni konstruktor, dobivač i postavljač @Override public boolean equals (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Promjenjiva tipka koja = (Promjenjiva tipka) o; vratiti Objects.equals (ime, to.ime); } @Override public int hashCode () {return Objects.hash (ime); }}

I evo testa:

MutableKey ključ = novi MutableKey ("početni"); Stavke na mapi = novi HashMap (); items.put (ključ, "uspjeh"); key.setName ("promijenjeno"); assertNull (items.get (ključ));

Kao što vidimo, više ne možemo dobiti odgovarajuću vrijednost nakon što se ključ promijeni, null se vraća. Ovo je zbog HashMap traži u pogrešnoj skupini.

Gornji testni slučaj može biti iznenađujući ako ne razumijemo dobro kako HashMap radi interno.

5.3. Sudari

Da bi ovo ispravno funkcioniralo, jednaki ključevi moraju imati isti heš, međutim, različiti ključevi mogu imati isti heš. Ako dva različita ključa imaju isto raspršivanje, dvije njima pripadajuće vrijednosti pohranit će se u isti segment. Unutar segmenta vrijednosti se pohranjuju na popis i dohvaćaju petljanjem po svim elementima. Trošak ovoga je Na).

Od Jave 8 (vidi JEP 180), struktura podataka u kojoj se pohranjuju vrijednosti unutar jednog segmenta mijenja se s popisa u uravnoteženo stablo ako segment sadrži 8 ili više vrijednosti, a vraća se na popis ako neki trenutak, u segmentu je ostalo samo 6 vrijednosti. Ovo poboljšava performanse koje treba biti O (zapisnik n).

5.4. Kapacitet i faktor opterećenja

Kako bi se izbjeglo da ima mnogo kašika s više vrijednosti, kapacitet se udvostručuje ako 75% (faktor opterećenja) kašika postane prazno. Zadana vrijednost za faktor opterećenja je 75%, a zadani početni kapacitet je 16. Obje se mogu postaviti u konstruktoru.

5.5. Sažetak staviti i dobiti Operacije

Sažmimo kako staviti i dobiti operativni rad.

Kada na kartu dodamo element,HashMap izračunava kantu. Ako segment već sadrži vrijednost, vrijednost se dodaje na popis (ili stablo) koji pripada tom segmentu. Ako faktor opterećenja postane veći od maksimalnog faktora opterećenja karte, kapacitet se udvostručuje.

Kada želimo dobiti vrijednost s karte,HashMap izračunava segment i dobiva vrijednost s istim ključem s popisa (ili stabla).

6. Zaključak

U ovom smo članku vidjeli kako se koristi HashMap i kako interno djeluje. Zajedno s ArrayList, HashMap jedna je od najčešće korištenih struktura podataka u Javi, pa je vrlo dobro imati dobro znanje o tome kako se koristi i kako to funkcionira ispod haube. Naš članak Java HashMap Under Hood pokriva unutarnje dijelove HashMap detaljnije.

Kao i obično, cjeloviti izvorni kod dostupan je na Githubu.


$config[zx-auto] not found$config[zx-overlay] not found