Лжеотождествление электровиолончели

Сделайте и замерьте :-) Можно ещё проще поступить — насчитать все нужные степени в таблицу, их немного. Будет ещё быстрее. А ещё вероятно стоит освоить деление в кольце вычетов. Думаю, для конкретных констант (31 и 2³²) можно получить конкретную формулу. Тогда по всем длинам пробегаться не придётся, будет ещё быстрее.

В данном случае задача одноразовая, поэтому общее время складывается из времени работы программы и времени работы программиста.

Собственно, идея с дискретным делением оказалась не такая сложная. Умножению на 31 для чисел int обратной операцией будет умножение на -1108378657 (удивительно, правда?). Можно переписать программу так:

import java.nio.charset.Charset;
import java.nio.file.*;
import java.util.*;
import java.util.stream.*;

public class PhraseHashCode3 {
    public static void main(String[] args) throws Exception {
        int target = Integer.MIN_VALUE;
        String[] preps = { "в", "и", "с", "по", "на", "под", "над", "от", "из",
                "через", "перед", "за", "до", "о", "не", "или", "у", "про", "для" };
        List<String> infixes = Stream.concat(Stream.of(" "), Arrays.stream(preps).map(p -> ' '+p+' '))
                .collect(Collectors.toList());
        List<String> words = Files.readAllLines(Paths.get("litf-win.txt"), Charset.forName("cp1251")).stream()
                .map(s -> s.substring(0, s.indexOf(' ')))
                .filter(s -> s.length() > 2)
                .collect(Collectors.toList());
        Map<Integer, List<String>> hashPrefix = words.stream()
                .map(s -> Character.toTitleCase(s.charAt(0)) + s.substring(1))
                .collect(Collectors.groupingBy(String::hashCode));
        words.stream()
                .flatMap(s -> infixes.stream().map((String infix) -> infix+s))
                .flatMap(s -> hashPrefix.getOrDefault(
                            IntStream.range(0, s.length()).reduce(target - s.hashCode(), (a, i) -> a*-1108378657), 
                            Collections.emptyList()).stream().map(prefix -> prefix+s))
                .sorted().forEach(System.out::println);
    }
}

Результат такой же, зато и короче, и быстрее (у меня раза в 4-5 прирост скорости).

Прошу прощения, это для нуля. Вот int.MinValue:

"вручить подкрякивать".GetHashCode() == int.MinValue