streamalism.org

1. Áttekintés

Térképek természetesen a Java gyűjtemény egyik legszélesebb stílusa.

És ami fontos, HashMap nem egy szálbiztos megvalósítás, míg Hashtable szálbiztonságot nyújt a műveletek szinkronizálásával.

Annak ellenére Hashtable szálbiztos, nem túl hatékony. Egy másik teljesen szinkronizált Térkép,Collections.synchronizedMap, sem mutat nagy hatékonyságot. Ha nagy biztonsággal, nagy egyidejűséggel rendelkező szálbiztonságot akarunk, akkor ezek a megvalósítások nem a megfelelő út.

A probléma megoldása érdekében a Java Collections Frameworkbemutatott ConcurrentMap ban ben Java 1.5.

A következő viták a következőkön alapulnak Java 1.8.

2. ConcurrentMap

ConcurrentMap kiterjesztése a Térkép felület. Célja, hogy struktúrát és útmutatást nyújtson az áteresztőképesség és a menetbiztonság összeegyeztetésének problémájához.

Több felületi alapértelmezett módszer felülírásával ConcurrentMap útmutatásokat ad az érvényes megvalósításokról a szálbiztonság és az emlékezet-konzisztens atomi műveletek biztosítása érdekében.

Számos alapértelmezett megvalósítást felülírnak, letiltva a nulla kulcs / érték támogatás:

• getOrDefault
• az egyes
• csereAll
• computeIfAbsent
• computeIfPresent
• kiszámít
• összeolvad

A következő API-k szintén felülírják az atomitás támogatását, alapértelmezett interfész-megvalósítás nélkül:

• putIfAbsent
• eltávolítani
• csere (kulcs, oldValue, newValue)
• csere (kulcs, érték)

A többi művelet közvetlenül öröklődik, és alapvetően összhangban áll a következőkkel Térkép.

3. ConcurrentHashMap

ConcurrentHashMap készen van a dobozon kívül ConcurrentMap végrehajtás.

A jobb teljesítmény érdekében csomópontok tömbjéből áll, mint táblázatcsomagok (korábban táblaszegmensek voltak előtte Java 8) a motorháztető alatt, és főleg a CAS műveleteket használja a frissítés során.

Az asztali vödrök lustán inicializálódnak, az első behelyezés után. Minden vödör függetlenül zárható, ha a vödör legelső csomópontját lezárja. Az olvasási műveletek nem blokkolják, és a frissítési tartalmak minimalizálódnak.

A szükséges szegmensek száma a táblához hozzáférő szálak számához viszonyítva van, így a folyamatban lévő frissítés szegmensenként legfeljebb egy lehet.

Előtt Java 8, a szükséges „szegmensek” száma a táblához hozzáférő szálak számához viszonyítva volt, így a folyamatban lévő frissítés szegmensenként nem több, mint egy.

Ezért a kivitelezők ehhez képest HashMap, biztosítja az extrát concurrencyLevel argumentum a becsült felhasználandó szálak számának ellenőrzésére:

public ConcurrentHashMap (

public ConcurrentHashMap (int kezdeti kapacitás, úszó terhelés tényező, int egyidejűség szint)

A másik két érv: kezdeti Kapacitás és terhelési tényező ugyanúgy dolgozott, mint HashMap.

Mivel azonban Java 8, a konstruktorok csak a visszamenőleges kompatibilitás miatt vannak jelen: a paraméterek csak a térkép kezdeti méretét befolyásolhatják.

3.1. Menetbiztonság

ConcurrentMap garantálja a memória konzisztenciáját a kulcs / érték műveleteknél több szálú környezetben.

Műveletek egy szálban, mielőtt egy objektumot a ConcurrentMap mint kulcs vagy érték történés előtt az objektum egy másik szálban való elérését vagy eltávolítását követő műveletek.

Ennek megerősítéséhez nézzünk meg egy memória-inkonzisztens esetet:

@Test public void givenHashMap_whenSumParallel_thenError () dobja a Kivételt {Map map = new HashMap (); Lista sumList = parallelSum100 (térkép, 100); assertNotEquals (1, sumList .stream () .distinct () .count ()); long wrongResultCount = sumList .stream () .filter (szám -> szám! = 100) .szám (); assertTrue (falseResultCount> 0); } privát Lista parallelSum100 (Térképtérkép, int végrehajtási idő) dobja az InterruptedException {List sumList = new ArrayList (1000); for (int i = 0; i <végrehajtási idők; i ++) {map.put ("teszt", 0); ExecutorService végrehajtóService = Executors.newFixedThreadPool (4); for (int j = 0; j {for (int k = 0; k értéke + 1);}); } executorService.shutdown (); végrehajtóService.awaitTermination (5, TimeUnit.SECONDS); sumList.add (map.get ("teszt")); } return sumList; }

