streamalism.org

1. Prehľad

Mapy sú prirodzene jedným z najrozšírenejších štýlov zbierky Java.

A čo je dôležité, HashMap nie je implementácia bezpečná pre vlákna, zatiaľ čo Hashtable zaisťuje bezpečnosť vlákien synchronizáciou operácií.

Aj napriek tomu Hashtable je bezpečný pre vlákna, nie je veľmi efektívny. Ďalšia plne synchronizovaná Mapa,Collections.synchronizedMap, tiež nevykazuje veľkú účinnosť. Ak požadujeme bezpečnosť vlákien s vysokou priepustnosťou pri vysokej súbežnosti, tieto implementácie nie sú cestou.

Na vyriešenie problému, Rámec zbierok Javapredstavený ConcurrentMap v Java 1.5.

Nasledujúce diskusie sú založené na Java 1.8.

2. ConcurrentMap

ConcurrentMap je rozšírením Mapa rozhranie. Jeho cieľom je poskytnúť štruktúru a usmernenie pri riešení problému zosúladenia priepustnosti s bezpečnosťou vlákien.

Prepísaním niekoľkých predvolených metód rozhrania ConcurrentMap poskytuje pokyny pre platné implementácie, ktoré zabezpečujú atómové operácie spojené s bezpečnosťou vlákien a pamäťou.

Niekoľko predvolených implementácií je prepísaných a deaktivuje sa nulový podpora kľúč / hodnota:

• getOrDefault
• pre každý
• nahradiť všetko
• computeIfAbsent
• computeIfPresent
• vypočítať
• zlúčiť

Nasledujúci API sú tiež prepísané na podporu atomicity bez implementácie predvoleného rozhrania:

• putIfAbsent
• odstrániť
• replace (key, oldValue, newValue)
• nahradiť (kľúč, hodnota)

Ostatné akcie sa dedia priamo a v podstate sa zhodujú s Mapa.

3. ConcurrentHashMap

ConcurrentHashMap je pripravený na použitie ConcurrentMap implementácia.

Pre lepší výkon sa skladá z radu uzlov ako segmentov tabuľky (predtým boli segmentmi tabuľky) Java 8) pod kapotou a pri aktualizácii využíva hlavne operácie CAS.

Vedierka stola sa inicializujú lenivo pri prvom vložení. Každý segment je možné nezávisle uzamknúť uzamknutím úplne prvého uzla v segmente. Operácie čítania neblokujú a aktualizácie sa minimalizujú.

Počet požadovaných segmentov je relatívny k počtu vlákien pristupujúcich k tabuľke, takže prebiehajúca aktualizácia na segment nebude trvať dlhšie ako jednu väčšinu času.

Predtým Java 8, požadovaný počet „segmentov“ bol relatívny k počtu vlákien vstupujúcich do tabuľky, takže prebiehajúca aktualizácia na segment nebude trvať dlhšie ako jednu väčšinu času.

Preto v porovnaní s konštruktérmi HashMap, poskytuje príplatok concurrencyLevel argument na kontrolu počtu odhadovaných vlákien, ktoré sa majú použiť:

verejná ConcurrentHashMap (

public ConcurrentHashMap (int initialCapacity, float loadFactor, int concurrencyLevel)

Ďalšie dva argumenty: initialCapacity a vyťaženosť fungoval úplne rovnako ako HashMap.

Avšak od Java 8, konštruktory sú k dispozícii iba kvôli spätnej kompatibilite: parametre môžu ovplyvniť iba počiatočnú veľkosť mapy.

3.1. Bezpečnosť závitov

ConcurrentMap zaručuje konzistenciu pamäte pri operáciách kľúč / hodnota v prostredí s viacerými vláknami.

Akcie vo vlákne pred umiestnením objektu do a ConcurrentMap ako kľúč alebo hodnota stalo sa predtým akcie nasledujúce po prístupe alebo odstránení tohto objektu v inom vlákne.

Na potvrdenie sa pozrime na prípad nesúladu pamäte:

@Test public void givenHashMap_whenSumParallel_thenError () vyvolá výnimku {Map map = new HashMap (); Zoznam sumList = parallelSum100 (mapa, 100); assertNotEquals (1, sumList .stream () .distinct () .count ()); long wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertTrue (wrongResultCount> 0); } private List parallelSum100 (Map map, int executionTimes) throws InterruptedException {List sumList = new ArrayList (1000); for (int i = 0; i <executionTimes; i ++) {map.put ("test", 0); ExecutorService executorService = Executors.newFixedThreadPool (4); pre (int j = 0; j {pre (int k = 0; hodnota k + 1);}); } executorService.shutdown (); executorService.awaitTermination (5, TimeUnit.SECONDS); sumList.add (map.get ("test")); } vratit sumList; }

Pre každý map.computeIfPresent konať paralelne, HashMap neposkytuje konzistentný pohľad na to, čo by mala byť súčasná celočíselná hodnota, čo vedie k nekonzistentným a nežiaducim výsledkom.

Ako pre ConcurrentHashMap, môžeme získať konzistentný a správny výsledok:

@Test public void givenConcurrentMap_whenSumParallel_thenCorrect () vyvolá výnimku {Map map = new ConcurrentHashMap (); Zoznam sumList = parallelSum100 (mapa, 1000); assertEquals (1, sumList .stream () .distinct () .count ()); long wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertEquals (0, wrongResultCount); }

3.2. Nulový Kľúč / hodnota

Väčšina APIs poskytuje ConcurrentMap nepovoľuje nulový kľúč alebo hodnota, napríklad:

@Test (očakáva sa = NullPointerException.class) public void givenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE () {concurrentMap.put (null, new Object ()); } @Test (očakáva sa = NullPointerException.class) public void givenConcurrentHashMap_whenPutNullValue_thenThrowsNPE () {concurrentMap.put ("test", null); }

Avšak pre vypočítať * a zlúčiť akcie, vypočítaná hodnota môže byť nulový, čo znamená, že mapovanie kľúč - hodnota je odstránené, ak je prítomné, alebo zostáva neprítomné, ak predtým nebolo k dispozícii.

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

3.3. Podpora streamu

Java 8 poskytuje Prúd podpora v ConcurrentHashMap tiež.

Na rozdiel od väčšiny prúdových metód hromadné (postupné a paralelné) operácie umožňujú bezpečnú súbežnú úpravu. ConcurrentModificationException nebude vyhodená, čo platí aj pre jej iterátory. Relevantné pre prúdy, niekoľko pre každý*, Vyhľadávaniea zmenšiť * pridávajú sa tiež metódy na podporu bohatších operácií prechodu a zmenšenia mapy.

3.4. Výkon

Pod kapotou, ConcurrentHashMap je niečo podobné ako HashMap, s prístupom k údajom a ich aktualizáciou na základe hašovacej tabuľky (aj keď zložitejšej).

A samozrejme, ConcurrentHashMap by vo väčšine súbežných prípadov malo priniesť oveľa lepší výkon pri načítaní a aktualizácii údajov.

Napíšme rýchly mikro-benchmark pre dostať a dať výkon a porovnaj to s Hashtable a Zbierky.synchronizovanáMapa, pričom obe operácie bežia 500 000-krát v 4 vláknach.

