Ist das Iterieren von ConcurrentHashMap-Werten threadsicher?

156

In Javadoc für ConcurrentHashMap ist Folgendes:

Abrufvorgänge (einschließlich get) werden im Allgemeinen nicht blockiert und können sich daher mit Aktualisierungsvorgängen (einschließlich put und remove) überschneiden. Abrufe spiegeln die Ergebnisse der zuletzt abgeschlossenen Aktualisierungsvorgänge wider, die bei ihrem Beginn ausgeführt wurden. Bei aggregierten Vorgängen wie putAll und clear können gleichzeitige Abfragen das Einfügen oder Entfernen nur einiger Einträge widerspiegeln. In ähnlicher Weise geben Iteratoren und Aufzählungen Elemente zurück, die den Status der Hash-Tabelle zu einem bestimmten Zeitpunkt oder seit der Erstellung des Iterators / der Aufzählung widerspiegeln. Sie lösen keine ConcurrentModificationException aus. Iteratoren können jedoch jeweils nur von einem Thread verwendet werden.

Was heißt das? Was passiert, wenn ich versuche, die Karte mit zwei Threads gleichzeitig zu iterieren? Was passiert, wenn ich einen Wert während der Iteration in die Karte einfüge oder aus der Karte entferne?

Palo
quelle

Antworten:

193

Was heißt das?

Das bedeutet, dass jeder Iterator, den Sie von einem erhalten ConcurrentHashMap, für die Verwendung durch einen einzelnen Thread ausgelegt ist und nicht weitergegeben werden sollte. Dies schließt den syntaktischen Zucker ein, den die for-each-Schleife bereitstellt.

Was passiert, wenn ich versuche, die Karte mit zwei Threads gleichzeitig zu iterieren?

Es funktioniert wie erwartet, wenn jeder der Threads seinen eigenen Iterator verwendet.

Was passiert, wenn ich einen Wert während der Iteration in die Karte einfüge oder aus der Karte entferne?

Es ist garantiert, dass die Dinge nicht kaputt gehen, wenn Sie dies tun (das ist ein Teil dessen, was "gleichzeitig" ist ConcurrentHashMap bedeutet). Es gibt jedoch keine Garantie dafür, dass ein Thread die Änderungen an der Map sieht, die der andere Thread ausführt (ohne einen neuen Iterator von der Map zu erhalten). Der Iterator gibt garantiert den Status der Karte zum Zeitpunkt ihrer Erstellung wieder. Weitere Änderungen können sich im Iterator widerspiegeln, müssen es aber nicht sein.

Abschließend eine Aussage wie

for (Object o : someConcurrentHashMap.entrySet()) {
    // ...
}

wird fast jedes Mal in Ordnung (oder zumindest sicher) sein, wenn Sie es sehen.

Waldheinz
quelle
Was passiert also, wenn während der Iteration ein anderer Thread ein Objekt o10 von der Karte entfernt hat? Kann ich o10 in der Iteration immer noch sehen, auch wenn es entfernt wurde? @ Waldheinz
Alex
Wie oben erwähnt, wird nicht angegeben, ob ein vorhandener Iterator spätere Änderungen an der Karte widerspiegelt. Ich weiß es also nicht, und laut Spezifikation tut es niemand (ohne auf den Code zu achten, und das kann sich mit jedem Update der Laufzeit ändern). Sie können sich also nicht darauf verlassen.
Waldheinz
8
Aber ich habe immer noch eine ConcurrentModificationException Weile Zeit, ein ConcurrentHashMap, warum?
Kimi Chiu
@KimiChiu Sie sollten wahrscheinlich eine neue Frage stellen, die den Code enthält, der diese Ausnahme auslöst, aber ich bezweifle sehr, dass er direkt aus der Iteration eines gleichzeitigen Containers stammt. es sei denn, die Java-Implementierung ist fehlerhaft.
Waldheinz
18

Mit dieser Klasse können Sie zwei Zugriffsthreads und einen Mutationstest für die gemeinsam genutzte Instanz von ConcurrentHashMap: testen.