Az egyes map.computeIfPresent párhuzamos cselekvés, HashMap nem ad következetes képet arról, hogy mi legyen a jelenlegi egész érték, ami következetlen és nemkívánatos eredményekhez vezet.

Ami ConcurrentHashMap, következetes és korrekt eredményt kaphatunk:

@Test public void givenConcurrentMap_whenSumParallel_thenCorrect () dobja a Kivételt {Map map = new ConcurrentHashMap (); Lista sumList = parallelSum100 (térkép, 1000); assertEquals (1, sumList .stream () .distinct () .count ()); long wrongResultCount = sumList .stream () .filter (szám -> szám! = 100) .szám (); assertEquals (0, falseResultCount); }

3.2. Nulla Kulcs érték

A legtöbb APIs által biztosított ConcurrentMap nem teszi lehetővé nulla kulcs vagy érték, például:

@Test (várható = NullPointerException.class) public void givenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE () {concurrentMap.put (null, new Object ()); } @Test (várható = NullPointerException.class) public void givenConcurrentHashMap_whenPutNullValue_thenThrowsNPE () {concurrentMap.put ("test", null); }

Azonban, mert kiszámít* és összeolvad műveletek esetén a kiszámított érték lehet nulla, amely azt jelzi, hogy a kulcs-érték leképezés eltávolításra kerül, ha van, vagy hiányzik, ha korábban hiányzott.

@Test public void givenKeyPresent_whenComputeRemappingNull_thenMappingRemoved () {Object oldValue = new Object (); concurrentMap.put ("teszt", oldValue); concurrentMap.compute ("teszt", (s, o) -> null); assertNull (concurrentMap.get ("teszt")); }

3.3. Adatfolyam támogatás

Java 8 biztosítja Folyam támogatás a ConcurrentHashMap is.

A legtöbb stream módszerrel ellentétben a tömeges (szekvenciális és párhuzamos) műveletek biztonságosan lehetővé teszik az egyidejű módosítást. ConcurrentModificationException nem dobják el, ami az iterátorokra is vonatkozik. Patakokhoz kapcsolódóan több az egyes*, keresés, és csökkenteni * módszerek is hozzáadódnak a gazdagabb bejáráshoz és a térképcsökkentéshez.

3.4. Teljesítmény

A motorháztető alatt, ConcurrentHashMap némileg hasonló a HashMap, adateléréssel és hash-tábla alapján történő frissítéssel (bár összetettebb).

És természetesen a ConcurrentHashMap sokkal jobb teljesítményt kell nyújtania a legtöbb egyidejű esetben az adatok visszakeresése és frissítése érdekében.

Írjunk egy gyors mikro-benchmarkot a kap és tedd teljesítményét, és hasonlítsa össze azzal Hashtable és Collections.synchronizedMap, mindkét műveletet 500 000-szer futtatva 4 szálon.

