streamalism.org

1. Overzicht

Kaarten zijn natuurlijk een van de meest voorkomende stijlen van Java-collecties.

En, belangrijker nog, Hash kaart is geen threadveilige implementatie, terwijl Hashtable biedt thread-veiligheid door operaties te synchroniseren.

Hoewel Hashtable is draadveilig, het is niet erg efficiënt. Een ander volledig gesynchroniseerd Kaart,Collections.synchronizedMap, vertoont ook geen grote efficiëntie. Als we thread-veiligheid willen met een hoge doorvoer bij hoge gelijktijdigheid, zijn deze implementaties niet de juiste keuze.

Om het probleem op te lossen, de Java Collections Frameworkgeïntroduceerd ConcurrentMap in Java 1.5.

De volgende discussies zijn gebaseerd op Java 1.8.

2. ConcurrentMap

ConcurrentMap is een uitbreiding van de Kaart koppel. Het is bedoeld om een ​​structuur en begeleiding te bieden voor het oplossen van het probleem van het verzoenen van doorvoer met draadveiligheid.

Door verschillende standaardmethoden van de interface te overschrijven, ConcurrentMap geeft richtlijnen voor geldige implementaties om thread-veiligheid en geheugen-consistente atomaire bewerkingen te bieden.

Verschillende standaardimplementaties worden overschreven, waardoor het nul sleutel / waarde ondersteuning:

• getOrDefault
• voor elk
• vervang alles
• computeIfAbsent
• computeIfPresent
• berekenen
• samenvoegen

Het volgende API's worden ook overschreven om atomiciteit te ondersteunen, zonder een standaard interface-implementatie:

• putIfAbsent
• verwijderen
• vervangen (key, oldValue, newValue)
• vervangen (sleutel, waarde)

De rest van de acties wordt direct overgeërfd en komt in principe overeen met Kaart.

3. ConcurrentHashMap

ConcurrentHashMap is de out-of-box klaar ConcurrentMap implementatie.

Voor betere prestaties bestaat het uit een reeks knooppunten als table buckets (voorheen tabelsegmenten) Java 8) onder de motorkap en gebruikt voornamelijk CAS-bewerkingen tijdens het updaten.

De tafelemmers worden lui geïnitialiseerd bij de eerste plaatsing. Elke bak kan onafhankelijk worden vergrendeld door het allereerste knooppunt in de bak te vergrendelen. Leesbewerkingen worden niet geblokkeerd en update-inhoud wordt geminimaliseerd.

Het aantal vereiste segmenten is relatief aan het aantal threads dat toegang heeft tot de tabel, zodat de lopende update per segment meestal niet meer dan één is.

Voordat Java 8, het aantal vereiste "segmenten" was gerelateerd aan het aantal threads dat toegang had tot de tabel, zodat de lopende update per segment meestal niet meer dan één zou zijn.

Dat is de reden waarom constructeurs, vergeleken met Hash kaart, zorgt voor de extra concurrencyLevel argument om het aantal geschatte threads te beheren dat moet worden gebruikt:

openbare ConcurrentHashMap (

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

De andere twee argumenten: initialCapacity en ladingsfactor werkte ongeveer hetzelfde als Hash kaart.

Echter, sinds Java 8, de constructors zijn alleen aanwezig voor achterwaartse compatibiliteit: de parameters kunnen alleen de initiële grootte van de kaart beïnvloeden.

3.1. Draad-veiligheid

ConcurrentMap garandeert geheugenconsistentie bij sleutel / waarde-bewerkingen in een omgeving met meerdere threads.

Acties in een thread voorafgaand aan het plaatsen van een object in een ConcurrentMap als sleutel of waarde gebeuren-voor acties die volgen op de toegang tot of verwijdering van dat object in een andere thread.

Laten we om dit te bevestigen eens kijken naar een geheugeninconsistent geval:

@Test openbare leegte gegevenHashMap_whenSumParallel_thenError () gooit uitzondering {Map map = new HashMap (); Lijst sumList = parallelSum100 (map, 100); assertNotEquals (1, sumList .stream () .distinct () .count ()); lang wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertTrue (wrongResultCount> 0); } private List parallelSum100 (Map map, int executionTimes) gooit 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 waarde + 1);}); } executorService.shutdown (); executorService.awaitTermination (5, TimeUnit.SECONDS); sumList.add (map.get ("test")); } return sumList; }

Voor elk map.computeIfPresent actie parallel, Hash kaart geeft geen consistent beeld van wat de huidige gehele waarde zou moeten zijn, wat leidt tot inconsistente en ongewenste resultaten.

Wat betreft ConcurrentHashMapkunnen we een consistent en correct resultaat krijgen:

@Test openbare leegte gegevenConcurrentMap_whenSumParallel_thenCorrect () gooit uitzondering {Map map = new ConcurrentHashMap (); Lijst sumList = parallelSum100 (kaart, 1000); assertEquals (1, sumList .stream () .distinct () .count ()); lang wrongResultCount = sumList .stream () .filter (num -> num! = 100) .count (); assertEquals (0, wrongResultCount); }

