Tengo un código de prueba como este:

List<Integer> list = new ArrayList<>(1000000);

for(int i=0;i<1000000;i++){
    list.add(i);
}

List<String> values = new ArrayList<>(1000000);

list.stream().forEach(
    i->values.add(new Date().toString())
);

System.out.println(values.size()); 

Al ejecutar esto, obtuve una salida correcta: 1000000.

Sin embargo, si cambio elstream() aparallelStream(), como este:

 list.parallelStream().forEach(
    i->values.add(new Date().toString())
 );

Obtuve una salida aleatoria, por ejemplo: 920821.

Que pasa