@Test public void givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster () dobja a Kivételt {Map hashtable = new Hashtable (); Map synchronizedHashMap = Collections.synchronizedMap (új HashMap ()); Map concurrentHashMap = new ConcurrentHashMap (); long hashtableAvgRuntime = timeElapseForGetPut (hashtable); hosszú syncHashMapAvgRuntime = timeElapseForGetPut (synchronizedHashMap); long concurrentHashMapAvgRuntime = timeElapseForGetPut (concurrentHashMap); assertTrue (hashtableAvgRuntime> concurrentHashMapAvgRuntime); assertTrue (syncHashMapAvgRuntime> concurrentHashMapAvgRuntime); } privát long timeElapseForGetPut (térképes térkép) dobja az InterruptedException {ExecutorService végrehajtóService = Executors.newFixedThreadPool (4); hosszú startTime = System.nanoTime (); for (int i = 0; i {for (int j = 0; j <500_000; j ++) {int érték = ThreadLocalRandom .current () .nextInt (10000); String kulcs = String.valueOf (érték); map.put (kulcs, érték); map.get (kulcs);}}); } executorService.shutdown (); végrehajtóService.awaitTermination (1, TimeUnit.MINUTES); return (System.nanoTime () - startTime) / 500_000; }

Ne feledje, hogy a mikro-benchmarkok csak egyetlen forgatókönyvet vizsgálnak, és nem mindig tükrözik jól a valós teljesítményt.

Ez azt jelenti, hogy egy átlagos dev rendszerű OS X rendszeren 100 egymást követő futás átlagmintáját látjuk (nanoszekundumban):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

Többszálas környezetben, ahol több szál várhatóan hozzáfér egy közöshez Térkép, a ConcurrentHashMap egyértelműen előnyösebb.

Amikor azonban a Térkép csak egyetlen szálhoz érhető el, HashMap jobb választás lehet egyszerűsége és szilárd teljesítménye miatt.

3.5. Buktatók

A visszakeresési műveletek általában nem blokkolják ConcurrentHashMap és átfedhetik a frissítési műveletekkel. Tehát a jobb teljesítmény érdekében csak a legfrissebb frissítési műveletek eredményeit tükrözik, amint azt a hivatalos Javadoc is kimondta.

Számos egyéb tényt kell szem előtt tartani:

• összesített állapot-módszerek eredményei, beleértve méret, üres, és tartalmazzaValue általában csak akkor hasznosak, ha a térképen nem zajlik egyidejű frissítés más szálakban:

A @Test public void givenConcurrentMap_whenUpdatingAndGetSize_thenError () dobja az InterruptedException {Runnable collectMapSizes = () -> {for (int i = 0; i {for (int i = 0; i <MAX_SIZE; i ++) {concurrentMap.put (String. ), i);}}; végrehajtóService.execute (updateMapData); végrehajtóService.execute (collectMapSizes); végrehajtóService.shutdown (); végrehajtóService.awaitTermination (1, TimeUnit.MINUTES); assertNotEquals (MAX_SIZE - 1 ) .intValue ()); assertEquals (MAX_SIZE, concurrentMap.size ());}

Ha az egyidejű frissítéseket szigorú ellenőrzés alatt tartják, az összesített állapot továbbra is megbízható.

Bár ezek az összesített státusz-módszerek nem garantálják a valós idejű pontosságot, monitoring vagy becslés céljából megfelelőek lehetnek.

Vegye figyelembe, hogy a méret() nak,-nek ConcurrentHashMap helyébe a következő lép: mappingCount (), az utóbbi módszerhez a hosszú bár mélyen ugyanazon a becslésen alapulnak.

• hash kód számít: vegye figyelembe, hogy sok, pontosan ugyanolyan billentyűt használ hash kód() biztos módja bármely hash tábla teljesítményének lelassítására.

A hatás enyhítésére, amikor a kulcsok vannak Hasonló, ConcurrentHashMap összehasonlítási sorrendet használhat a kulcsok között a kapcsolatok megszakításához. Ennek ellenére kerülnünk kell ugyanezt hash kód() amennyit csak tudunk.

• az iterátorokat csak egyetlen szálon történő használatra tervezték, mivel gyenge konzisztenciát nyújtanak, nem pedig gyorsan elbukó átmenetet, és soha nem fognak dobni ConcurrentModificationException.
• az alapértelmezett kezdeti táblázatkapacitás 16, és a megadott egyidejűségi szint módosítja:

