Sollten Sie überprüfen, ob die Karte Schlüssel enthält, bevor Sie putIfAbsent von ConcurrentMap verwenden

71

Ich habe Javas ConcurrentMap für eine Map verwendet, die von mehreren Threads verwendet werden kann. PutIfAbsent ist eine großartige Methode und viel einfacher zu lesen / schreiben als die Verwendung von Standardkartenoperationen. Ich habe einen Code, der so aussieht:

ConcurrentMap<String, Set<X>> map = new ConcurrentHashMap<String, Set<X>>();

// ...

map.putIfAbsent(name, new HashSet<X>());
map.get(name).add(Y);

In Bezug auf die Lesbarkeit ist dies großartig, erfordert jedoch jedes Mal das Erstellen eines neuen HashSet, selbst wenn es bereits in der Karte enthalten ist. Ich könnte das schreiben:

if (!map.containsKey(name)) {
    map.putIfAbsent(name, new HashSet<X>());
}
map.get(name).add(Y);

Mit dieser Änderung verliert es etwas an Lesbarkeit, muss jedoch nicht jedes Mal das HashSet erstellen. Was ist in diesem Fall besser? Ich neige dazu, mich dem ersten anzuschließen, da es besser lesbar ist. Die zweite würde besser abschneiden und könnte korrekter sein. Vielleicht gibt es einen besseren Weg, dies zu tun als beide.

Was ist die beste Vorgehensweise, um ein putIfAbsent auf diese Weise zu verwenden?

Chris Dail
quelle
3
In Ihrem Beispiel müsste das Value-HashSet auch ein ConcurrentHashSet sein, sonst ist dies immer noch nicht threadsicher.
Markus Kull
1
Tom Hawtins Lösung ist genau das, wonach Sie suchen
John Vint
1
Wie von Markus hervorgehoben, muss der Werttyp (in diesem Fall das Set) auch threadsicher sein, da mehrere Threads gleichzeitig darauf zugreifen können.
Sjlee
Selbst wenn Sie die Antwort von Tom Hawtin verwenden, die unvollständig ist und meiner Meinung nach Ihrem eigenen Vorschlag entspricht.
Petersaints

Antworten:

106

Parallelität ist schwer. Wenn Sie sich mit gleichzeitigen Karten beschäftigen möchten, anstatt sie einfach zu sperren, können Sie sich genauso gut dafür entscheiden. Suchen Sie in der Tat nicht mehr als nötig.

Set<X> set = map.get(name);
if (set == null) {
    final Set<X> value = new HashSet<X>();
    set = map.putIfAbsent(name, value);
    if (set == null) {
        set = value;
    }
}

(Üblicher Haftungsausschluss für Stapelüberläufe: Auf den ersten Blick. Nicht getestet. Nicht kompiliert. Usw.)

Update: 1.8 hat die computeIfAbsentStandardmethode hinzugefügt ConcurrentMap(und Mapdas ist irgendwie interessant, weil diese Implementierung falsch wäre ConcurrentMap). (Und 1.7 fügte den "Diamantoperator" hinzu <>.)

Set<X> set = map.computeIfAbsent(name, n -> new HashSet<>());

(Beachten Sie, dass Sie für die Thread-Sicherheit aller Vorgänge der HashSetin der ConcurrentMap. Enthaltenen s verantwortlich sind .)

Tom Hawtin - Tackline
quelle
23
+1 für "Parallelität ist schwer" und unter Verwendung des Rückgabewerts von putIfAbsent
Markus Kull
1
@Markus - +1 auch für den Hinweis auf die offensichtliche, aber leicht zu ignorierende Tatsache, dass die Wiederverwendung des Rückgabewerts eine gute Praxis ist.
Drupad Panchal
1
Gute Antwort. Erinnert mich an doppelt überprüftes Sperren: en.wikipedia.org/wiki/Double-checked_locking
Mansoor Siddiqui
1
Würde es nicht immer noch mehrere Instanzen instanziieren, HashSetfalls mehrere Threads gleichzeitig die if (set == null)Prüfung nicht bestehen würden?
Zerkms
2
@zerkms Das kann passieren, und der zweite if (set == null)behandelt das mit dem ersten Thread durch Gewinnen. Die Situation ist unwahrscheinlich und die zusätzliche Zuweisungszeit ist wahrscheinlich nicht signifikant. Sie können einen temporären Wert einfügen, um einem einzelnen Thread exklusiven Zugriff zu gewähren. Dies kann jedoch die allgemeine Leistung und Zuverlässigkeit beeinträchtigen.
Tom Hawtin - Tackline
16