@Test public void givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster () vyvolá výnimku {Map hashtable = new Hashtable (); Mapa synchronizedHashMap = Collections.synchronizedMap (nový HashMap ()); Mapa concurrentHashMap = nová ConcurrentHashMap (); long hashtableAvgRuntime = timeElapseForGetPut (hashtable); long syncHashMapAvgRuntime = timeElapseForGetPut (synchronizedHashMap); long concurrentHashMapAvgRuntime = timeElapseForGetPut (concurrentHashMap); assertTrue (hashtableAvgRuntime> concurrentHashMapAvgRuntime); assertTrue (syncHashMapAvgRuntime> concurrentHashMapAvgRuntime); } private long timeElapseForGetPut (mapa mapy) hodí InterruptedException {ExecutorService executorService = Executors.newFixedThreadPool (4); long startTime = System.nanoTime (); for (int i = 0; i {for (int j = 0; j <500_000; j ++) {int value = ThreadLocalRandom .current () .nextInt (10 000); String key = String.valueOf (value); map.put (kľúč, hodnota); map.get (kľúč);}}); } executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); návrat (System.nanoTime () - startTime) / 500_000; }

Pamätajte, že mikro-referenčné hodnoty sa pozerajú iba na jediný scenár a nie vždy sú dobrým odrazom výkonu v reálnom svete.

To znamená, že na systéme OS X s priemerným systémom dev vidíme priemerný výsledok vzorky za 100 po sebe idúcich behov (v nanosekundách):

Hashtable: 1142,45 SynchronizedHashMap: 1273,89 ConcurrentHashMap: 230,2

V prostredí s viacerými vláknami, kde sa od viacerých vlákien očakáva prístup k spoločnému Mapa, ConcurrentHashMap je jednoznačne výhodnejšia.

Keď však Mapa je prístupný iba pre jedno vlákno, HashMap môže byť lepšou voľbou pre jeho jednoduchosť a solídny výkon.

3.5. Úskalia

Operácie načítania sa spravidla neblokujú ConcurrentHashMap a mohli by sa prekrývať s operáciami aktualizácie. Pre lepšiu výkonnosť teda odrážajú iba výsledky naposledy dokončených aktualizácií, ako je uvedené v oficiálnom dokumente Javadoc.

Je potrebné mať na pamäti niekoľko ďalších skutočností:

• výsledky metód súhrnného stavu vrátane veľkosť, je prázdnya containsValue sú zvyčajne užitočné iba v prípade, že mapa nepodlieha súbežným aktualizáciám v iných vláknach:

@ Test public void givenConcurrentMap_whenUpdatingAndGetSize_thenError () vyvolá InterruptedException {Runnable collectMapSizes = () -> {for (int i = 0; i {for (int i = 0; i <MAX_SIZE; i ++) {concurrentMap.put (String.valueOval (String.valueOval) ), i);}}; executorService.execute (updateMapData); executorService.execute (collectMapSizes); executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); assertNotEquals (MAX_SIZE, mapSizes.get (1) ) .intValue ()); assertEquals (MAX_SIZE, concurrentMap.size ());}

Ak súbežné aktualizácie podliehajú prísnej kontrole, súhrnný stav by bol stále spoľahlivý.

Aj keď tieto Metódy súhrnného stavu nezaručujú presnosť v reálnom čase, môžu byť postačujúce na účely monitorovania alebo odhadu.

Všimnite si, že použitie veľkosť () z ConcurrentHashMap by mal byť nahradený mappingCount (), pre druhú metódu vracia a dlho počítať, aj keď sú v hĺbke založené na rovnakom odhade.

• hashCode záleží: všimnite si, že používanie mnohých klávesov s úplne rovnakými hashCode () je bezpečný spôsob, ako spomaliť výkon akejkoľvek hashovacej tabuľky.

Na zlepšenie dopadu, keď sú klávesy Porovnateľné, ConcurrentHashMap môže použiť poradie porovnávania medzi kľúčmi na pomoc pri zlomení väzieb. Napriek tomu by sme sa mali vyhnúť použitiu toho istého hashCode () ako môžeme.

• iterátory sú navrhnuté iba na použitie v jednom vlákne, pretože poskytujú slabú konzistenciu namiesto rýchleho zlyhania a nikdy nebudú hádzať ConcurrentModificationException.
• predvolená počiatočná kapacita tabuľky je 16 a je upravená o zadanú úroveň súbežnosti:

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

