Что позади метода hashCode() для String в Java?

Я исследовал методы hashCode() в java и нашел странным для класса String. Исходный код выглядит следующим образом:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Сам код довольно прямолинейный. Но интересно, какая причина для вычисления хеш-кода таким образом?
Почему нужно выбрать 31?
Почему начинаются с 0 вместо value.length - 1?
Любая гарантия того, что это сделает хэш-коды менее возможными, чтобы столкнуться с друг друга?

Ответы

Ответ 1

Да вероятность столкновения хэш-кодов очень низкая, например, в случае String это зависит от строкового значения. Если мы не создаем String с новым оператором, то если новая String имеет то же самое значение, которое уже присутствует, то новый объект String не создается, он ссылается на старое значение из кучи, и в этом случае только значение hashCode будет быть таким же, как ожидалось.

Общий контракт hashCode:

Всякий раз, когда он вызывается одним и тем же объектом более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если информация, используемая при равных сравнениях с объектом, не изменяется. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение того же приложения.

Из Java 1.2 класс java.lang.String реализует свой hashCode() с использованием алгоритма суммирования продукта по всему тексту строки. [2] Например, для экземпляра s класса java.lang.String будет иметь хэш-код h (s), определенный

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

где термины суммируются с использованием 32-битового добавления Java, s [i] обозначает i-й символ строки, а n - длину s.

Для вашей справки в Apache Harmony метод hashCode:

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}