Un guide de ConcurrentMap

1. Vue d'ensemble

Les cartes sont naturellement l'un des styles les plus répandus de la collection Java.

Et, plus important encore, HashMap n'est pas une implémentation thread-safe, tandis que Hashtable assure la sécurité des threads en synchronisant les opérations.

Même si Hashtable est thread-safe, il n'est pas très efficace. Une autre carte entièrement synchronisée , Collections.synchronizedMap, ne montre pas non plus une grande efficacité. Si nous voulons une sécurité des threads avec un débit élevé sous une concurrence élevée, ces implémentations ne sont pas la voie à suivre.

Pour résoudre le problème, le Java Collections Framework a introduit ConcurrentMap dans Java 1.5 .

Les discussions suivantes sont basées sur Java 1.8 .

2. ConcurrentMap

ConcurrentMap est une extension de l' interface Map . Il vise à fournir une structure et des conseils pour résoudre le problème de la conciliation du débit avec la sécurité des threads.

En remplaçant plusieurs méthodes d'interface par défaut, ConcurrentMap donne des instructions pour les implémentations valides afin de fournir des opérations atomiques de sécurité des threads et cohérentes en mémoire.

Plusieurs implémentations par défaut sont remplacées, désactivant la prise en charge de la clé / valeur nulle :

  • getOrDefault
  • pour chaque
  • remplace tout
  • computeIfAbsent
  • computeIfPresent
  • calculer
  • fusionner

Les API suivantes sont également remplacées pour prendre en charge l'atomicité, sans implémentation d'interface par défaut:

  • putIfAbsent
  • retirer
  • replace (clé, oldValue, newValue)
  • replace (clé, valeur)

Le reste des actions est directement hérité avec fondamentalement cohérent avec Map .

3. ConcurrentHashMap

ConcurrentHashMap est l' implémentation de ConcurrentMap prête à l'emploi .

Pour de meilleures performances, il se compose d'un tableau de nœuds sous forme de compartiments de table (auparavant des segments de table avant Java 8 ) sous le capot, et utilise principalement les opérations CAS lors de la mise à jour.

Les compartiments de table sont initialisés paresseusement, lors de la première insertion. Chaque bucket peut être verrouillé indépendamment en verrouillant le tout premier nœud du bucket. Les opérations de lecture ne bloquent pas et les conflits de mise à jour sont minimisés.

Le nombre de segments requis est relatif au nombre de threads accédant à la table afin que la mise à jour en cours par segment ne soit pas plus d'un la plupart du temps.

Avant Java 8 , le nombre de «segments» requis était relatif au nombre de threads accédant à la table afin que la mise à jour en cours par segment ne soit pas plus d'un la plupart du temps.

C'est pourquoi les constructeurs, par rapport à HashMap , fournissent l' argument supplémentaire concurrencyLevel pour contrôler le nombre de threads estimé à utiliser:

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

Les deux autres arguments: initialCapacity et loadFactor fonctionnaient à peu près de la même manière que HashMap .

Cependant, depuis Java 8 , les constructeurs ne sont présents que pour la rétrocompatibilité: les paramètres ne peuvent affecter que la taille initiale de la carte .

3.1. Fil-Sécurité

ConcurrentMap garantit la cohérence de la mémoire sur les opérations clé / valeur dans un environnement multi-threading.

Actions dans un thread avant de placer un objet dans un ConcurrentMap en tant que clé ou valeur avant les actions consécutives à l'accès ou à la suppression de cet objet dans un autre thread.

Pour confirmer, examinons un cas de mémoire incohérente:

@Test public void givenHashMap_whenSumParallel_thenError() throws Exception { Map map = new HashMap(); List sumList = parallelSum100(map, 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); for (int j = 0; j  { for (int k = 0; k  value + 1 ); }); } executorService.shutdown(); executorService.awaitTermination(5, TimeUnit.SECONDS); sumList.add(map.get("test")); } return sumList; }

