Haute performance Concurrent MultiMap Java / Scala

Je recherche un MultiMap performant, simultané. J’ai cherché partout mais je ne peux tout simplement pas trouver une solution qui utilise la même approche que ConcurrentHashMap (Verrouiller uniquement un segment du tableau de hachage).

Le multimap sera à la fois lu, ajouté et retiré de souvent.

La clé multimap sera une chaîne et sa valeur sera arbitraire.

J’ai besoin de O (1) pour trouver toutes les valeurs pour une clé donnée, O (N) est OK pour la suppression, mais O (logN) serait préféré.

Il est crucial que la suppression de la dernière valeur d’une clé donnée supprime le conteneur de valeurs de la clé, afin de ne pas laisser de mémoire.

VOICI LA SOLUTION QUE JE CONSTRUIT, disponible sous ApacheV2: Index (multimap)

Pourquoi ne pas encapsuler ConcurrentHashMap [T, ConcurrentLinkedQueue [U]] avec de belles méthodes de type Scala (par exemple, conversion implicite en Iterable ou autre, et méthode de mise à jour)?

Avez-vous essayé Google Collections? Ils ont diverses implémentations Multimap .

Il y en a un en akka bien que je ne l’ aie pas utilisé.

J’ai réalisé un mixin ConcurrentMultiMap qui étend le mixin mutable.MultiMap et a un auto-type simult.Map [A, Set [B]]. Il se verrouille par clé, ce qui a une complexité d’espace O (n), mais sa complexité temporelle est plutôt bonne si vous n’êtes pas particulièrement lourd en écriture.

vous devriez essayer les films . voici le pdf .

Je devais avoir une Map> où l’insertion sur la carte devait être simultanée et aussi sur le jeu correspondant, mais une fois qu’une clé était consommée depuis la map, elle devait être supprimée. si, en tant que Job exécuté toutes les deux secondes, qui consum tout le Set partir d’une clé spécifique, mais que l’insertion soit totalement concourante pour que la plupart des valeurs soient mises en mémoire tampon

Remarque: j’utilise la classe d’assistance de Guava Maps pour créer les cartes simultanées. Cette solution émule également les access simultanés Java dans le listing 5.19 :

 import com.google.common.collect.MapMaker; import com.google.common.collect.Sets; import java.util.Collection; import java.util.Set; import java.util.concurrent.ConcurrentMap; /** * A general purpose Multimap implementation for delayed processing and concurrent insertion/deletes. * * @param  A comparable Key * @param  A comparable Value */ public class ConcurrentMultiMap { private final int size; private final ConcurrentMap> cache; private final ConcurrentMap locks; public ConcurrentMultiMap() { this(32, 2); } public ConcurrentMultiMap(final int concurrencyLevel) { this(concurrencyLevel, 2); } public ConcurrentMultiMap(final int concurrencyLevel, final int factor) { size=concurrencyLevel * factor; cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).makeMap(); locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).weakKeys().weakValues().makeMap(); } private Object getLock(final K key){ final Object object=new Object(); Object lock=locks.putIfAbsent(key, object); if(lock == null){ lock=object; } return lock; } public void put(final K key, final V value) { synchronized(getLock(key)){ Set set=cache.get(key); if(set == null){ set=Sets.newHashSetWithExpectedSize(size); cache.put(key, set); } set.add(value); } } public void putAll(final K key, final Collection values) { synchronized(getLock(key)){ Set set=cache.get(key); if(set == null){ set=Sets.newHashSetWithExpectedSize(size); cache.put(key, set); } set.addAll(values); } } public Set remove(final K key) { synchronized(getLock(key)){ return cache.remove(key); } } public Set getKeySet() { return cache.keySet(); } public int size() { return cache.size(); } } 

Avez-vous jeté un coup d’oeil à Javalution qui est prévu pour le temps réel etc. et bien sûr la haute performance.

Il est tard pour la discussion, pourtant …

En ce qui concerne les produits concurrents haute performance, il faut être prêt à coder la solution. Avec Concurrent, la déclaration du Diable dans les détails a un sens complet. Il est possible d’implémenter la structure de manière totalement concurrente et sans locking.

La base de départ serait la table de hachage non bloquante http://sourceforge.net/projects/high-scale-lib/ , puis en fonction du nombre de valeurs par clé et de la fréquence à laquelle il faut append / supprimer de la copie sur l’écriture Object [] pour les valeurs ou une Array basé sur un ensemble avec sémaphore / locking de rotation.

Je suis un peu en retard sur ce sujet mais je pense que de nos jours, vous pouvez utiliser Guava comme ceci:

 Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)