streamalism.org

1. Oversigt

Kort er naturligvis en af ​​de mest almindelige Java-samlinger.

Og vigtigst af alt HashMap er ikke en trådsikker implementering, mens Hashtable giver tråd-sikkerhed ved at synkronisere operationer.

Selv om Hashtable er trådsikker, det er ikke særlig effektivt. En anden fuldt synkroniseret Kort,Collections.synchronizedMap, udviser heller ikke stor effektivitet. Hvis vi ønsker trådsikkerhed med høj kapacitet under høj samtidighed, er disse implementeringer ikke vejen at gå.

For at løse problemet er Java Collections Frameworkintroduceret ConcurrentMap i Java 1.5.

De følgende diskussioner er baseret på Java 1.8.

2. ConcurrentMap

ConcurrentMap er en udvidelse af Kort interface. Det sigter mod at give en struktur og vejledning til løsning af problemet med at forene kapacitet med trådsikkerhed.

Ved at tilsidesætte flere standardgrænseflademetoder, ConcurrentMap giver retningslinjer for gyldige implementeringer for at give trådsikkerhed og hukommelseskonsistente atomoperationer.

Flere standardimplementeringer tilsidesættes, hvilket deaktiverer nul nøgle / værdi support:

• getOrDefault
• for hver
• udskift alle
• ComputeIfAbsent
• computeIfPresent
• beregne
• fusionere

Det følgende API'er er også tilsidesat for at understøtte atomicitet uden en standard interfaceimplementering:

• putIfAbsent
• fjerne
• udskift (nøgle, oldValue, newValue)
• udskift (nøgle, værdi)

Resten af ​​handlinger arves direkte med grundlæggende i overensstemmelse med Kort.

3. ConcurrentHashMap

ConcurrentHashMap er out-of-box klar ConcurrentMap implementering.

For bedre ydeevne består den af ​​en række noder som bordspande (plejede at være bordsegmenter før Java 8) under emhætten og bruger hovedsageligt CAS-operationer under opdatering.

Bordspandene initialiseres doven ved første isætning. Hver spand kan låses uafhængigt ved at låse den allerførste knude i spanden. Læseoperationer blokerer ikke, og opdateringsstridigheder minimeres.

Antallet af krævede segmenter er i forhold til antallet af tråde, der får adgang til tabellen, således at den igangværende opdatering pr. Segment ikke vil være mere end én det meste af tiden.

Før Java 8, antallet af "segmenter", der kræves, var i forhold til antallet af tråde, der fik adgang til tabellen, således at den opdatering, der er i gang pr. segment, ikke skal være mere end én det meste af tiden.

Derfor er konstruktører sammenlignet med HashMap, giver ekstra concurrencyNiveau argument for at kontrollere antallet af estimerede tråde, der skal bruges:

offentlig ConcurrentHashMap (

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

De to andre argumenter: initialCapacity og belastningsfaktor arbejdede helt det samme som HashMap.

Men siden Java 8, konstruktørerne er kun til stede for bagudkompatibilitet: parametrene kan kun påvirke kortets indledende størrelse.

3.1. Trådsikkerhed

ConcurrentMap garanterer hukommelseskonsistens på nøgle- / værdihandlinger i et multi-threading-miljø.

Handlinger i en tråd, inden en genstand placeres i en ConcurrentMap som en nøgle eller værdi ske før handlinger efter adgang til eller fjernelse af objektet i en anden tråd.

For at bekræfte, lad os se på en hukommelseskonsekvent sag:

@Test offentlig ugyldighed givenHashMap_whenSumParallel_thenError () kaster undtagelse {Map map = new HashMap (); Liste sumList = parallelSum100 (kort, 100); assertNotEquals (1, sumList .stream () .distinct () .count ()); lang wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertTrue (wrongResultCount> 0); } privat liste parallelSum100 (Map map, int executTimes) kaster InterruptedException {List sumList = new ArrayList (1000); til (int i = 0; i <executTimes; i ++) {map.put ("test", 0); ExecutorService executorService = Executors.newFixedThreadPool (4); for (int j = 0; j {for (int k = 0; k værdi + 1);}); } executorService.shutdown (); executorService.awaitTermination (5, TimeUnit.SECONDS); sumList.add (map.get ("test")); } returner sumList; }

For hver map.computeIfPresent handling parallelt, HashMap giver ikke et konsistent billede af, hvad der skal være den nuværende heltal, hvilket fører til inkonsekvente og uønskede resultater.

Som for ConcurrentHashMap, kan vi få et konsekvent og korrekt resultat:

