Uma história de dois iteradores: estratégias de modificação competitiva em Java

O autor da nota é Grzegorz Mirek, desenvolvedor de software de Cracóvia (Polônia). Ele começou a desenvolver em Java há cerca de 6 anos, ainda na universidade, e desde então vem aprimorando incansavelmente suas habilidades nesta área. Ele está particularmente interessado em desempenho e otimização de JVM, sobre o qual ele escreve principalmente em seu blog . Algumas das perguntas mais populares das entrevistas sobre Java incluem: Qual é a diferença entre iteradores rápidos e à prova de falhas? A resposta mais simplificada para isso é: Um iterador à prova de falhas lança uma ConcurrentModificationException se a coleção for alterada durante a iteração, mas um iterador à prova de falhas não. Embora isto pareça bastante significativo, ainda não está claro o que o entrevistador quer dizer com segurança contra falhas. As especificações da linguagem Java não definem este termo em relação aos iteradores. No entanto, existem quatro estratégias de modificação competitiva.

Modificação competitiva

Primeiro, vamos definir o que é modificação competitiva (ou paralela). Digamos que temos uma coleção e quando o iterador está ativo ocorrem algumas alterações que não vêm deste iterador. Neste caso, obtemos uma modificação competitiva. Deixe-me dar um exemplo simples: digamos que temos vários threads. O primeiro thread itera e o segundo thread insere ou remove elementos da mesma coleção. No entanto, podemos obter uma ConcurrentModificationException ao executar em um ambiente de thread único:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Falha rápida

O fragmento de código acima é um exemplo de iterador rápido . Como você pode ver, uma ConcurrentModificationException foi lançada ao tentar recuperar o segundo elemento do iterator . Como um iterador sabe que a coleção foi modificada desde que foi criada? Por exemplo, a coleção pode ter um carimbo de data/hora, digamos lastModified . Ao criar um iterador, você deve copiar este campo e armazená-lo em um objeto iterador. Então, cada vez que você chamar o método next() , você simplesmente comparará o valor lastModified da coleção com a cópia do iterador. Uma abordagem muito semelhante é usada, por exemplo, na implementação da classe ArrayList . Possui uma variável de instância modCount que armazena o número de vezes que a lista foi modificada:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

É importante observar que os iteradores fail-fast operam com base nos melhores, o que significa que não há garantia de que uma ConcurrentModificationException será lançada no caso de uma modificação simultânea. Portanto, você não deve confiar neles - em vez disso, eles devem ser usados ​​para detectar erros. A maioria das coleções não simultâneas fornece iteradores à prova de falhas .

Consistência Fraca

A maioria das coleções simultâneas no pacote java.util.concurrent (como ConcurrentHashMap e a maioria das Queue ) fornecem iteradores fracamente consistentes. O significado deste termo está muito bem explicado na documentação :

• Eles podem ser processados ​​simultaneamente com outras operações
• Eles nunca lançam uma ConcurrentModificationException
• É garantido que eles atravessem os elementos existentes no momento em que o iterador foi criado exatamente uma vez e podem (mas não são obrigados a) refletir modificações subsequentes.

Instantâneo

Com esta estratégia, o iterador está associado ao estado da coleção no momento da sua criação - este é um instantâneo da coleção. Quaisquer alterações feitas na coleção original resultam na criação de uma nova versão da estrutura de dados subjacente. Isso deixa nosso instantâneo inalterado, portanto não reflete as alterações na coleção que ocorreram após a criação do iterador. Esta é a boa e velha técnica copy-on-write (COW) . Resolve completamente o problema de modificações simultâneas, portanto, uma ConcurrentModificationException não é gerada com esta abordagem. Além disso, os iteradores não suportam operações que alteram elementos. Coleções de cópia na gravação tendem a ser muito caras para usar, mas faz sentido usá-las se as alterações ocorrerem com muito menos frequência do que as travessias do iterador. Exemplos são as classes CopyOnWriteArrayList e CopyOnWriteArraySet .

Comportamento indefinido

Você pode encontrar um comportamento indefinido em tipos de coleções herdadas, como Vector e Hashtable . Ambos possuem iteradores fail-fast padrão , mas além disso, permitem o uso de implementações da interface Enumeration , e não sabem como se comportar em caso de modificação concorrente. Você pode encontrar alguns elementos repetidos ou ausentes, ou até mesmo algumas exceções estranhas. É melhor não brincar com eles!