Q:

Comparar 2 listas de millones de valores en java

Tengo 2 listas cada una con mas de 4 millones de valores(distintos tamaños), se necesita comparar ambas listas y obtener una lista que tenga los valores iguales, sin embargo demora mucho tiempo.
¿Qué alternativas puedo optar? ¿hilos?
Las listas no están ordenadas, no son del mismo tamaño pero si grandes, son string.
lista1 = {id4, id8,id2, id1,....} 
lista2 = {zzzzzz_id8, bbbb_id5, ccc_id7, fffffffff_id2,....}

    private static List<String> compara(List<String> lista1, List<String> lista2) {
    List<String> iguales= new ArrayList<>();
    lista1.stream().forEach(
            (a) -> {
                lista2.stream()
                        .filter(b -> b.contains(a))
                        .forEach(iguales::add);
            }
    );
    return iguales;
}

A:

veo que usas dos foreach entonces quizá eso este afectando el rendimiento. Ya que usas Java 8 podrías usar retainAll
El método retainAll de ArrayList se usa para eliminar todos los elementos de la lista de la matriz que no están contenidos en la colección especificada o retiene todos los elementos coincidentes en la instancia actual de ArrayList que coinciden con todos los elementos de la lista de Colección pasados ​​como parámetro al método. 
List<String> listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
        List<String> listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));

        listOne.retainAll( listTwo );
        System.out.println( listOne );

OutPut
[dingo, hafil, iga]

