streamalism.org

1. Áttekintés

Ebben a cikkben megtudjuk, hogyan kell használni HashMap Java-ban, és megnézzük, hogyan működik belsőleg.

Nagyon hasonló osztály HashMap van Hashtable. Kérjük, olvassa el néhány másik cikkünket, hogy többet megtudjon a java.util.Hashtable maga az osztály és a különbségek HashMap és Hashtable.

2. Alapvető használat

Először nézzük meg, mit jelent ez HashMap egy térkép. A térkép kulcs-érték leképezés, ami azt jelenti, hogy minden kulcs pontosan egy értékhez van hozzárendelve, és hogy a kulcs segítségével lekérhetjük a megfelelő értéket egy térképről.

Kérdezhetjük, miért nem egyszerűen hozzáadjuk az értéket egy listához. Miért van szükségünk a HashMap? Az egyszerű ok a teljesítmény. Ha egy adott elemet meg akarunk találni egy listában, akkor az idő bonyolultsága az Tovább) és ha a lista rendezve van, akkor az lesz O (log n) például bináris kereséssel.

A. Előnye HashMap az, hogy az érték beillesztésének és visszakeresésének időbeli összetettsége O (1) átlagban. Később megvizsgáljuk, hogyan lehet ezt elérni. Először nézzük meg, hogyan kell használni HashMap.

2.1. Beállít

Hozzunk létre egy egyszerű osztályt, amelyet a cikkben használunk:

public class Termék {private String name; privát karakterlánc leírása; privát lista címkék; // standard getters / setters / konstruktorok public Product addTagsOfOtherProdcut (Product product) {this.tags.addAll (product.getTags ()); adja vissza ezt; }}

2.2. Tedd

Most létrehozhatunk egy HashMap típusú kulccsal Húr és típusú elemek Termék:

Térképes termékekByName = új HashMap (); 

És adjon termékeket a mi HashMap:

Product eBike = új termék ("E-Bike", "Bicikli akkumulátorral"); Termék roadBike = új termék ("Országúti kerékpár", "Kerékpár a versenyhez"); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 

2.3. Kap

Egy értéket lekérhetünk a térképről a kulcsával:

Termék nextPurchase = productsByName.get ("E-Bike"); assertEquals ("Kerékpár akkumulátorral", nextPurchase.getDescription ());

Ha megpróbálunk olyan kulcsot találni, amely nem létezik a térképen, akkor a nulla érték:

Termék nextPurchase = productsByName.get ("Autó"); assertNull (nextPurchase);

És ha beillesztünk egy második értéket ugyanazzal a kulccsal, akkor csak a kulcs utolsó beillesztett értékét kapjuk meg:

Termék newEBike = új termék ("E-Bike", "Jobb akkumulátorú kerékpár"); productsByName.put (newEBike.getName (), newEBike); assertEquals ("Kerékpár jobb akkumulátorral", productsByName.get ("E-Bike"). getDescription ());

2.4. Null, mint a kulcs

HashMap is lehetővé teszi számunkra, hogy nulla kulcsként:

Product defaultProduct = new Product ("Csokoládé", "Legalább vásároljon csokoládét"); productsByName.put (null, defaultProduct); Termék nextPurchase = productsByName.get (null); assertEquals ("Legalább vásároljon csokoládét", nextPurchase.getDescription ());

2.5. Értékek ugyanazzal a kulccsal

Ezenkívül kétszer beilleszthetjük ugyanazt az objektumot egy másik kulccsal:

productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("Csokoládé"));

2.6. Érték eltávolítása

Eltávolíthatjuk a kulcs-érték leképezést a HashMap:

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

2.7. Ellenőrizze, hogy létezik-e kulcs vagy érték a térképen

Annak ellenőrzésére, hogy van-e kulcs a térképen, használhatjuk a tartalmazzaKey () módszer:

productsByName.containsKey ("E-Bike");

Vagy ellenőrizhetjük, hogy van-e érték a térképen, használhatjuk a tartalmazzaValue () módszer:

productsByName.containsValue (eBike);

Mindkét módszerhívás visszatér igaz példánkban. Bár nagyon hasonlítanak egymásra, a két módszerhívás között fontos a teljesítménybeli különbség. A bonyolultság ellenőrzése, hogy van-e kulcs, igen O (1), míg egy elem ellenőrzésének összetettsége Tovább), mivel szükség van a térkép összes elemének áttekintésére.

2.8. Iteráló Több mint a HashMap

Három alapvető módja van az összes kulcsérték-pár iterációjának az a-ban HashMap.

Iterálhatunk az összes kulcs halmazán:

for (Karaktersorozatkulcs: productsByName.keySet ()) {Product product = productsByName.get (kulcs); }

Vagy iterálhatunk az összes bejegyzés halmazán:

a (Map.Entry bejegyzéshez: productsByName.entrySet ()) {Product product = entry.getValue (); Karaktersorozat = entry.getKey (); // tegyen valamit a kulccsal és az értékkel}

Végül minden értéket iterálni tudunk:

Terméklista = new ArrayList (productsByName.values ​​());

3. A kulcs

Bármely osztályt használhatjuk kulcsként HashMap. A térkép megfelelő működéséhez azonban biztosítanunk kell a megvalósítását egyenlő () és hash kód().Tegyük fel, hogy szeretnénk egy térképet, amelynek kulcsa a termék és értéke az ár:

HashMap priceByProduct = új HashMap (); priceByProduct.put (eBike, 900);

Végezzük el a egyenlő () és hash kód() mód:

@Orride public boolean egyenlő (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Terméktermék = (Termék) o; return Objects.equals (név, termék.név) && Objects.equals (leírás, termék.leírás); } @Orride public int hashCode () {return Objects.hash (név, leírás); }

Vegye figyelembe, hogy hash kód() és egyenlő () csak azoknál az osztályoknál kell felülírni, amelyeket térképkulcsként akarunk használni, nem pedig azoknál az osztályoknál, amelyeket csak értékként használunk a térképen. A cikk 5. szakaszában megtudjuk, miért van erre szükség.

4. További módszerek a Java 8-tól kezdve

A Java 8 számos funkcionális stílusú módszert adott hozzá HashMap. Ebben a szakaszban megnézzük ezeket a módszereket.

Mindegyik módszerhez két példát nézünk meg. Az első példa bemutatja, hogyan kell használni az új módszert, a második példa pedig azt mutatja be, hogyan érhető el ugyanez a Java korábbi verzióiban.

Mivel ezek a módszerek meglehetősen egyszerűek, részletesebb példákat nem nézünk meg.

4.1. az egyes()

A az egyes A módszer a funkcionális stílusú módszer a térkép összes elemének iterációjára:

productsByName.forEach ((kulcs, termék) -> {System.out.println ("Kulcs:" + kulcs + "Termék:" + product.getDescription ()); // tegyen valamit a kulccsal és az értékkel}); 

Java 8 előtt:

a (Map.Entry bejegyzéshez: productsByName.entrySet ()) {Product product = entry.getValue (); Karaktersorozat = entry.getKey (); // tegyen valamit a kulccsal és az értékkel}

Cikkünk Útmutató a Java 8-hoz az egyes lefedi a az egyes hurok részletesebben.

4.2. getOrDefault ()

Használni a getOrDefault () metódus esetén lekérhetünk egy értéket a térképről, vagy visszaadhatunk egy alapértelmezett elemet, ha nincs hozzárendelés az adott kulcshoz:

Termékcsokoládé = új Termék ("csokoládé", "valami édes"); Product defaultProduct = productsByName.getOrDefault ("lovaskocsi", csokoládé); Termékkerékpár = productsByName.getOrDefault ("E-Bike", csokoládé);

Java 8 előtt:

Termék bike2 = productsByName.containsKey ("E-Bike")? productsByName.get ("E-Bike"): csokoládé; Product defaultProduct2 = productsByName.containsKey ("lovaskocsi")? productsByName.get ("lovaskocsi"): csokoládé; 

4.3. putIfAbsent ()

Ezzel a módszerrel felvehetünk egy új leképezést, de csak akkor, ha még nincs hozzárendelés az adott kulcshoz:

productsByName.putIfAbsent ("E-Bike", csokoládé); 

Java 8 előtt:

if (productsByName.containsKey ("E-Bike")) {productsByName.put ("E-Bike", csokoládé); }

A Két térkép egyesítése Java 8-tal cikkünk közelebbről megvizsgálja ezt a módszert.

4.4. összeolvad()

És azzal összeolvad(), módosíthatjuk az adott kulcs értékét, ha létezik leképezés, vagy másképpen hozzáadhatunk egy új értéket:

EBike2 = új termék ("E-Bike", "Bike with a battery"); eBike2.getTags (). add ("sport"); productsByName.merge ("E-Bike", eBike2, Product :: addTagsOfOtherProdcut);

Java 8 előtt:

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

4.5. kiszámít()

A ... val kiszámít() módszerrel kiszámíthatjuk egy adott kulcs értékét:

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

Java 8 előtt:

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

Érdemes megjegyezni, hogy a mód összeolvad() és kiszámít() meglehetősen hasonlóak. A compute () metódus két érvet fogad el: a kulcs és a BiFunction az újratervezéshez. És összeolvad() három paramétert fogad el: a kulcs, a alapértelmezett érték hozzáadni a térképhez, ha a kulcs még nem létezik, és a BiFunction az újratervezéshez.

5. HashMap Belsők

Ebben a részben megnézzük, hogyan HashMap belül működik, és milyen előnyökkel jár a használata HashMap például egy egyszerű lista helyett.

Mint láttuk, lekérhetünk egy elemet az a-ból HashMap kulcsával. Az egyik megközelítés egy lista használata, az összes elem ismétlése és visszatérés, ha találunk egy elemet, amelyhez a kulcs egyezik. E megközelítés időbeli és térbeli összetettsége egyaránt Tovább).

Val vel HashMap, elérhetjük az átlagos időbeli komplexitást O (1) a tedd és kap műveletek és a tér komplexitása Tovább). Lássuk, hogyan működik.

5.1. A hash kód és az egyenlő

Ahelyett, hogy iterálna az összes elemén, HashMap megkísérli kiszámítani egy érték pozícióját a kulcsa alapján.

A naiv megközelítés az lenne, ha lenne egy lista, amely annyi elemet tartalmazhat, ahány kulcs lehetséges. Példaként tegyük fel, hogy kulcsunk kisbetűs karakter. Akkor elegendő, ha van egy 26-os méretű lista, és ha el akarjuk érni az elemet a „c” kulccsal, tudnánk, hogy ez a 3. pozícióban van, és közvetlenül visszakereshetjük.

Ez a megközelítés azonban nem lenne túl hatékony, ha sokkal nagyobb a kulcstérünk. Tegyük fel például, hogy a kulcsunk egész szám volt. Ebben az esetben a lista méretének 2 147 483 647-nek kellene lennie. A legtöbb esetben nekünk is sokkal kevesebb elemünk lenne, így a lefoglalt memória nagy része kihasználatlan maradna.

HashMap elemeket úgynevezett vödrökben tárol, és a vödrök számát hívják meg kapacitás.

Ha a térképbe beírunk egy értéket, akkor a kulcsé hash kód() metódus segítségével meghatározható az a csoport, amelyben az érték tárolásra kerül.

Az érték lekéréséhez HashMap ugyanúgy kiszámítja a vödröt - a hash kód(). Ezután végigméri az adott vödörben található objektumokat, és használja a kulcsokat egyenlő () módszer a pontos egyezés megtalálásához.

5.2. Keys megváltoztathatatlansága

A legtöbb esetben változhatatlan kulcsokat kell használnunk. Vagy legalábbis tisztában kell lennünk a változtatható kulcsok használatának következményeivel.

Lássuk, mi történik, ha a kulcsunk megváltozik, miután értéket tároltunk a térképen.

Ebben a példában létrehozzuk a MutableKey:

public class MutableKey {private String name; // standard konstruktor, getter és szetter @Orride public boolean egyenlő (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } MutableKey, amely = (MutableKey) o; return Objects.equals (név, az a név); } @Orride public int hashCode () {return Objects.hash (név); }}

És itt megy a teszt:

MutableKey kulcs = new MutableKey ("kezdeti"); Térképelemek = new HashMap (); items.put (kulcs, "siker"); key.setName ("megváltozott"); assertNull (items.get (kulcs));

Amint láthatjuk, a kulcs megváltoztatása után már nem tudjuk megszerezni a megfelelő értéket, nulla visszatér. Ez azért van, mert HashMap rossz vödörben keres.

A fenti tesztesemény meglepő lehet, ha nem értjük jól, hogyan HashMap belsőleg működik.

5.3. Ütközések

Ahhoz, hogy ez megfelelően működjön, az egyenlő kulcsoknak ugyanannak a kivonattal kell rendelkezniük, azonban a különböző kulcsoknak ugyanaz a kivonatuk lehet. Ha két különböző kulcsnak ugyanaz a kivonata, a hozzájuk tartozó két érték ugyanabban a vödörben lesz tárolva. A vödör belsejében az értékek egy listában vannak tárolva, és az összes elem körbevonásával lekérhetők. Ennek költsége az Tovább).

A Java 8-tól kezdve (lásd JEP 180) az adatstruktúra, amelyben az egy vödörben lévő értékek vannak tárolva, egy listáról kiegyensúlyozott fára változik, ha egy vödör 8 vagy több értéket tartalmaz, és visszaáll listára, ha, valamikor csak 6 érték marad a vödörben. Ez javítja a teljesítményt O (log n).

5.4. Kapacitás és terhelési tényező

Annak elkerülése érdekében, hogy sok, több értékű vödör legyen, a kapacitás megduplázódik, ha a vödrök 75% -a (terhelési tényező) nem üres. A terhelési tényező alapértelmezett értéke 75%, az alapértelmezett kezdeti kapacitás pedig 16. Mindkettő beállítható a konstruktorban.

5.5. Összefoglaló tedd és kap Tevékenységek

Foglaljuk össze, hogyan tedd és kap műveletek működnek.

Amikor hozzáadunk egy elemet a térképhez,HashMap kiszámítja a vödröt. Ha a vödör már tartalmaz értéket, az érték hozzáadódik az adott vödörhöz tartozó listához (vagy fához). Ha a terhelési tényező nagyobb lesz, mint a térkép maximális terhelési tényezője, akkor a kapacitás megduplázódik.

Amikor értéket akarunk kapni a térképről,HashMap kiszámítja a vödröt, és ugyanazzal a kulccsal megkapja az értéket a listából (vagy egy fáról).

6. Következtetés

Ebben a cikkben láttuk, hogyan kell használni a HashMap és hogyan működik belsőleg. Együtt Tömb lista, HashMap a Java egyik leggyakrabban használt adatstruktúrája, ezért nagyon hasznos, ha jól ismeri a használatát és működését a motorháztető alatt. A Java HashMap a motorháztető alatt című cikkünk a HashMap részletesebben.

Szokás szerint a teljes forráskód elérhető a Githubon.