Czy iteracja wartości ConcurrentHashMap jest bezpieczna dla wątków?

156

W javadoc dla ConcurrentHashMap jest następujący:

Operacje pobierania (w tym get) na ogół nie blokują się, więc mogą nakładać się na operacje aktualizacji (w tym operacje przesyłania i usuwania). Pobieranie odzwierciedla wyniki ostatnio zakończonych operacji aktualizacji, które miały miejsce w momencie ich rozpoczęcia. W przypadku operacji zagregowanych, takich jak putAll i clear, jednoczesne pobieranie może odzwierciedlać wstawianie lub usuwanie tylko niektórych wpisów. Podobnie Iteratory i Enumerations zwracają elementy odzwierciedlające stan tabeli skrótów w pewnym momencie lub od momentu utworzenia iteratora / wyliczenia. Nie zgłaszają wyjątku ConcurrentModificationException. Jednak iteratory są zaprojektowane do używania tylko przez jeden wątek naraz.

Co to znaczy? Co się stanie, jeśli spróbuję iterować mapę z dwoma wątkami w tym samym czasie? Co się stanie, jeśli wstawię lub usunę wartość z mapy podczas jej iteracji?

Palo
źródło

Odpowiedzi:

193

Co to znaczy?

Oznacza to, że każdy iterator uzyskany z a ConcurrentHashMapjest przeznaczony do użytku przez jeden wątek i nie powinien być przekazywany. Obejmuje to cukier syntaktyczny, który zapewnia pętla for-each.

Co się stanie, jeśli spróbuję iterować mapę z dwoma wątkami w tym samym czasie?

Będzie działać zgodnie z oczekiwaniami, jeśli każdy z wątków używa swojego własnego iteratora.

Co się stanie, jeśli wstawię lub usunę wartość z mapy podczas jej iteracji?

To jest zagwarantowane, że rzeczy nie złamie, jeśli nie ten (to część tego, co „równoległy” w ConcurrentHashMapdrodze). Jednak nie ma gwarancji, że jeden wątek zobaczy zmiany mapy, które wykonuje drugi wątek (bez uzyskiwania nowego iteratora z mapy). Iterator gwarantuje, że odzwierciedla stan mapy w momencie jej tworzenia. Dalsze zmiany mogą być odzwierciedlone w iteratorze, ale nie muszą.

Podsumowując, stwierdzenie jak

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

będzie dobrze (lub przynajmniej bezpiecznie) prawie za każdym razem, gdy go zobaczysz.

Waldheinz
źródło
Więc co się stanie, jeśli podczas iteracji inny wątek usunie obiekt o10 z mapy? Czy nadal widzę o10 w iteracji, nawet jeśli zostało usunięte? @Waldheinz
Alex
Jak wspomniano powyżej, tak naprawdę nie jest określone, czy istniejący iterator będzie odzwierciedlał późniejsze zmiany mapy. Więc nie wiem, a według specyfikacji nikt tego nie robi (bez patrzenia na kod, a to może się zmienić przy każdej aktualizacji środowiska wykonawczego). Więc nie możesz na tym polegać.
Waldheinz
8
Ale wciąż mam trochę ConcurrentModificationExceptionczasu na iterację ConcurrentHashMap, dlaczego?
Kimi Chiu
@KimiChiu prawdopodobnie powinieneś zadać nowe pytanie, podając kod wywołujący ten wyjątek, ale wątpię, że wynika to bezpośrednio z iteracji kontenera współbieżnego. chyba że implementacja Java jest wadliwa.
Waldheinz,
18

Możesz użyć tej klasy do przetestowania dwóch wątków uzyskujących dostęp i jednego mutującego współdzieloną instancję ConcurrentHashMap:

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);
  }
}

Żaden wyjątek nie zostanie odrzucony.

Udostępnianie tego samego iteratora między wątkami akcesorów może prowadzić do zakleszczenia:

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);
  }
}