Toms Antwort ist richtig, was die API-Nutzung für ConcurrentMap betrifft. Eine Alternative, die die Verwendung von putIfAbsent vermeidet, ist die Verwendung der Computerkarte aus GoogleCollections / Guava MapMaker, die die Werte automatisch mit einer bereitgestellten Funktion auffüllt und die gesamte Thread-Sicherheit für Sie übernimmt. Es wird tatsächlich nur ein Wert pro Schlüssel erstellt. Wenn die Erstellungsfunktion teuer ist, werden andere Threads, die nach demselben Schlüssel fragen, blockiert, bis der Wert verfügbar wird.

Bei der Bearbeitung von Guava 11 ist MapMaker veraltet und wird durch das Zeug Cache / LocalCache / CacheBuilder ersetzt. Dies ist etwas komplizierter in seiner Verwendung, aber im Grunde genommen isomorph.

Jed Wesley-Smith
quelle
Ich habe es gerade versucht und es ist eine großartige Lösung. Sie erhalten alle Vorteile von ConcurrentMap, ohne sich um die putIfAbsent-Redewendungen kümmern zu müssen, die leicht durcheinander zu bringen sind.
Matt Friedman
5

Sie können MutableMap.getIfAbsentPut(K, Function0<? extends V>)aus Eclipse-Sammlungen (früher GS-Sammlungen ) verwenden.

Der Vorteil gegenüber dem Aufrufen get(), Durchführen einer Nullprüfung und anschließendem Aufrufen putIfAbsent()besteht darin, dass wir den Hashcode des Schlüssels nur einmal berechnen und einmal die richtige Stelle in der Hashtabelle finden. In ConcurrentMaps wie org.eclipse.collections.impl.map.mutable.ConcurrentHashMapist die Implementierung von getIfAbsentPut()auch threadsicher und atomar.

import org.eclipse.collections.impl.map.mutable.ConcurrentHashMap;
...
ConcurrentHashMap<String, MyObject> map = new ConcurrentHashMap<>();
map.getIfAbsentPut("key", () -> someExpensiveComputation());

Die Implementierung von org.eclipse.collections.impl.map.mutable.ConcurrentHashMap ist wirklich nicht blockierend. Obwohl alle Anstrengungen unternommen werden, um die Factory-Funktion nicht unnötig aufzurufen, besteht die Möglichkeit, dass sie während eines Konflikts mehrmals aufgerufen wird.

Diese Tatsache unterscheidet es von Java 8 ConcurrentHashMap.computeIfAbsent(K, Function<? super K,? extends V>). Das Javadoc für diese Methode besagt:

Der gesamte Methodenaufruf wird atomar ausgeführt, sodass die Funktion höchstens einmal pro Schlüssel angewendet wird. Einige versuchte Aktualisierungsvorgänge auf dieser Karte durch andere Threads werden möglicherweise blockiert, während die Berechnung ausgeführt wird. Daher sollte die Berechnung kurz und einfach sein ...

Hinweis: Ich bin ein Committer für Eclipse-Sammlungen.

Craig P. Motlin
quelle
3
Ich mag das sehr. Ich habe diese Frage vor Jahren gestellt, aber mit Java 8 ist dies eine wirklich schöne Lösung.
Chris Dail
3

Indem Sie für jeden Thread einen vorinitialisierten Wert beibehalten, können Sie die akzeptierte Antwort verbessern:

Set<X> initial = new HashSet<X>();
...
Set<X> set = map.putIfAbsent(name, initial);
if (set == null) {
    set = initial;
    initial = new HashSet<X>();
}
set.add(Y);

Ich habe dies kürzlich mit AtomicInteger-Kartenwerten anstelle von Set verwendet.

Karmakaze
quelle
Wie im Update der akzeptierten Antwort erwähnt, fügt Java 1.8 computeIfAbsent hinzu, das das gleiche Ergebnis erzielt und viel einfacher ist.
Karmakaze
Der Kontext, in dem dieser Code verwendet werden muss, wird schwierig. Es wird einen "interessanten" Fehler verursachen, wenn nicht gleich. Ich bin auch nicht davon überzeugt, dass es ein Leistungsgewinn ist. (Auch müssen Sie den Zugang zum sperren HashSet.)
Tom Hawtin - Tackline
2