@Test offentlig ugyldighed givenConcurrentMap_whenSumParallel_thenCorrect () kaster undtagelse {Map map = new ConcurrentHashMap (); Liste sumList = parallelSum100 (kort, 1000); assertEquals (1, sumList .stream () .distinct () .count ()); lang wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertEquals (0, wrongResultCount); }

3.2. Nul Nøgle / værdi

Mest APIs leveret af ConcurrentMap tillader ikke nul nøgle eller værdi, for eksempel:

@Test (forventet = NullPointerException.class) offentlig ugyldighed givenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE () {concurrentMap.put (null, nyt objekt ()); } @Test (forventet = NullPointerException.class) offentlig ugyldighed givenConcurrentHashMap_whenPutNullValue_thenThrowsNPE () {concurrentMap.put ("test", null); }

Imidlertid, til beregne * og fusionere handlinger, kan den beregnede værdi være nul, som angiver, at nøgleværdikortlægningen fjernes, hvis den er til stede eller forbliver fraværende, hvis den tidligere er fraværende.

@Test offentlig ugyldighed givetKeyPresent_whenComputeRemappingNull_thenMappingRemoved () {Object oldValue = nyt objekt (); concurrentMap.put ("test", oldValue); concurrentMap.compute ("test", (s, o) -> null); assertNull (concurrentMap.get ("test")); }

3.3. Streamsupport

Java 8 giver Strøm støtte i ConcurrentHashMap såvel.

I modsætning til de fleste streammetoder tillader bulk (sekventielle og parallelle) operationer samtidig ændring sikkert. ConcurrentModificationException vil ikke blive kastet, hvilket også gælder for dets iteratorer. Relevant for streams, flere for hver*, Søgog reducere* Metoder tilføjes også for at understøtte mere gennemgribende og kortreducerende operationer.

3.4. Ydeevne

Under kølerhjelmen, ConcurrentHashMap ligner noget HashMap, med dataadgang og opdatering baseret på en hash-tabel (dog mere kompleks).

Og selvfølgelig ConcurrentHashMap skulle give langt bedre ydeevne i de fleste samtidige tilfælde til datahentning og opdatering.

Lad os skrive et hurtigt mikro-benchmark for få og sætte ydeevne og sammenlign det med Hashtable og Collections.synchronizedMap, kører begge operationer 500.000 gange i 4 tråde.

@Test offentlig ugyldighed givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster () kaster Undtagelse {Map hashtable = new Hashtable (); Kort synchronizedHashMap = Collections.synchronizedMap (nyt HashMap ()); Kort concurrentHashMap = ny ConcurrentHashMap (); lang hashtableAvgRuntime = timeElapseForGetPut (hashtable); lang syncHashMapAvgRuntime = timeElapseForGetPut (synkroniseretHashMap); lang concurrentHashMapAvgRuntime = timeElapseForGetPut (concurrentHashMap); assertTrue (hashtableAvgRuntime> concurrentHashMapAvgRuntime); assertTrue (syncHashMapAvgRuntime> concurrentHashMapAvgRuntime); } privat lang timeElapseForGetPut (kortkort) kaster InterruptedException {ExecutorService executorService = Executors.newFixedThreadPool (4); lang starttid = System.nanoTime (); for (int i = 0; i {for (int j = 0; j <500_000; j ++) {int value = ThreadLocalRandom .current () .nextInt (10000); String key = String.valueOf (value); map.put (nøgle, værdi); map.get (nøgle);}}); } executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); returnere (System.nanoTime () - startTime) / 500_000; }

Husk, at mikrobenchmarks kun ser på et enkelt scenarie og ikke altid er en god afspejling af den virkelige verdens ydeevne.

Når det er sagt, på et OS X-system med et gennemsnitligt dev-system ser vi et gennemsnitligt prøveresultat i 100 på hinanden følgende kørsler (i nanosekunder):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

I et miljø med flere tråde, hvor flere tråde forventes at få adgang til et fælles Kort, det ConcurrentHashMap er klart at foretrække.

Men når den Kort er kun tilgængelig for en enkelt tråd, HashMap kan være et bedre valg for sin enkelhed og solide ydeevne.

3.5. Faldgruber

Hentningsoperationer blokerer generelt ikke ConcurrentHashMap og kunne overlappe med opdateringshandlinger. Så for bedre ydeevne afspejler de kun resultaterne af de senest gennemførte opdateringsoperationer, som anført i den officielle Javadoc.

Der er flere andre fakta at huske på:

• resultater af samlede statusmetoder inklusive størrelse, er tomog indeholder værdi er typisk kun nyttige, når et kort ikke gennemgår samtidige opdateringer i andre tråde:

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