import java.util.Map;
import java.util.Random;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentMapIteration
{
  private final Map<String, String> map = new ConcurrentHashMap<String, String>();

  private final static int MAP_SIZE = 100000;

  public static void main(String[] args)
  {
    new ConcurrentMapIteration().run();
  }

  public ConcurrentMapIteration()
  {
    for (int i = 0; i < MAP_SIZE; i++)
    {
      map.put("key" + i, UUID.randomUUID().toString());
    }
  }

  private final ExecutorService executor = Executors.newCachedThreadPool();

  private final class Accessor implements Runnable
  {
    private final Map<String, String> map;

    public Accessor(Map<String, String> map)
    {
      this.map = map;
    }

    @Override
    public void run()
    {
      for (Map.Entry<String, String> entry : this.map.entrySet())
      {
        System.out.println(
            Thread.currentThread().getName() + " - [" + entry.getKey() + ", " + entry.getValue() + ']'
        );
      }
    }
  }

  private final class Mutator implements Runnable
  {

    private final Map<String, String> map;
    private final Random random = new Random();

    public Mutator(Map<String, String> map)
    {
      this.map = map;
    }

    @Override
    public void run()
    {
      for (int i = 0; i < 100; i++)
      {
        this.map.remove("key" + random.nextInt(MAP_SIZE));
        this.map.put("key" + random.nextInt(MAP_SIZE), UUID.randomUUID().toString());
        System.out.println(Thread.currentThread().getName() + ": " + i);
      }
    }
  }

  private void run()
  {
    Accessor a1 = new Accessor(this.map);
    Accessor a2 = new Accessor(this.map);
    Mutator m = new Mutator(this.map);

    executor.execute(a1);
    executor.execute(m);
    executor.execute(a2);
  }
}

Es wird keine Ausnahme ausgelöst.

Das Teilen desselben Iterators zwischen Accessor-Threads kann zu einem Deadlock führen:

import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentMapIteration
{
  private final Map<String, String> map = new ConcurrentHashMap<String, String>();
  private final Iterator<Map.Entry<String, String>> iterator;

  private final static int MAP_SIZE = 100000;

  public static void main(String[] args)
  {
    new ConcurrentMapIteration().run();
  }

  public ConcurrentMapIteration()
  {
    for (int i = 0; i < MAP_SIZE; i++)
    {
      map.put("key" + i, UUID.randomUUID().toString());
    }
    this.iterator = this.map.entrySet().iterator();
  }

  private final ExecutorService executor = Executors.newCachedThreadPool();

  private final class Accessor implements Runnable
  {
    private final Iterator<Map.Entry<String, String>> iterator;

    public Accessor(Iterator<Map.Entry<String, String>> iterator)
    {
      this.iterator = iterator;
    }

    @Override
    public void run()
    {
      while(iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        try
        {
          String st = Thread.currentThread().getName() + " - [" + entry.getKey() + ", " + entry.getValue() + ']';
        } catch (Exception e)
        {
          e.printStackTrace();
        }

      }
    }
  }

  private final class Mutator implements Runnable
  {

    private final Map<String, String> map;
    private final Random random = new Random();

    public Mutator(Map<String, String> map)
    {
      this.map = map;
    }

    @Override
    public void run()
    {
      for (int i = 0; i < 100; i++)
      {
        this.map.remove("key" + random.nextInt(MAP_SIZE));
        this.map.put("key" + random.nextInt(MAP_SIZE), UUID.randomUUID().toString());
      }
    }
  }

  private void run()
  {
    Accessor a1 = new Accessor(this.iterator);
    Accessor a2 = new Accessor(this.iterator);
    Mutator m = new Mutator(this.map);

    executor.execute(a1);
    executor.execute(m);
    executor.execute(a2);
  }
}

Sobald Sie beginnen, dasselbe für Iterator<Map.Entry<String, String>>Accessor- und Mutator-Threads freizugeben, werden java.lang.IllegalStateExceptions angezeigt.

import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentMapIteration
{
  private final Map<String, String> map = new ConcurrentHashMap<String, String>();
  private final Iterator<Map.Entry<String, String>> iterator;

  private final static int MAP_SIZE = 100000;

  public static void main(String[] args)
  {
    new ConcurrentMapIteration().run();
  }

  public ConcurrentMapIteration()
  {
    for (int i = 0; i < MAP_SIZE; i++)
    {
      map.put("key" + i, UUID.randomUUID().toString());
    }
    this.iterator = this.map.entrySet().iterator();
  }

  private final ExecutorService executor = Executors.newCachedThreadPool();

  private final class Accessor implements Runnable
  {
    private final Iterator<Map.Entry<String, String>> iterator;

    public Accessor(Iterator<Map.Entry<String, String>> iterator)
    {
      this.iterator = iterator;
    }

    @Override
    public void run()
    {
      while (iterator.hasNext())
      {
        Map.Entry<String, String> entry = iterator.next();
        try
        {
          String st =
              Thread.currentThread().getName() + " - [" + entry.getKey() + ", " + entry.getValue() + ']';
        } catch (Exception e)
        {
          e.printStackTrace();
        }

      }
    }
  }

  private final class Mutator implements Runnable
  {

    private final Random random = new Random();

    private final Iterator<Map.Entry<String, String>> iterator;

    private final Map<String, String> map;

    public Mutator(Map<String, String> map, Iterator<Map.Entry<String, String>> iterator)
    {
      this.map = map;
      this.iterator = iterator;
    }

    @Override
    public void run()
    {
      while (iterator.hasNext())
      {
        try
        {
          iterator.remove();
          this.map.put("key" + random.nextInt(MAP_SIZE), UUID.randomUUID().toString());
        } catch (Exception ex)
        {
          ex.printStackTrace();
        }
      }

    }
  }

  private void run()
  {
    Accessor a1 = new Accessor(this.iterator);
    Accessor a2 = new Accessor(this.iterator);
    Mutator m = new Mutator(map, this.iterator);

    executor.execute(a1);
    executor.execute(m);
    executor.execute(a2);
  }
}
Boris Pavlović
quelle
Sind Sie sicher, dass die gemeinsame Nutzung des gleichen Iterators zwischen Accessor-Threads zu einem Deadlock führen kann? Das Dokument besagt, dass das Lesen nicht blockiert ist und ich Ihr Programm ausprobiert habe und noch kein Deadlock aufgetreten ist. Obwohl das iterierte Ergebnis falsch sein wird.
Tony
12

