streamalism.org

1. Oversikt

Kart er naturlig nok en av de mest stilige Java-samlingene.

Og, viktigere, HashMap er ikke en trådsikker implementering, mens Hashtable gir trådsikkerhet ved å synkronisere operasjoner.

Selv om Hashtable er trådsikker, er det ikke veldig effektivt. Nok en fullt synkronisert Kart,Collections.synchronizedMap, utviser heller ikke stor effektivitet. Hvis vi ønsker trådsikkerhet med høy gjennomstrømning under høy samtidighet, er ikke disse implementeringene veien å gå.

For å løse problemet, Java Collections Frameworkintrodusert ConcurrentMap i Java 1.5.

Følgende diskusjoner er basert på Java 1.8.

2. ConcurrentMap

ConcurrentMap er en utvidelse av Kart grensesnitt. Det tar sikte på å gi en struktur og veiledning for å løse problemet med å forene gjennomstrømning med trådsikkerhet.

Ved å overstyre flere standardgrensesnittmetoder, ConcurrentMap gir retningslinjer for gyldige implementeringer for å gi trådsikkerhet og minne-konsistente atomoperasjoner.

Flere standardimplementeringer overstyres, og deaktiverer null nøkkel / verdi støtte:

• getOrDefault
• for hver
• erstatte alle
• computeIfAbsent
• computeIfPresent
• beregne
• slå sammen

Følgende APIer overstyres også for å støtte atomicitet, uten standardgrensesnittimplementering:

• putIfAbsent
• fjerne
• erstatt (nøkkel, gammel verdi, ny verdi)
• erstatt (nøkkel, verdi)

Resten av handlingene er direkte arvet med i utgangspunktet i samsvar med Kart.

3. ConcurrentHashMap

ConcurrentHashMap er out-of-box klar ConcurrentMap gjennomføring.

For bedre ytelse består den av en rekke noder som bordbøtter (pleide å være bordsegmenter før Java 8) under panseret, og bruker hovedsakelig CAS-operasjoner under oppdatering.

Bordskuffene initialiseres lat ved første innsetting. Hver bøtte kan låses uavhengig av hverandre ved å låse den aller første noden i bøtta. Leseoperasjoner blokkerer ikke, og oppdateringsinnhold er minimert.

Antall segmenter som kreves er i forhold til antall tråder som får tilgang til tabellen, slik at oppdateringen som pågår per segment ikke vil være mer enn en mesteparten av tiden.

Før Java 8, antall "segmenter" som kreves var relativt til antall tråder som fikk tilgang til tabellen, slik at oppdateringen som pågår per segment ikke vil være mer enn en mesteparten av tiden.

Det er derfor konstruktører, sammenlignet med HashMap, gir ekstra samtidighetNivå argument for å kontrollere antall estimerte tråder som skal brukes:

offentlig ConcurrentHashMap (

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

De to andre argumentene: initialCapacity og loadFactor jobbet ganske det samme som HashMap.

Imidlertid siden Java 8, konstruktørene er bare til stede for bakoverkompatibilitet: parametrene kan bare påvirke den opprinnelige størrelsen på kartet.

3.1. Trådsikkerhet

ConcurrentMap garanterer hukommelseskonsistens på nøkkel- / verdioperasjoner i et miljø med flere tråder.

Handlinger i en tråd før du plasserer et objekt i en ConcurrentMap som en nøkkel eller verdi skje-før handlinger etter tilgang eller fjerning av objektet i en annen tråd.

For å bekrefte, la oss ta en titt på et minne inkonsekvent tilfelle:

@Test offentlig ugyldighet gittHashMap_whenSumParallel_thenError () kaster unntak {Map map = new HashMap (); Liste sumList = parallelSum100 (kart, 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); for (int i = 0; i <executionTimes; i ++) {map.put ("test", 0); ExecutorService executorService = Executors.newFixedThreadPool (4); for (int j = 0; j {for (int k = 0; k verdi + 1);}); } executorService.shutdown (); executorService.awaitTermination (5, TimeUnit.SECONDS); sumList.add (map.get ("test")); } returner sumList; }

