O segmento de valores ConcurrentHashMap iterativo é seguro?

156

No javadoc para ConcurrentHashMap, é o seguinte:

As operações de recuperação (incluindo get) geralmente não são bloqueadas, portanto, podem se sobrepor às operações de atualização (incluindo colocar e remover). As recuperações refletem os resultados das operações de atualização concluídas mais recentemente, mantidas após o início. Para operações agregadas, como putAll e clear, as recuperações simultâneas podem refletir a inserção ou remoção de apenas algumas entradas. Da mesma forma, Iteradores e Enumerações retornam elementos que refletem o estado da tabela de hash em algum momento na ou desde a criação do iterador / enumeração. Eles não lançam ConcurrentModificationException. No entanto, os iteradores são projetados para serem usados ​​por apenas um encadeamento por vez.

O que isso significa? O que acontece se eu tentar iterar o mapa com dois threads ao mesmo tempo? O que acontece se eu colocar ou remover um valor do mapa enquanto o iterar?

Palo
fonte

Respostas:

193

O que isso significa?

Isso significa que cada iterador que você obtém de um ConcurrentHashMapé projetado para ser usado por um único encadeamento e não deve ser passado adiante. Isso inclui o açúcar sintático fornecido pelo loop for-each.

O que acontece se eu tentar iterar o mapa com dois threads ao mesmo tempo?

Funcionará como esperado se cada um dos threads usar seu próprio iterador.

O que acontece se eu colocar ou remover um valor do mapa enquanto o iterar?

É garantido que as coisas não vão quebrar se você fizer isso (isso faz parte do que significa "simultâneo" ConcurrentHashMap). No entanto, não há garantia de que um segmento veja as alterações no mapa que o outro segmento executa (sem obter um novo iterador no mapa). O iterador é garantido para refletir o estado do mapa no momento de sua criação. Outras mudanças podem ser refletidas no iterador, mas elas não precisam ser.

Em conclusão, uma declaração como

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

ficará bem (ou pelo menos seguro) quase toda vez que você o vir.

Waldheinz
fonte
Então, o que acontecerá se, durante a iteração, outro thread remover um objeto o10 ​​do mapa? Ainda posso ver o10 na iteração, mesmo que ela tenha sido removida? @Waldheinz
Alex
Como mencionado acima, não é realmente especificado se um iterador existente refletirá alterações posteriores no mapa. Então, eu não sei, e por especificação, ninguém sabe (sem olhar o código, e isso pode mudar a cada atualização do tempo de execução). Então você não pode confiar nisso.
Waldheinz
8
Mas ainda tenho um ConcurrentModificationExceptiontempo repetindo a ConcurrentHashMap, por quê?
Kimi Chiu
@KimiChiu, você provavelmente deve postar uma nova pergunta, fornecendo o código que aciona essa exceção, mas eu duvido que ela decorra diretamente da iteração de um contêiner simultâneo. a menos que a implementação do Java seja com erros.
Waldheinz
18

Você pode usar esta classe para testar dois threads de acesso e um mutando a instância compartilhada de 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);
  }
}

Nenhuma exceção será lançada.

Compartilhar o mesmo iterador entre os segmentos do acessador pode levar a um conflito:

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

Assim que você começar a compartilhar o mesmo Iterator<Map.Entry<String, String>>entre threads de acessador e mutadorjava.lang.IllegalStateException , começará a aparecer.

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ć
fonte
Tem certeza de que 'Compartilhar o mesmo iterador entre os segmentos do acessador pode levar a um conflito'? O documento diz que a leitura não está bloqueada e eu tentei o seu programa e nenhum conflito ainda acontece. Embora o resultado iterado esteja errado.
Tony
12

Isso significa que você não deve compartilhar um objeto iterador entre vários encadeamentos. Criar vários iteradores e usá-los simultaneamente em threads separados é bom.

Tuure Laurinolli
fonte
Algum motivo para você não capitalizar o I no Iterator? Como é o nome da classe, pode ser menos confuso.
Bill Michell
1
@ Bill Michell, agora estamos na semântica de postar etiqueta. Eu acho que ele deveria ter feito do Iterator um link para o javadoc para um Iterator ou, no mínimo, colocado dentro das anotações do código embutido (`).
Tim Bender
10

Isso pode lhe dar uma boa ideia

O ConcurrentHashMap alcança maior concorrência ao relaxar levemente as promessas que faz aos chamadores. Uma operação de recuperação retornará o valor inserido pela operação de inserção concluída mais recente e também poderá retornar um valor adicionado por uma operação de inserção que esteja em andamento simultaneamente (mas em nenhum caso retornará um resultado sem sentido). Os iteradores retornados por ConcurrentHashMap.iterator () retornam cada elemento no máximo uma vez e nunca lançam ConcurrentModificationException, mas podem ou não refletir inserções ou remoções que ocorreram desde que o iterador foi construído. Nenhum bloqueio em toda a tabela é necessário (ou mesmo possível) para fornecer segurança de thread ao iterar a coleção. O ConcurrentHashMap pode ser usado como um substituto para o synchronizedMap ou o Hashtable em qualquer aplicativo que não dependa da capacidade de bloquear a tabela inteira para impedir atualizações.

Em relação a este:

No entanto, os iteradores são projetados para serem usados ​​por apenas um encadeamento por vez.

Isso significa que, embora o uso de iteradores produzidos pelo ConcurrentHashMap em dois threads seja seguro, isso pode causar um resultado inesperado no aplicativo.

Nanda
fonte
4

O que isso significa?

Isso significa que você não deve tentar usar o mesmo iterador em dois threads. Se você tiver dois threads que precisam iterar sobre as chaves, valores ou entradas, cada um deles deve criar e usar seus próprios iteradores.

O que acontece se eu tentar iterar o mapa com dois threads ao mesmo tempo?

Não está totalmente claro o que aconteceria se você quebrasse essa regra. Você poderia obter um comportamento confuso, da mesma maneira que faria se (por exemplo) dois threads tentassem ler da entrada padrão sem sincronizar. Você também pode obter um comportamento não thread-safe.

Mas se os dois threads usaram iteradores diferentes, você deve estar bem.

O que acontece se eu colocar ou remover um valor do mapa enquanto o iterar?

Essa é uma questão separada, mas a seção javadoc que você citou responde adequadamente. Basicamente, os iteradores são seguros para threads, mas não está definido se você verá os efeitos de inserções, atualizações ou exclusões simultâneas refletidas na sequência de objetos retornados pelo iterador. Na prática, provavelmente depende de onde no mapa as atualizações ocorrem.

Stephen C
fonte