In mehr als 5 Jahren kann ich nicht glauben, dass niemand eine Lösung erwähnt oder veröffentlicht hat, die ThreadLocal verwendet , um dieses Problem zu lösen. und einige der Lösungen auf dieser Seite sind nicht threadsicher und nur schlampig.

Die Verwendung von ThreadLocals für dieses spezielle Problem wird nicht nur als bewährte Methode für die Parallelität angesehen, sondern auch zur Minimierung der Erstellung von Müll / Objekten während eines Thread-Konflikts. Außerdem ist es unglaublich sauberer Code.

Zum Beispiel:

private final ThreadLocal<HashSet<X>> 
  threadCache = new ThreadLocal<HashSet<X>>() {
      @Override
      protected
      HashSet<X> initialValue() {
          return new HashSet<X>();
      }
  };


private final ConcurrentMap<String, Set<X>> 
  map = new ConcurrentHashMap<String, Set<X>>();

Und die eigentliche Logik ...

// minimize object creation during thread contention
final Set<X> cached = threadCache.get();

Set<X> data = map.putIfAbsent("foo", cached);
if (data == null) {
    // reset the cached value in the ThreadLocal
    listCache.set(new HashSet<X>());
    data = cached;
}

// make sure that the access to the set is thread safe
synchronized(data) {
    data.add(object);
}
Nathan
quelle
Dies ist "Thread-Shared". Der ThreadLocal soll verhindern, dass während des Aufrufs "putIfAbsent ()" unnötige Objekte erstellt werden (Map und folglich Set-Erstellung ist nicht billig). Das Set wird korrekt und sicher in allen Threads veröffentlicht.
Nathan
Und in Kombination mit putIfAbsent()gewinnt nur einer. Somit dataist es in allen Threads immer gleich.
Nathan
Ich denke nicht, dass die Leistung davon großartig sein wird. Sie müssen ThreadLocalzusätzlich jedes Mal eine durchlaufen, wenn Sie nur eine benötigen ConcurrentMap.get. (Und Sie Zugriff auf die HashSet ist nicht threadsicher .)
Tom Hawtin - Tackline
Es trifft die Sperre auf der gleichzeitigen Karte, so dass es gemäß JSL Kapitel 17.4 und dem allgemeinen Verhalten von Sperren (Bearbeiten) sichtbar ist. aber nicht threadsicher ist . Vielen Dank für den Hinweis, ich habe die Antwort aktualisiert. Sie haben Recht mit der Leistung ... Wenn Sie jedoch Leistung wünschen, würden Sie weder eine gleichzeitige Zuordnung noch den (Standard-) lokalen Thread verwenden, sondern sehr unterschiedliche Datenstrukturen. Das geht weit über den Rahmen dieser Frage hinaus.
Nathan
Ich sollte auch darauf hinweisen, dass der Leistungseinbruch bei ThreadLocal weitaus geringer ist als der Leistungseinbruch beim Erstellen und Instanziieren neuer Objekte, insbesondere eines Sets ...
Nathan
0

Meine generische Annäherung:

public class ConcurrentHashMapWithInit<K, V> extends ConcurrentHashMap<K, V> {
  private static final long serialVersionUID = 42L;

  public V initIfAbsent(final K key) {
    V value = get(key);
    if (value == null) {
      value = initialValue();
      final V x = putIfAbsent(key, value);
      value = (x != null) ? x : value;
    }
    return value;
  }

  protected V initialValue() {
    return null;
  }
}

Und als Anwendungsbeispiel:

public static void main(final String[] args) throws Throwable {
  ConcurrentHashMapWithInit<String, HashSet<String>> map = 
        new ConcurrentHashMapWithInit<String, HashSet<String>>() {
    private static final long serialVersionUID = 42L;

    @Override
    protected HashSet<String> initialValue() {
      return new HashSet<String>();
    }
  };
  map.initIfAbsent("s1").add("chao");
  map.initIfAbsent("s2").add("bye");
  System.out.println(map.toString());
}
ggrandes
quelle