For hver map.computeIfPresent handling parallelt, HashMap gir ikke et konsistent bilde av hva som skal være nåværende heltall, noe som fører til inkonsekvente og uønskede resultater.

Når det gjelder ConcurrentHashMap, kan vi få et jevnt og riktig resultat:

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

3.2. Null Nøkkel / verdi

Mest APIs levert av ConcurrentMap tillater ikke null nøkkel eller verdi, for eksempel:

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

Derimot, til beregne * og slå sammen handlinger, kan den beregnede verdien være null, som indikerer at nøkkelverdikartleggingen fjernes hvis den er tilstede eller forblir fraværende hvis den tidligere ikke er tilstede.

@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. Stream-støtte

Java 8 gir Strøm støtte i ConcurrentHashMap også.

I motsetning til de fleste strømmetoder, tillater bulk (sekvensiell og parallell) operasjon samtidig endring trygt. ConcurrentModificationException vil ikke bli kastet, noe som også gjelder for iteratorene. Relevant for bekker, flere for hver*, Søk, og redusere* metoder er også lagt til for å støtte rikere gjennomkjøring og kartreduserende operasjoner.

3.4. Opptreden

Under panseret, ConcurrentHashMap ligner noe på HashMap, med datatilgang og oppdatering basert på en hash-tabell (men mer komplisert).

Og selvfølgelig, den ConcurrentHashMap burde gi mye bedre ytelse i de fleste samtidige tilfeller for datainnhenting og oppdatering.

La oss skrive en rask mikro-referanse for få og sette ytelse og sammenlign den med Hashtable og Collections.synchronizedMap, kjører begge operasjonene 500 000 ganger i 4 tråder.

@Test offentlig ugyldighet givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster () kaster Unntak {Map hashtable = new Hashtable (); Kart synchronizedHashMap = Collections.synchronizedMap (nytt HashMap ()); Kart concurrentHashMap = ny ConcurrentHashMap (); lang hashtableAvgRuntime = timeElapseForGetPut (hashtable); lang syncHashMapAvgRuntime = timeElapseForGetPut (synkronisertHashMap); lang concurrentHashMapAvgRuntime = timeElapseForGetPut (concurrentHashMap); assertTrue (hashtableAvgRuntime> concurrentHashMapAvgRuntime); assertTrue (syncHashMapAvgRuntime> concurrentHashMapAvgRuntime); } private long timeElapseForGetPut (Map map) 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økkel, verdi); map.get (nøkkel);}}); } executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); retur (System.nanoTime () - startTime) / 500_000; }

Husk at mikrobenkverdier bare ser på et enkelt scenario og ikke alltid er en god refleksjon av ytelsen i den virkelige verden.

Når det er sagt, på et OS X-system med et gjennomsnittlig utviklingssystem, ser vi et gjennomsnittlig prøveresultat for 100 påfølgende runder (i nanosekunder):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

I et miljø med flere tråder, der det forventes at flere tråder får tilgang til et felles Kart, den ConcurrentHashMap er klart å foretrekke.

Imidlertid når Kart er bare tilgjengelig for en enkelt tråd, HashMap kan være et bedre valg for sin enkelhet og solide ytelse.

3.5. Fallgruver

Hentingsoperasjoner blokkerer vanligvis ikke ConcurrentHashMap og kan overlappe med oppdateringsoperasjoner. Så for bedre ytelse, gjenspeiler de bare resultatene av de siste fullførte oppdateringsoperasjonene, som nevnt i den offisielle Javadoc.

Det er flere andre fakta å huske på:

• resultater av samlede statusmetoder inkludert størrelse, er tom, og inneholder verdi er vanligvis bare nyttige når et kart ikke gjennomgår samtidige oppdateringer i andre tråder:

@Test offentlig ugyldighet givenConcurrentMap_whenUpdatingAndGetSize_thenError () kaster InterruptedException {Runnable collectMapSizes = () -> {for (int i = 0; i {for (int i = 0; i <MAX_SIZE; i ++) {concurrentMap.put (String i ), 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 oppdateringer er under streng kontroll, vil samlet status fortsatt være pålitelig.

Selv om disse samlede statusmetoder garanterer ikke nøyaktigheten i sanntid, de kan være tilstrekkelig for overvåking eller estimering.

Merk at bruk av størrelse() av ConcurrentHashMap bør erstattes av mappingCount (), for sistnevnte metode returnerer a lang telle, selv om de er innerst inne basert på samme estimering.

• hashCode betyr noe: Vær oppmerksom på at du bruker mange taster med nøyaktig det samme hashCode () er en sikker måte å bremse ytelsen til et hvilket som helst hasjbord.

For å forbedre påvirkningen når tastene er Sammenlignelig, ConcurrentHashMap kan bruke sammenligningsrekkefølge mellom nøkler for å bidra til å bryte bånd. Likevel bør vi unngå å bruke det samme hashCode () så mye vi kan.

• iteratorer er bare designet for å brukes i en enkelt tråd, ettersom de gir svak konsistens i stedet for hurtig feilsøking, og de vil aldri kaste ConcurrentModificationException.
• standard innledende tabellkapasitet er 16, og den justeres etter det angitte samtidighetsnivået:

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

• forsiktighet ved omkartingsfunksjoner: selv om vi kan utføre kartleggingsoperasjoner som følger med beregne og slå sammen* metoder, bør vi holde dem raske, korte og enkle, og fokusere på den nåværende kartleggingen for å unngå uventet blokkering.
• tastene inn ConcurrentHashMap ikke er i sortert rekkefølge, så i tilfeller der bestilling er påkrevd, ConcurrentSkipListMap er et passende valg.

4. ConcurrentNavigableMap

For tilfeller der det kreves bestilling av nøkler, kan vi bruke ConcurrentSkipListMap, en samtidig versjon av TreeMap.

Som et supplement til ConcurrentMap, ConcurrentNavigableMap støtter totalbestilling av nøklene (i stigende rekkefølge som standard) og er samtidig navigerbar. Metoder som returnerer visninger av kartet blir overstyrt for samtidighetskompatibilitet:

• underkart
• headMap
• tailMap
• underkart
• headMap
• tailMap
• synkende Kart

keySet () visningens iteratorer og spliteratorer forbedres med svak minne-konsistens:

• navigableKeySet
• keySet
• descendingKeySet

5. ConcurrentSkipListMap

Tidligere har vi dekket NavigableMap grensesnitt og implementering av det TreeMap. ConcurrentSkipListMap kan sees i en skalerbar samtidig versjon av TreeMap.

I praksis er det ingen samtidig implementering av det rød-svarte treet i Java. En samtidig variant av SkipLists er implementert i ConcurrentSkipListMap, gir en forventet gjennomsnittlig logg (n) tidskostnad for inneholder nøkkel, få, sette og fjerne operasjoner og deres varianter.

I tillegg til TreeMapFunksjoner, nøkkelinnføring, fjerning, oppdatering og tilgangsoperasjoner er garantert med trådsikkerhet. Her er en sammenligning med TreeMap når du navigerer samtidig:

@Test offentlig ugyldighet givenSkipListMap_whenNavConcurrently_thenCountCorrect () kaster InterruptedException {NavigableMap skipListMap = new ConcurrentSkipListMap (); int count = countMapElementByPollingFirstEntry (skipListMap, 10000, 4); assertEquals (10000 * 4, count); } @Test offentlig ugyldighet 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 counter = new 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 fullstendig forklaring på forestillingsproblemene bak kulissene ligger utenfor omfanget av denne artikkelen. Detaljene finner du i ConcurrentSkipListMap's Javadoc, som ligger under java / util / samtidig i src.zip fil.

6. Konklusjon

I denne artikkelen introduserte vi hovedsakelig ConcurrentMap grensesnitt og funksjonene til ConcurrentHashMap og dekket på ConcurrentNavigableMap å være nøkkelbestilling nødvendig.

Den fullstendige kildekoden for alle eksemplene som brukes i denne artikkelen finner du i GitHub-prosjektet.