Dies bedeutet, dass Sie ein Iteratorobjekt nicht für mehrere Threads freigeben sollten. Das Erstellen mehrerer Iteratoren und deren gleichzeitige Verwendung in separaten Threads ist in Ordnung.

Tuure Laurinolli
quelle
Gibt es einen Grund, warum Sie das Ich in Iterator nicht groß geschrieben haben? Da es sich um den Namen der Klasse handelt, ist dies möglicherweise weniger verwirrend.
Bill Michell
1
@ Bill Michell, jetzt sind wir in der Semantik der Posting-Etikette. Ich denke, er hätte Iterator für einen Iterator zu einem Link zurück zum Javadoc machen oder ihn zumindest in die Inline-Code-Annotationen (`) einfügen sollen.
Tim Bender
10

Dies könnte Ihnen einen guten Einblick geben

ConcurrentHashMap erzielt eine höhere Parallelität, indem die Versprechen an Anrufer leicht gelockert werden. Eine Abrufoperation gibt den Wert zurück, der durch die zuletzt abgeschlossene Einfügeoperation eingefügt wurde, und kann auch einen Wert zurückgeben, der durch eine gleichzeitig laufende Einfügeoperation hinzugefügt wurde (in keinem Fall wird jedoch ein Unsinnsergebnis zurückgegeben). Von ConcurrentHashMap.iterator () zurückgegebene Iteratoren geben jedes Element höchstens einmal zurück und lösen niemals eine ConcurrentModificationException aus, können jedoch Einfügungen oder Entfernungen widerspiegeln, die seit der Erstellung des Iterators aufgetreten sind oder nicht. Es ist keine tabellenweite Sperre erforderlich (oder sogar möglich), um die Thread-Sicherheit beim Iterieren der Sammlung zu gewährleisten. ConcurrentHashMap kann als Ersatz für synchronizedMap oder Hashtable in jeder Anwendung verwendet werden, die nicht auf die Fähigkeit angewiesen ist, die gesamte Tabelle zu sperren, um Aktualisierungen zu verhindern.

Was das betrifft:

Iteratoren können jedoch jeweils nur von einem Thread verwendet werden.

Dies bedeutet, dass die Verwendung von Iteratoren, die von ConcurrentHashMap in zwei Threads erstellt wurden, zwar sicher ist, jedoch zu einem unerwarteten Ergebnis in der Anwendung führen kann.

Nanda
quelle
4

Was heißt das?

Dies bedeutet, dass Sie nicht versuchen sollten, denselben Iterator in zwei Threads zu verwenden. Wenn Sie zwei Threads haben, die über die Schlüssel, Werte oder Einträge iterieren müssen, sollten sie jeweils ihre eigenen Iteratoren erstellen und verwenden.

Was passiert, wenn ich versuche, die Karte mit zwei Threads gleichzeitig zu iterieren?

Es ist nicht ganz klar, was passieren würde, wenn Sie gegen diese Regel verstoßen würden. Sie könnten nur verwirrendes Verhalten bekommen, genauso wie Sie es tun, wenn (zum Beispiel) zwei Threads versuchen, von der Standardeingabe zu lesen, ohne sie zu synchronisieren. Sie könnten auch ein nicht threadsicheres Verhalten erhalten.

Wenn die beiden Threads jedoch unterschiedliche Iteratoren verwendeten, sollte es Ihnen gut gehen.

Was passiert, wenn ich einen Wert während der Iteration in die Karte einfüge oder aus der Karte entferne?

Das ist ein separates Problem, aber der von Ihnen zitierte Javadoc-Abschnitt beantwortet es angemessen. Grundsätzlich sind die Iteratoren threadsicher, es ist jedoch nicht definiert, ob die Auswirkungen gleichzeitiger Einfügungen, Aktualisierungen oder Löschungen in der vom Iterator zurückgegebenen Reihenfolge von Objekten angezeigt werden. In der Praxis hängt es wahrscheinlich davon ab, wo in der Karte die Aktualisierungen stattfinden.

Stephen C.
quelle