Строка Java с хэш-кодом, равным Integer.MIN_VALUE

String#hashCode() определяется как:

Возвращает хэш-код для этой строки. Хэш-код для объекта String вычисляется как

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

используя арифметику int, где s[i] — это i-й символ строки, n — длина строки, а ^ указывает на возведение в степень. (Хеш-значение пустой строки равно нулю.)

Теперь вам просто нужно решить для -2147483648 (возможно, с ограничением только печатных символов ASCII: 32–127) :)

Или вы используете грубую силу (это займет некоторое время):

public class HashFinder {
    private static final int SIZE = 7;
    private static long hashesCalculated = 0L;

    public static void main(String[] args) {
        hashesCalculated = 0L;
        final long start = System.nanoTime();
        findHash(SIZE);
        final long duration = System.nanoTime() - start;

        System.err.println("Checked strings of size " + SIZE);
        System.err.println(hashesCalculated + " hashes in " + TimeUnit.NANOSECONDS.toSeconds(duration) + "s");
    }

    public static void findHash(final int size) {
        findHash("", size);
    }

    public static void findHash(final String prefix, final int size) {
        if (size <= 0) {
            return;
        }

        final StringBuilder sb = new StringBuilder(prefix).append(' ');
        for (char c = ' '; c < '~'; ++c) {
            sb.setCharAt(prefix.length(), c);
            final String s = sb.toString();
            ++hashesCalculated;
            if (s.hashCode() == Integer.MIN_VALUE) {
                System.out.printf("Found string with min hashCode! '%s'%n", s);
            }

            findHash(s, size - 1);
        }
    }
}

Но выделение всех этих строк и компоновщиков строк обходится дорого. Перебор становится возможным, когда мы вычисляем хэш-код вручную из массива символов:

public class HashFinderBytes {
    public static void main(String[] args) {
        final char start = ' ', end = '~';
        for (int size = 1; size <= 9; size++) {
            char[] chars = new char[size];
            Arrays.fill(chars, start);

            final long startNano = System.nanoTime();
            final long combinations = BigInteger.valueOf(end - start).pow(size).longValue();
            System.err.println("Checking " + combinations + " strings of size " + size);
            for (long i = 0; i < combinations; ++i) {
                if (hashCode(chars) == Integer.MIN_VALUE) {
                    System.out.printf("Found string with min hashCode! \"%s\"%n", new String(chars));
                    System.out.println("Sanity check: " + (new String(chars).hashCode() == Integer.MIN_VALUE));
                }
                for (int j = 0; j < chars.length; ++j) {
                    ++chars[j];
                    if (chars[j] <= end) {
                        break;
                    }
                    chars[j] = (byte) start;
                }
            }
            final long duration = System.nanoTime() - startNano;

            final long millis = TimeUnit.NANOSECONDS.toMillis(duration);
            System.err.println("in " + millis + "ms (" + (combinations / millis) + " ops/ms)");
        }
    }