3.2. Nul Sleutel waarde

Meest APIs geleverd door ConcurrentMap staat niet toe nul sleutel of waarde, bijvoorbeeld:

@Test (verwacht = NullPointerException.class) openbare ongeldige gegevenConcurrentHashMap_whenPutWithNullKey_thenThrowsNPE () {concurrentMap.put (null, nieuw Object ()); } @Test (verwacht = NullPointerException.class) openbare leegte gegevenConcurrentHashMap_whenPutNullValue_thenThrowsNPE () {concurrentMap.put ("test", null); }

Echter, voor berekenen* en samenvoegen acties, kan de berekende waarde zijn nul, wat aangeeft dat de sleutel / waardetoewijzing wordt verwijderd als deze aanwezig is of afwezig blijft als deze eerder afwezig was.

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

3.3. Stream-ondersteuning

Java 8 biedt Stroom ondersteuning in de ConcurrentHashMap ook.

In tegenstelling tot de meeste stream-methoden, maken de bulkbewerkingen (sequentiële en parallelle) gelijktijdige wijzigingen veilig mogelijk. ConcurrentModificationException wordt niet gegooid, wat ook van toepassing is op de iterators. Relevant voor streams, verschillende voor elk *, zoeken, en verminderen* Er zijn ook methoden toegevoegd om rijkere traversal- en kaartverminderende bewerkingen te ondersteunen.

3.4. Prestatie

Onder de motorkap, ConcurrentHashMap lijkt enigszins op Hash kaart, met gegevenstoegang en update op basis van een hashtabel (hoewel complexer).

En natuurlijk de ConcurrentHashMap zou in de meeste gelijktijdige gevallen veel betere prestaties moeten opleveren voor het ophalen en bijwerken van gegevens.

Laten we een korte micro-benchmark schrijven voor krijgen en leggen prestaties en vergelijk dat met Hashtable en Collections.synchronizedMap, waarbij beide bewerkingen 500.000 keer in 4 threads worden uitgevoerd.

@Test openbare leegte gegevenMaps_whenGetPut500KTimes_thenConcurrentMapFaster () gooit Uitzondering {Map hashtable = new Hashtable (); Map synchronizedHashMap = Collections.synchronizedMap (nieuwe HashMap ()); Map concurrentHashMap = nieuwe ConcurrentHashMap (); lange hashtableAvgRuntime = timeElapseForGetPut (hashtabel); lang syncHashMapAvgRuntime = timeElapseForGetPut (synchronizedHashMap); lang concurrentHashMapAvgRuntime = timeElapseForGetPut (concurrentHashMap); assertTrue (hashtableAvgRuntime> concurrentHashMapAvgRuntime); assertTrue (syncHashMapAvgRuntime> concurrentHashMapAvgRuntime); } privé lange timeElapseForGetPut (kaartkaart) gooit InterruptedException {ExecutorService executorService = Executors.newFixedThreadPool (4); lange startTime = 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 (waarde); map.put (sleutel, waarde); map.get (sleutel);}}); } executorService.shutdown (); executorService.awaitTermination (1, TimeUnit.MINUTES); return (System.nanoTime () - startTime) / 500_000; }

Houd er rekening mee dat microbenchmarks slechts naar één scenario kijken en niet altijd een goede weerspiegeling zijn van de prestaties in de echte wereld.

Dat gezegd hebbende, zien we op een OS X-systeem met een gemiddeld ontwikkelsysteem een ​​gemiddeld voorbeeldresultaat voor 100 opeenvolgende runs (in nanoseconden):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

In een omgeving met meerdere threads, waar wordt verwacht dat meerdere threads toegang hebben tot een common Kaart, de ConcurrentHashMap heeft duidelijk de voorkeur.

Wanneer het Kaart is alleen toegankelijk voor een enkele thread, Hash kaart kan een betere keuze zijn vanwege zijn eenvoud en solide prestaties.

3.5. Valkuilen

Ophaalbewerkingen blokkeren over het algemeen niet ConcurrentHashMap en zou kunnen overlappen met updatebewerkingen. Dus voor betere prestaties geven ze alleen de resultaten weer van de meest recent voltooide updatebewerkingen, zoals vermeld in de officiële Javadoc.

Er zijn verschillende andere feiten waarmee u rekening moet houden:

• resultaten van geaggregeerde statusmethoden, waaronder grootte, is leeg, en bevatValue zijn doorgaans alleen nuttig als een kaart geen gelijktijdige updates ondergaat in andere threads:

@Test openbare ongeldige gegevenConcurrentMap_whenUpdatingAndGetSize_thenError () gooit InterruptedException {Runnable collectMapSizes = () -> {voor (int i = 0; i {voor (int i = 0; i <MAX_SIZE; i ++) {concurrentMap.put (String.valueOf ), 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 ());}

Als gelijktijdige updates onder strikte controle staan, zou de geaggregeerde status nog steeds betrouwbaar zijn.

Hoewel deze geaggregeerde statusmethoden garanderen de realtime nauwkeurigheid niet; ze kunnen geschikt zijn voor monitoring- of schattingsdoeleinden.

Merk op dat het gebruik van grootte() van ConcurrentHashMap moet worden vervangen door mappingCount (), voor de laatste methode retourneert een lang tellen, hoewel ze diep van binnen op dezelfde schatting zijn gebaseerd.

• hashCode zaken: merk op dat het gebruik van veel toetsen met exact dezelfde hashCode () is een zekere manier om de prestaties van een hashtabel te vertragen.

Om de impact te verzachten wanneer de sleutels zijn Vergelijkbaar, ConcurrentHashMap kan vergelijkingsvolgorde tussen sleutels gebruiken om banden te verbreken. Toch moeten we vermijden hetzelfde te gebruiken hashCode () zoveel als we kunnen.

• iterators zijn alleen ontworpen om in een enkele thread te gebruiken, omdat ze een zwakke consistentie bieden in plaats van een snelle doorgang, en ze zullen nooit gooien ConcurrentModificationException.
• de standaard capaciteit van de initiële tabel is 16, en deze wordt aangepast door het gespecificeerde gelijktijdigheidsniveau:

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

• voorzichtigheid bij het opnieuw toewijzen van functies: hoewel we herindelingsbewerkingen kunnen uitvoeren met het geboden berekenen en samenvoegen* methoden, moeten we ze snel, kort en eenvoudig houden en ons concentreren op de huidige mapping om onverwachte blokkering te voorkomen.
• sleutels in ConcurrentHashMap zijn niet in gesorteerde volgorde, dus voor gevallen waarin bestellen is vereist, ConcurrentSkipListMap is een geschikte keuze.

4. ConcurrentNavigableMap

Voor gevallen waarin het bestellen van sleutels vereist is, kunnen we gebruik maken van ConcurrentSkipListMap, een gelijktijdige versie van TreeMap.

Als aanvulling op ConcurrentMap, ConcurrentNavigableMap ondersteunt de totale volgorde van de toetsen (standaard in oplopende volgorde) en is gelijktijdig navigeerbaar. Methoden die weergaven van de kaart retourneren, worden overschreven vanwege compatibiliteit met gelijktijdigheid:

• subMap
• headMap
• tailMap
• subMap
• headMap
• tailMap
• aflopendMap

sleutelbos() de iterators en spliterators van weergaven zijn verbeterd met een zwakke geheugenconsistentie:

• navigableKeySet
• sleutelbos
• descendingKeySet

5. ConcurrentSkipListMap

Eerder hebben we gedekt NavigableMap interface en de implementatie ervan TreeMap. ConcurrentSkipListMap kan worden gezien als een schaalbare gelijktijdige versie van TreeMap.

In de praktijk is er geen gelijktijdige implementatie van de rood-zwarte boom in Java. Een gelijktijdige variant van SkipLists is geïmplementeerd in ConcurrentSkipListMap, met de verwachte gemiddelde log (n) tijdkosten voor het bevatKey, krijgen, leggen en verwijderen operaties en hun varianten.

In aanvulling op TreeMapDe functies, het invoegen, verwijderen, bijwerken en openen van sleutels zijn gegarandeerd met draadveiligheid. Hier is een vergelijking met TreeMap bij gelijktijdig navigeren:

@Test openbare leegte gegevenSkipListMap_whenNavConcurrently_thenCountCorrect () gooit InterruptedException {NavigableMap skipListMap = nieuwe ConcurrentSkipListMap (); int count = countMapElementByPollingFirstEntry (skipListMap, 10000, 4); assertEquals (10000 * 4, aantal); } @Test openbare leegte gegevenTreeMap_whenNavConcurrently_thenCountError () gooit InterruptedException {NavigableMap treeMap = nieuwe TreeMap (); int count = countMapElementByPollingFirstEntry (treeMap, 10000, 4); assertNotEquals (10000 * 4, aantal); } private int countMapElementByPollingFirstEntry (NavigableMap navigableMap, int elementCount, int concurrencyLevel) gooit InterruptedException {voor (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); terugkeer counter.get (); }

Een volledige uitleg van de prestatieproblemen achter de schermen valt buiten het bestek van dit artikel. De details zijn te vinden in ConcurrentSkipListMap's Javadoc, dat zich bevindt onder java / util / concurrent in de src.zip het dossier.

6. Conclusie

In dit artikel hebben we voornamelijk de ConcurrentMap interface en de kenmerken van ConcurrentHashMap en bedekt ConcurrentNavigableMap sleutelbestelling vereist.

De volledige broncode voor alle voorbeelden die in dit artikel worden gebruikt, is te vinden in het GitHub-project.