Gdy tylko zaczniesz udostępniać to samo Iterator<Map.Entry<String, String>>między wątkami akcesorów i mutatorów java.lang.IllegalStateException, zaczną pojawiać się s.

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ć
źródło
Czy na pewno „Udostępnianie tego samego iteratora między wątkami akcesorów może prowadzić do zakleszczenia”? Dokument mówi, że odczyt nie jest zablokowany, a ja wypróbowałem twój program i nie doszło jeszcze do impasu. Chociaż wynik iteracji będzie błędny.
Tony
12

Oznacza to, że nie powinieneś udostępniać obiektu iteratora między wieloma wątkami. Tworzenie wielu iteratorów i używanie ich jednocześnie w oddzielnych wątkach jest w porządku.

Tuure Laurinolli
źródło
Jest jakiś powód, dla którego nie wykorzystałeś I w Iteratorze? Ponieważ jest to nazwa klasy, może być mniej zagmatwana.
Bill Michell,
1
@Bill Michell, teraz jesteśmy w semantyce etykiety publikowania. Myślę, że powinien był uczynić Iterator odsyłaczem z powrotem do javadoc dla Iteratora lub przynajmniej umieścić go wewnątrz adnotacji kodu wbudowanego (`).
Tim Bender,
10

To może dać ci dobry wgląd

ConcurrentHashMap osiąga wyższą współbieżność, nieznacznie rozluźniając obietnice składane dzwoniącym. Operacja pobierania zwróci wartość wstawioną przez ostatnią zakończoną operację wstawiania, a także może zwrócić wartość dodaną przez operację wstawiania, która jest równolegle w toku (ale w żadnym wypadku nie zwróci bezsensownego wyniku). Iteratory zwrócone przez ConcurrentHashMap.iterator () zwrócą każdy element najwyżej raz i nigdy nie będą zgłaszać wyjątku ConcurrentModificationException, ale mogą, ale nie muszą, odzwierciedlać wstawienia lub usunięcia, które wystąpiły od czasu skonstruowania iteratora. Nie jest potrzebne (lub nawet możliwe) blokowanie całej tabeli, aby zapewnić bezpieczeństwo wątków podczas iteracji kolekcji. ConcurrentHashMap może być używany jako zamiennik synchronizedMap lub Hashtable w dowolnej aplikacji, która nie polega na możliwości zablokowania całej tabeli, aby zapobiec aktualizacjom.

Odnośnie tego:

Jednak iteratory są zaprojektowane tak, aby były używane tylko przez jeden wątek naraz.

Oznacza to, że używanie iteratorów generowanych przez ConcurrentHashMap w dwóch wątkach jest bezpieczne, może to spowodować nieoczekiwany rezultat w aplikacji.

nanda
źródło
4

Co to znaczy?

Oznacza to, że nie powinieneś próbować używać tego samego iteratora w dwóch wątkach. Jeśli masz dwa wątki, które wymagają iteracji po kluczach, wartościach lub wpisach, każdy z nich powinien utworzyć i używać własnych iteratorów.

Co się stanie, jeśli spróbuję iterować mapę z dwoma wątkami w tym samym czasie?

Nie jest do końca jasne, co by się stało, gdybyś złamał tę zasadę. Możesz po prostu uzyskać mylące zachowanie, w taki sam sposób, jak robisz to, jeśli (na przykład) dwa wątki próbują czytać ze standardowego wejścia bez synchronizacji. Możesz również uzyskać zachowanie niegwintowane.

Ale jeśli dwa wątki używały różnych iteratorów, powinno być dobrze.

Co się stanie, jeśli wstawię lub usunę wartość z mapy podczas jej iteracji?

To osobna kwestia, ale sekcja javadoc, którą zacytowałeś, odpowiednio ją rozwiązuje. Zasadniczo iteratory są bezpieczne dla wątków, ale nie jest zdefiniowane, czy efekty wszelkich jednoczesnych wstawień, aktualizacji lub usunięcia będą odzwierciedlone w sekwencji obiektów zwracanych przez iterator. W praktyce prawdopodobnie zależy to od tego, gdzie na mapie występują aktualizacje.

Stephen C.
źródło