Hvis samtidige opdateringer er under streng kontrol, vil samlet status stadig være pålidelig.

Selvom disse samlede statusmetoder garanterer ikke realtidsnøjagtigheden, de kan være tilstrækkelige til overvågnings- eller estimeringsformål.

Bemærk, at brug af størrelse() af ConcurrentHashMap bør erstattes af mappingCount (), for sidstnævnte metode returnerer a lang tælle, selvom de dybt nede er baseret på det samme skøn.

• hashCode betyder noget: Bemærk, at du bruger mange taster med nøjagtigt det samme hashCode () er en sikker måde at bremse ydeevnen på enhver hash-tabel.

For at forbedre påvirkningen, når nøglerne er Sammenlignelig, ConcurrentHashMap kan bruge sammenligningsrækkefølge blandt nøgler for at hjælpe med at bryde bånd. Alligevel bør vi undgå at bruge det samme hashCode () så meget som vi kan.

• iteratorer er kun designet til at blive brugt i en enkelt tråd, da de giver svag konsistens snarere end hurtig fail-traversal, og de vil aldrig kaste ConcurrentModificationException.
• den oprindelige standardtabellekapacitet er 16, og den justeres efter det angivne samtidighedsniveau:

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

• forsigtighed ved omkortning af funktioner: skønt vi kan foretage omlægning med de medfølgende beregne og fusionere* metoder, skal vi holde dem hurtige, korte og enkle og fokusere på den aktuelle kortlægning for at undgå uventet blokering.
• nøgler ind ConcurrentHashMap er ikke i sorteret rækkefølge, så i tilfælde, hvor bestilling er påkrævet, ConcurrentSkipListMap er et passende valg.

4. ConcurrentNavigableMap

I tilfælde hvor bestilling af nøgler er påkrævet, kan vi bruge ConcurrentSkipListMap, en samtidig version af TreeMap.

Som et supplement til ConcurrentMap, ConcurrentNavigableMap understøtter total ordning af dens nøgler (i stigende rækkefølge som standard) og er samtidig navigerbar. Metoder, der returnerer visninger af kortet, tilsidesættes af hensyn til samtidighedskompatibilitet:

• underkort
• headMap
• hale kort
• underkort
• headMap
• hale kort
• faldende kort

keySet () visnings iteratorer og spliteratorer forbedres med svag hukommelseskonsistens:

• navigableKeySet
• keySet
• descendingKeySet

5. ConcurrentSkipListMap

Tidligere har vi dækket NavigableMap interface og dets implementering TreeMap. ConcurrentSkipListMap kan ses en skalerbar samtidig version af TreeMap.

I praksis er der ingen samtidig implementering af det rød-sorte træ i Java. En samtidig variant af SkipLister er implementeret i ConcurrentSkipListMap, der giver en forventet gennemsnitlig log (n) tidsomkostning for indeholderKey, få, sætte og fjerne operationer og deres varianter.

I tillæg til TreeMap'S funktioner, nøgleindsættelse, fjernelse, opdatering og adgangsoperationer er garanteret med trådsikkerhed. Her er en sammenligning med TreeMap når du navigerer samtidigt:

@Test offentlig ugyldighed givenSkipListMap_whenNavConcurrently_thenCountCorrect () kaster InterruptedException {NavigableMap skipListMap = new ConcurrentSkipListMap (); int count = countMapElementByPollingFirstEntry (skipListMap, 10000, 4); assertEquals (10000 * 4, count); } @Test offentlig ugyldighed givenTreeMap_whenNavConcurrently_thenCountError () kaster InterruptedException {NavigableMap treeMap = new TreeMap (); int count = countMapElementByPollingFirstEntry (treeMap, 10000, 4); assertNotEquals (10000 * 4, count); } private int countMapElementByPollingFirstEntry (NavigableMap navigableMap, int elementCount, int concurrencyLevel) kaster InterruptedException {for (int i = 0; i <elementCount * concurrencyLevel; i ++) {navigableMap.put (i, i); } AtomicInteger-tæller = nyt 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); return counter.get (); }

En fuld forklaring af forestillingsproblemerne bag kulisserne ligger uden for denne artikels anvendelsesområde. Detaljerne kan findes i ConcurrentSkipListMap's Javadoc, som ligger under java / util / samtidig i src.zip fil.

6. Konklusion

I denne artikel introducerede vi hovedsageligt ConcurrentMap interface og funktionerne i ConcurrentHashMap og dækket af ConcurrentNavigableMap der kræves nøglebestilling.

Den fulde kildekode til alle eksemplerne i denne artikel kan findes i GitHub-projektet.