Доказательство: почему реализация java.lang.String.hashCode () соответствует его документации? - PullRequest
Новая
       5

Доказательство: почему реализация java.lang.String.hashCode () соответствует его документации?

9 голосов
/ 05 мая 2009

Документация JDK для java.lang.String.hashCode() Famious говорит:

Хеш-код для объекта String вычисляется как 

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

с использованием int арифметики, где s[i] - *i*-й символ строки, n - длина строки, а ^ - возведение в степень.

Стандартная реализация этого выражения: 

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

Глядя на это, я чувствую, что сплю в курсе алгоритмов. Как это математическое выражение переводится в код выше?

Ответы [ 5 ]

24 голосов
/ 05 мая 2009

разверните цикл. Тогда вы получите: 

int hash = 0;

hash = 31*hash + value[0];
hash = 31*hash + value[1];
hash = 31*hash + value[2];
hash = 31*hash + value[3];
...
return hash;

Теперь вы можете сделать некоторые математические манипуляции, вставив 0 для начального значения хеша: 

hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])...

Упростите это еще немного: 

hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]...

И это по сути исходный алгоритм.

12 голосов
/ 05 мая 2009

Я не уверен, что вы пропустили, где в этой документации написано "^ означает возведение в степень" (не xor).

Каждый раз в цикле предыдущее значение хеша умножается на 31 снова перед добавлением к следующему элементу value.

Можно было бы доказать, что эти вещи равны по индукции, но я думаю, что пример может быть более ясно:

Скажем, мы имеем дело со строкой из 4 символов. Давайте развернем цикл: 

hash = 0;
hash = 31 * hash + value[0];
hash = 31 * hash + value[1];
hash = 31 * hash + value[2];
hash = 31 * hash + value[3];

Теперь объедините их в один оператор, подставив каждое значение хэша в следующий оператор: 

hash = 31 * (31 * (31 * (31 * 0 + value[0]) + value[1]) + value[2])
     + value[3];

31 * 0 равно 0, поэтому упростите: 

hash = 31 * (31 * (31 * value[0] + value[1]) + value[2])
     + value[3];

Теперь умножьте два внутренних члена на эту секунду 31: 

hash = 31 * (31 * 31 * value[0] + 31 * value[1] + value[2])
     + value[3];

Теперь умножьте три внутренних члена на эти первые 31: 

hash = 31 * 31 * 31 * value[0] + 31 * 31 * value[1] + 31 * value[2]
     + value[3];

и преобразовать в экспоненты (больше не Java): 

hash = 31^3 * value[0] + 31^2 * value[1] + 31^1 * value[2] + value[3];
10 голосов
/ 05 мая 2009

Доказательство по индукции: 

T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1])
T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s)

Let s be an arbitrary string, and n=|s|
Base case: n = 0
    0 (additive identity, T2(s)) = 0 (T1(s))
    P(0)
Suppose n > 0
    T1(s) = s[n-1] + 31*T1(s[0:n-1])
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1])
    By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so
        s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1])
    P(n)

Я думаю, что у меня есть, и было запрошено доказательство.

9 голосов
/ 05 мая 2009

Посмотрите на первые несколько итераций, и вы увидите, что шаблон начинает появляться: 

hash<sub>0</sub> = 0 + s<sub>0</sub> = s<sub>0</sub>
hash<sub>1</sub> = 31(hash<sub>0</sub>) + s<sub>1</sub> = 31(s<sub>0</sub>) + s<sub>1</sub>
hash<sub>2</sub> = 31(hash<sub>1</sub>) + s<sub>2</sub> = 31(31(s<sub>0</sub>) + s<sub>1</sub>) + s<sub>2</sub> = 31<sup>2</sup>(s<sub>0</sub>) + 31(s<sub>1</sub>) + s<sub>2</sub>
...
0 голосов
/ 21 июля 2013

Разве бесполезно считать хеш-код строки всех символов ? Представьте себе имена файлов или имена классов с их полным путем, помещенным в HashSet. Или кто-то, кто использует документы HashSets of String вместо списков, потому что " HashSet всегда бьет списки ".

Я бы сделал что-то вроде: 

int off = offset;
char val[] = value;
int len = count;

int step = len <= 10 ? 1 : len / 10;

for (int i = 0; i < len; i+=step) {
   h = 31*h + val[off+i];
}
hash = h

В конце хеш-код - не более чем подсказка.

...