    public static int hashCode(char[] value) {
        int h = 0;
        for (char v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }
}

На самом деле существует множество строк с хэш-кодом, идентичным Integer.MIN_VALUE.

Длина 6:

I='<*!
H\'<*!
G{'<*!
I<F<*!
H[F<*!
GzF<*!
I;e<*!
HZe<*!
Gye<*!
I=&[*!
H\&[*!
G{&[*!
I<E[*!
H[E[*!
GzE[*!
I;d[*!
HZd[*!
Gyd[*!
I=%z*!
H\%z*!
G{%z*!
I<Dz*!
H[Dz*!
GzDz*!
I;cz*!
HZcz*!
Gycz*!
I=';I!
H\';I!
G{';I!
I<F;I!
H[F;I!
GzF;I!
I;e;I!
HZe;I!
Gye;I!
I=&ZI!
H\&ZI!
G{&ZI!
I<EZI!
H[EZI!
GzEZI!
I;dZI!
HZdZI!
GydZI!
I=%yI!
H\%yI!
G{%yI!
I<DyI!
H[DyI!
GzDyI!
I;cyI!
HZcyI!
GycyI!
I=':h!
H\':h!
G{':h!
I<F:h!
H[F:h!
GzF:h!
I;e:h!
HZe:h!
Gye:h!
I=&Yh!
H\&Yh!
G{&Yh!
I<EYh!
H[EYh!
GzEYh!
I;dYh!
HZdYh!
GydYh!
I=%xh!
H\%xh!
G{%xh!
I<Dxh!
H[Dxh!
GzDxh!
I;cxh!
HZcxh!
Gycxh!

Длина 7 (все строки ниже заканчиваются пробелом); не все показано:

p4*|{e 
oS*|{e 
nr*|{e 
p3I|{e 
oRI|{e 
nqI|{e 
p2h|{e 
oQh|{e 
nph|{e 

На основе формулы для хэш-кода (из StringLatin1):

    public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }

это линейно зависит от символов, чем длиннее строка и больше символов, тем больше будет хэш-код, пока не переполнится. Также обратите внимание, что первые символы оказывают большее влияние на итоговый хеш-код (чаще умножаются на 31).

Основная идея двух первых алгоритмов состоит в том, чтобы увеличивать символы до тех пор, пока хеш-код не станет отрицательным, начиная с самого левого символа, поскольку он имеет больший вес. Искомая строка должна иметь символ, предшествующий тому, который вызвал ее переполнение на каждой позиции, кроме последней.

Код начинает проверять строки "A", "AA", "AAA", ..., пока одна из них не начнет возвращать отрицательное значение — предыдущая строка используется в качестве начального значения.
Теперь он начинает увеличивать первый символ до Z или до тех пор, пока не будет найдена строка с отрицательным хешем. То же самое делается для каждого следующего символа. Так как хэш-код таких строк еще не достиг Integer.MIN_VALUE, выполняется дополнительный проход, чтобы также проверить символы нижнего регистра. Это должно было быть интегрировано в предыдущий цикл...
Теперь последний символ настраивается так, чтобы точно получить Integer.MIN_VALUE — просто, поскольку последний символ просто добавляется, без умножения для вычисления хэш-кода.

Вот код:

var string = "A";
while ((string+"A").hashCode() > 0) {
    string += "A";
}

var array = string.toCharArray();
var i = 0;
while (i < array.length) {
    array[i] += 1;
    if (array[i] > 'z' || new String(array).hashCode() < 0) {
        array[i] -= 1;
        i += 1;
        continue;
    }
}

i = 1;
while (i < array.length) {
    if (array[i] == 'Z') {
        array[i] = 'a';
    }else {
        array[i] += 1;
    }
    if (array[i] > 'Z' || new String(array).hashCode() < 0) {
        if (array[i] == 'a')
            array[i] = 'Z';
        else
            array[i] -= 1;
        i += 1;
        continue;
    }
}
int hash = new String(array).hashCode();
if (hash > 0) {
    array[array.length-1] += Integer.MAX_VALUE - hash + 1; 
}
System.out.printf("%s = %d%n", new String(array), new String(array).hashCode());

Это приводит к:

HZcxf_ = -2147483648

Объединяя два цикла увеличения предыдущего кода, мы имеем:

var string = "A";
while ((string+"A").hashCode() > 0) {
    string += "A";
}

var array = string.toCharArray();
var i = 0;
while (i < array.length) {
    var prev = array[i];
    if (prev == 'Z') {
        array[i] = 'a';
    } else {
        array[i] += 1;
    }
    if (array[i] > 'z' || new String(array).hashCode() < 0) {
        array[i] = prev;
        i += 1;
        continue;
    }
}
int hash = new String(array).hashCode();
if (hash > 0) {
    array[array.length-1] += Integer.MAX_VALUE - hash + 1; 
}
System.out.printf("%s = %d%n", new String(array), new String(array).hashCode());

В результате (немного отличается от предыдущего):

HZdZG_ = -2147483648

Другой метод был бы более сильно основан на вычислении хэша, по сути, отменяя его. Поскольку я не хотел работать с отрицательным числом, оно начинается с Integer.MAX_VALUE, что на единицу меньше, чем Integer.MIN_VALUE (с учетом переполнения).
Сначала он выясняет, как часто его нужно делить на 31, пока результат не станет меньше 128 (ASCII), как бы определяя длину строки. Затем он зацикливается и находит каждый символ с некоторой специальной обработкой, чтобы избежать символов меньше ' '.
В конце последний символ увеличивается на единицу, чтобы переместить хэш-код с MAX_VALUE на MIN_VALUE путем переполнения.

var string = "";
var remain = Integer.MAX_VALUE;
var i = 0;
var multiplier = 1;
while (remain > 127) {
    remain /= 31;
    multiplier *= 31;
    i += 1;
}
remain = Integer.MAX_VALUE;
while (i >= 0) {
    var ch = (char)(remain / multiplier);
    remain -= ch * multiplier;
    multiplier /= 31;
    if (i > 0) {
        // correct if next ch will be less than ' '
        var correct = (' ' - (remain / multiplier) + 30) / 31;  // old fashion rounding
        if (correct > 0) {
            ch -= correct;
            remain += correct * 31 * multiplier;
        }
    } else {
        ch += 1;
    }
    string += ch;
    i -= 1;
}
System.out.printf("%s = %d%n", string, string.hashCode());

И его результаты:

I='<*! = -2147483648

Примечание: последний код окончательно не сработает, если изменить алгоритм хэш-кода String! Предыдущие два могут завершиться ошибкой, в зависимости от того, как изменено вычисление хэша.