Pour chaque action map.computeIfPresent en parallèle, HashMap ne fournit pas une vue cohérente de ce que devrait être la valeur entière actuelle, conduisant à des résultats incohérents et indésirables.

Quant à ConcurrentHashMap , nous pouvons obtenir un résultat cohérent et correct:

@Test public void givenConcurrentMap_whenSumParallel_thenCorrect() throws Exception { Map map = new ConcurrentHashMap(); List sumList = parallelSum100(map, 1000); assertEquals(1, sumList .stream() .distinct() .count()); long wrongResultCount = sumList .stream() .filter(num -> num != 100) .count(); assertEquals(0, wrongResultCount); }

3.2. Clé / valeur nulle

La plupart des API fournies par ConcurrentMap n'autorisent pas la clé ou la valeur nulle , par exemple:

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

Cependant, pour les actions de calcul * et de fusion , la valeur calculée peut être nulle , ce qui indique que le mappage clé-valeur est supprimé s'il est présent ou reste absent s'il était auparavant absent .

@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. Prise en charge du flux

Java 8 provides Stream support in the ConcurrentHashMap as well.

Unlike most stream methods, the bulk (sequential and parallel) operations allow concurrent modification safely. ConcurrentModificationException won't be thrown, which also applies to its iterators. Relevant to streams, several forEach*, search, and reduce* methods are also added to support richer traversal and map-reduce operations.

3.4. Performance

Under the hood, ConcurrentHashMap is somewhat similar to HashMap, with data access and update based on a hash table (though more complex).

And of course, the ConcurrentHashMap should yield much better performance in most concurrent cases for data retrieval and update.

Let's write a quick micro-benchmark for get and put performance and compare that to Hashtable and Collections.synchronizedMap, running both operations for 500,000 times in 4 threads.

@Test public void givenMaps_whenGetPut500KTimes_thenConcurrentMapFaster() throws Exception { Map hashtable = new Hashtable(); Map synchronizedHashMap = Collections.synchronizedMap(new HashMap()); Map concurrentHashMap = new ConcurrentHashMap(); long hashtableAvgRuntime = timeElapseForGetPut(hashtable); long syncHashMapAvgRuntime = timeElapseForGetPut(synchronizedHashMap); long concurrentHashMapAvgRuntime = timeElapseForGetPut(concurrentHashMap); assertTrue(hashtableAvgRuntime > concurrentHashMapAvgRuntime); assertTrue(syncHashMapAvgRuntime > concurrentHashMapAvgRuntime); } private long timeElapseForGetPut(Map map) throws 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(10000); String key = String.valueOf(value); map.put(key, value); map.get(key); } }); } executorService.shutdown(); executorService.awaitTermination(1, TimeUnit.MINUTES); return (System.nanoTime() - startTime) / 500_000; }

Keep in mind micro-benchmarks are only looking at a single scenario and aren't always a good reflection of real world performance.

That being said, on an OS X system with an average dev system, we're seeing an average sample result for 100 consecutive runs (in nanoseconds):

Hashtable: 1142.45 SynchronizedHashMap: 1273.89 ConcurrentHashMap: 230.2

In a multi-threading environment, where multiple threads are expected to access a common Map, the ConcurrentHashMap is clearly preferable.

However, when the Map is only accessible to a single thread, HashMap can be a better choice for its simplicity and solid performance.

3.5. Pitfalls

Retrieval operations generally do not block in ConcurrentHashMap and could overlap with update operations. So for better performance, they only reflect the results of the most recently completed update operations, as stated in the official Javadoc.

There are several other facts to bear in mind:

  • results of aggregate status methods including size, isEmpty, and containsValue are typically useful only when a map is not undergoing concurrent updates in other threads:
@Test public void givenConcurrentMap_whenUpdatingAndGetSize_thenError() throws InterruptedException { Runnable collectMapSizes = () -> { for (int i = 0; i  { for (int i = 0; i < MAX_SIZE; i++) { concurrentMap.put(String.valueOf(i), i); } }; executorService.execute(updateMapData); executorService.execute(collectMapSizes); executorService.shutdown(); executorService.awaitTermination(1, TimeUnit.MINUTES); assertNotEquals(MAX_SIZE, mapSizes.get(MAX_SIZE - 1).intValue()); assertEquals(MAX_SIZE, concurrentMap.size()); }

If concurrent updates are under strict control, aggregate status would still be reliable.

Although these aggregate status methods do not guarantee the real-time accuracy, they may be adequate for monitoring or estimation purposes.

Note that usage of size() of ConcurrentHashMap should be replaced by mappingCount(), for the latter method returns a long count, although deep down they are based on the same estimation.

  • hashCode matters: note that using many keys with exactly the same hashCode() is a sure way to slow down a performance of any hash table.

To ameliorate impact when keys are Comparable, ConcurrentHashMap may use comparison order among keys to help break ties. Still, we should avoid using the same hashCode() as much as we can.

  • iterators are only designed to use in a single thread as they provide weak consistency rather than fast-fail traversal, and they will never throw ConcurrentModificationException.
  • the default initial table capacity is 16, and it's adjusted by the specified concurrency level:
public ConcurrentHashMap( int initialCapacity, float loadFactor, int concurrencyLevel) { //... if (initialCapacity < concurrencyLevel) { initialCapacity = concurrencyLevel; } //... }
  • caution on remapping functions: though we can do remapping operations with provided compute and merge* methods, we should keep them fast, short and simple, and focus on the current mapping to avoid unexpected blocking.
  • keys in ConcurrentHashMap are not in sorted order, so for cases when ordering is required, ConcurrentSkipListMap is a suitable choice.

4. ConcurrentNavigableMap

For cases when ordering of keys is required, we can use ConcurrentSkipListMap, a concurrent version of TreeMap.

As a supplement for ConcurrentMap, ConcurrentNavigableMap supports total ordering of its keys (in ascending order by default) and is concurrently navigable. Methods that return views of the map are overridden for concurrency compatibility:

  • subMap
  • headMap
  • tailMap
  • subMap
  • headMap
  • tailMap
  • descendingMap

keySet() views' iterators and spliterators are enhanced with weak-memory-consistency:

  • navigableKeySet
  • keySet
  • descendingKeySet

5. ConcurrentSkipListMap

Previously, we have covered NavigableMap interface and its implementation TreeMap. ConcurrentSkipListMap can be seen a scalable concurrent version of TreeMap.

In practice, there's no concurrent implementation of the red-black tree in Java. A concurrent variant of SkipLists is implemented in ConcurrentSkipListMap, providing an expected average log(n) time cost for the containsKey, get, put and remove operations and their variants.

In addition to TreeMap‘s features, key insertion, removal, update and access operations are guaranteed with thread-safety. Here's a comparison to TreeMap when navigating concurrently:

@Test public void givenSkipListMap_whenNavConcurrently_thenCountCorrect() throws InterruptedException { NavigableMap skipListMap = new ConcurrentSkipListMap(); int count = countMapElementByPollingFirstEntry(skipListMap, 10000, 4); assertEquals(10000 * 4, count); } @Test public void givenTreeMap_whenNavConcurrently_thenCountError() throws InterruptedException { NavigableMap treeMap = new TreeMap(); int count = countMapElementByPollingFirstEntry(treeMap, 10000, 4); assertNotEquals(10000 * 4, count); } private int countMapElementByPollingFirstEntry( NavigableMap navigableMap, int elementCount, int concurrencyLevel) throws 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(); }

Une explication complète des problèmes de performances dans les coulisses dépasse le cadre de cet article. Les détails peuvent être trouvés dans le Javadoc de ConcurrentSkipListMap , qui se trouve sous java / util / concurrent dans le fichier src.zip .

6. Conclusion

Dans cet article, nous avons principalement présenté l' interface ConcurrentMap et les fonctionnalités de ConcurrentHashMap et couvert sur ConcurrentNavigableMap étant l'ordre des clés requis.

Le code source complet de tous les exemples utilisés dans cet article se trouve dans le projet GitHub.