public ConcurrentHashMap (int kezdetiCapacity, float loadFactor, int concurrencyLevel) {// ... if (initialCapacity <concurrencyLevel) {initialCapacity = concurrencyLevel; } // ...}

• óvatosság a funkciók újratervezésével kapcsolatban: bár a feltöltéssel elvégezhetünk újratervezési műveleteket kiszámít és összeolvad* módszereket, ezeket gyorsnak, rövidnek és egyszerűnek kell tartanunk, és a váratlan blokkolás elkerülése érdekében az aktuális feltérképezésre kell összpontosítanunk.
• kulcsok ConcurrentHashMap nincsenek rendezve, ezért azokban az esetekben, amikor megrendelésre van szükség, ConcurrentSkipListMap megfelelő választás.

4. ConcurrentNavigableMap

Olyan esetekben, amikor kulcsok megrendelésére van szükség, használhatjuk ConcurrentSkipListMap, egyidejű változata TreeMap.

Kiegészítésként a ConcurrentMap, ConcurrentNavigableMap támogatja a kulcsok teljes rendezését (alapértelmezés szerint növekvő sorrendben), és egyidejűleg navigálható. A párhuzamosság kompatibilitása felülbírálja a térkép nézeteit visszaadó módszereket:

• subMap
• headMap
• tailMap
• subMap
• headMap
• tailMap
• csökkenő térkép

keySet () A nézetek iterátorait és elosztóit gyengébb memória-konzisztencia jellemzi:

• navigableKeySet
• keySet
• descendingKeySet

5. ConcurrentSkipListMap

Korábban már kitértünk rá NavigableMap felület és annak megvalósítása TreeMap. ConcurrentSkipListMap a skálázható egyidejű változata látható TreeMap.

A gyakorlatban a vörös-fekete fa egyidejű megvalósítása nincs a Java-ban. A. Egyidejű változata SkipLists évben kerül végrehajtásra ConcurrentSkipListMap, megadva a várható átlagos log (n) időköltséget a tartalmazzaKey, kap, tedd és eltávolítani műveletek és változataik.

Továbbá TreeMapA szálbiztonság garantálja a funkciókat, a kulcs behelyezését, eltávolítását, frissítését és elérését. Itt van egy összehasonlítás a következővel: TreeMap ha egyszerre navigál:

@Test public void givenSkipListMap_whenNavConcurrently_thenCountCorrect () dob InterruptedException {NavigableMap skipListMap = new ConcurrentSkipListMap (); int count = countMapElementByPollingFirstEntry (skipListMap, 10000, 4); assertEquals (10000 * 4, szám); } @Test public void givenTreeMap_whenNavConcurrently_thenCountError () dobja az InterruptedException {NavigableMap treeMap = új TreeMap (); int count = countMapElementByPollingFirstEntry (treeMap, 10000, 4); assertNotEquals (10000 * 4, szám); } private int countMapElementByPollingFirstEntry (NavigableMap navigableMap, int elementCount, int concurrencyLevel) dobja az InterruptedException {for (int i = 0; i <elementCount * concurrencyLevel; i ++) {navigableMap.put (i, i); } AtomicInteger számláló = új AtomicInteger (0); ExecutorService végrehajtóService = Executors.newFixedThreadPool (concurrencyLevel); for (int j = 0; j {for (int i = 0; i <elementCount; i ++) {if (navigableMap.pollFirstEntry ()! = null) {counter.incrementAndGet ();}}}}; } executorService.shutdown (); végrehajtóService.awaitTermination (1, TimeUnit.MINUTES); return counter.get (); }

A színfalak mögötti előadások teljes körű magyarázata meghaladja a cikk kereteit. A részletek megtalálhatók itt: ConcurrentSkipListMap's Javadoc, amely alatt található java / util / concurrent ban,-ben src.zip fájl.

6. Következtetés

Ebben a cikkben elsősorban a ConcurrentMap interfész és a ConcurrentHashMap és be van takarva ConcurrentNavigableMap kulcsrendelés szükséges.

A cikkben használt összes példa teljes forráskódja megtalálható a GitHub projektben.