• opatrnosť pri premapovaní funkcií: aj keď môžeme vykonávať operácie premapovania pomocou poskytnutých vypočítať a zlúčiť* metódy, mali by sme ich udržiavať rýchle, krátke a jednoduché a zamerať sa na aktuálne mapovanie, aby sme sa vyhli neočakávanému blokovaniu.
• kľúče v ConcurrentHashMap nie sú zoradené, takže pre prípady, keď je objednávka požadovaná, ConcurrentSkipListMap je vhodná voľba.

4. ConcurrentNavigableMap

V prípade, že je potrebné objednať kľúče, môžeme použiť ConcurrentSkipListMap, súbežná verzia TreeMap.

Ako doplnok k ConcurrentMap, ConcurrentNavigableMap podporuje celkové poradie jeho klávesov (v predvolenom nastavení vzostupne) a je súčasne navigovateľný. Metódy, ktoré vracajú zobrazenia mapy, sú prepísané kvôli kompatibilite súbežnosti:

• čiastková mapa
• headMap
• tailMap
• čiastková mapa
• headMap
• tailMap
• zostupneMapa

keySet () iterátory a rozdeľovače pohľadov sú vylepšené o konzistenciu so slabou pamäťou:

• navigableKeySet
• keySet
• descendingKeySet

5. ConcurrentSkipListMap

Predtým sme pokryli NavigableMap rozhranie a jeho implementácia TreeMap. ConcurrentSkipListMap je vidieť škálovateľnú súbežnú verziu TreeMap.

V praxi neexistuje žiadna súbežná implementácia červeno-čierneho stromu v Jave. Súbežný variant SkipLists je implementovaný v ConcurrentSkipListMap, ktoré poskytujú očakávané priemerné náklady na protokol (n) v čase containsKey, dostať, dať a odstrániť operácie a ich varianty.

Okrem tohoto TreeMapFunkcie, vkladanie, vyberanie, aktualizácia a prístup k kľúčom sú zaručené vďaka bezpečnosti vlákien. Tu je porovnanie s TreeMap pri súčasnej navigácii:

@ Test public void givenSkipListMap_whenNavConcurrently_thenCountCorrect () vyvolá InterruptedException {NavigableMap skipListMap = nový ConcurrentSkipListMap (); int count = countMapElementByPollingFirstEntry (skipListMap, 10 000, 4); assertEquals (10 000 * 4, počet); } @Test public void givenTreeMap_whenNavConcurrently_thenCountError () vyvolá InterruptedException {NavigableMap treeMap = new TreeMap (); int count = countMapElementByPollingFirstEntry (treeMap, 10 000, 4); assertNotEquals (10 000 * 4, počet); } private int countMapElementByPollingFirstEntry (NavigableMap navigableMap, int elementCount, int concurrencyLevel) hodí InterruptedException {for (int i = 0; i <elementCount * concurrencyLevel; i ++) {navigableMap.put (i, i); } Počítadlo AtomicInteger = nový AtomicInteger (0); ExecutorService executorService = Executors.newFixedThreadPool (concurrencyLevel); for (int j = 0; j {for (int i = 0; i <elementCount; i ++) {if (navigableMap.pollFirstEntry ()! = null) {counter.incrementAndGet ();}}}); } executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); návrat counter.get (); }

Úplné vysvetlenie zákulisia týkajúceho sa výkonu presahuje rámec tohto článku. Podrobnosti nájdete v ConcurrentSkipListMap Javadoc, ktorý sa nachádza pod java / util / súbežné v src.zip spis.

6. Záver

V tomto článku sme predstavili hlavne súbor ConcurrentMap rozhranie a vlastnosti ConcurrentHashMap a zakryté ConcurrentNavigableMap vyžaduje sa objednávanie kľúčov.

Celý zdrojový kód všetkých príkladov použitých v tomto článku nájdete v projekte GitHub.