Атака на String.hashCode: прообразы и коллизии

До Java 1.2 хеш-функция строки была другой:

public int hashCode() {
    int h = 0;
    int off = offset;
    char val[] = value;
    int len = count;

    if (len < 16) {
        for (int i = len ; i > 0; i--) {
            h = (h * 37) + val[off++];
        }
    } else {
        // only sample some characters
        int skip = len / 8;
        for (int i = len ; i > 0; i -= skip, off += skip) {
            h = (h * 39) + val[off];
        }
    }
    return h;
}

Она была медленнее, коллизии для неё подобрать было ещё легче, для строк длиннее 15 символов учитывался лишь каждый S.length() / 8 символ, да ещё и в Java Language Specification была ошибка.

Потом это обнаружили и Джош Блох предложил всё переделать, детали в JDK-4045622.

Откуда взялся коэффициент 31, и почему решили считать именно так?

Приведу несколько цитат из вышеупомянутого issue:

The class of hash function that I recommend using is polynomials whose
coefficients are the characters in the string:

P(x) = s[0] * x^(n-1) + s[1] * x^(n-2) +… + s[n-1]

The value of x is part of the definition of the hash function; choosing
this value is somewhat of a black art.

While this class of hash function is recommended in The Dragon Book
(P(65599)) and Kernighan and Ritchie's «The C Programming Language, 2 Ed.»
(P(31)), it is not attributed in either of these books.

I went so far as to call up Dennis Ritchie, who said that he did not know where the hash function came from. He walked across the hall and asked Brian Kernighan, who also had no recollection.

I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two).

Откуда взялось 31 не помнят даже Керниган и Ричи. Чёрная магия, как она есть.
Если тема интересна, то стоит прочитать все комментарии к JDK-4045622 по ссылке выше.