Erro:

Segue o erro:

Exception in thread "Thread-0" Exception in thread "Thread-2" Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 167
    at java.util.ArrayList.add(Unknown Source)
    at Threads.ProduzMensagens.run(ProduzMensagens.java:20)
    at java.lang.Thread.run(Unknown Source)
java.lang.ArrayIndexOutOfBoundsException: 165
    at java.util.ArrayList.add(Unknown Source)
    at Threads.ProduzMensagens.run(ProduzMensagens.java:20)
    at java.lang.Thread.run(Unknown Source)
java.lang.ArrayIndexOutOfBoundsException: 166
    at java.util.ArrayList.add(Unknown Source)
    at Threads.ProduzMensagens.run(ProduzMensagens.java:20)
    at java.lang.Thread.run(Unknown Source)
Exception in thread "main" Threads produtoras de mensagens finalizadas!
java.lang.ArrayIndexOutOfBoundsException: 166
    at java.util.ArrayList.indexOf(Unknown Source)
    at java.util.ArrayList.contains(Unknown Source)
    at Threads.RegistroDeMensagens.main(RegistroDeMensagens.java:29)

segue o código:

package Threads;

import java.util.Collection;

public class ProduzMensagens implements Runnable {

    private int comeco;
    private int fim;
    private Collection<String> mensagens;

    public ProduzMensagens(int comeco, int fim, Collection<String> mensagens) {
        this.comeco = comeco;
        this.fim = fim;
        this.mensagens = mensagens;
    }

    @Override
    public void run() {
        for (int i = comeco; i < fim; i++) {
            mensagens.add("Mensagem " + i);
        }
    }

}

package Threads;

import java.util.ArrayList;
import java.util.Collection;

public class RegistroDeMensagens{

    public static void main(String[] args) throws InterruptedException {

        Collection<String> mensagens = new ArrayList<String>();

         Thread t1 = new Thread(new ProduzMensagens(0, 10000, mensagens));
         Thread t2 = new Thread(new ProduzMensagens(10000, 20000, mensagens));
         Thread t3 = new Thread(new ProduzMensagens(20000, 30000, mensagens));

         t1.start();
         t2.start();
         t3.start();

      // faz com que a thread que roda o main aguarde o fim dessas
         t1.join();
         t2.join();
         t3.join();

         System.out.println("Threads produtoras de mensagens finalizadas!");

         // verifica se todas as mensagens foram guardadas
         for (int i = 0; i < 30000; i++) {
             if (!mensagens.contains("Mensagem " + i)) {
                 throw new IllegalStateException("Não encontrei a mensagem: " + i);
             }
         }

         // verifica se alguma mensagem ficou nula
         if (mensagens.contains(null)) {
             throw new IllegalStateException("Não devia ter null aqui dentro!");
         }

         System.out.println("Fim da execução com sucesso");
     }
}