Строка hashCode () документация против реализации - PullRequest
Новая
       12

Строка hashCode () документация против реализации

0 голосов
/ 03 мая 2018

Ниже приведен фрагмент исходного кода метода String.hashCode() из Java 8 (точнее, 1.8.0_131) 

<code>/**
 * Returns a hash code for this string. The hash code for a
 * {@code String} object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 *
* используя арифметику {@code int}, где {@code s [i]} * i -й символ строки, {@code n} - длина * строка, а {@code ^} обозначает возведение в степень. * (Хеш-значение пустой строки равно нулю.) * * @ вернуть значение хеш-кода для этого объекта. * / public int hashCode () { int h = хэш; if (h == 0 && value.length> 0) { char val [] = значение; for (int i = 0; i

Вы можете видеть, что в документации сказано, что hashCode() вычисляется по следующей формуле 

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

в то время как фактическая реализация отличается 

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

Я что-то упускаю из виду? Пожалуйста, помогите мне.

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

Проще всего увидеть, что происходит с некоторым примером. Давайте возьмем строку s длины n и все обозначения, как указано выше. Мы проанализируем итерацию цикла для итерации. Мы назовем h_old значение h в начале текущей итерации, а h_new значение h в конце текущей итерации. Легко видеть, что h_new итерации i будет h_old итерации i + 1. 

╔═════╦════════════════════════════╦═════════════════════════════════════════════════╗
║ It. ║ h_old                      ║ h_new                                           ║
╠═════╬════════════════════════════╬═════════════════════════════════════════════════╣
║ 1   ║ 0                          ║ 31*h_old + s[0] =                               ║
║     ║                            ║          s[0]                                   ║
║     ║                            ║                                                 ║
║ 2   ║ s[0]                       ║ 31*h_old + s[1] =                               ║
║     ║                            ║ 31      *s[0] +          s[1]                   ║
║     ║                            ║                                                 ║
║ 3   ║ 31  *s[0] +    s[1]        ║ 31^2    *s[0] + 31      *s[1] +    s[2]         ║
║     ║                            ║                                                 ║
║ 4   ║ 31^2*s[0] + 31*s[1] + s[2] ║ 31^3    *s[0] + 31^2    *s[1] + 31*s[2] + s[3]  ║
║ :   ║ :                          ║ :                                               ║
║ n   ║ ...                        ║ 31^(n-1)*s[0] + 31^(n-2)*s[1] + ... + 31^0*s[n] ║
╚═════╩════════════════════════════╩═════════════════════════════════════════════════╝

(таблица, сгенерированная с помощью Senseful )

Степени 31 создаются через цикл и постоянное умножение h на 31 (с использованием дистрибутивности умножения). Как вы можете видеть в последнем ряду таблицы, это именно то, что сказано в документации.

0 голосов
/ 03 мая 2018

Реализация правильная, с оговоркой, что может произойти переполнение целых чисел (что здесь нормально, это ничего не вредит). Он использует метод Хорнера для полиномиальной оценки.

Вот шаги на примере строки "CAT". 

h = 0

Первый цикл: 

i = 0
h = 31 * 0 + 'C' (67) = 67

Второй цикл: 

i = 1
h = 31 * 67 + 'A' (65) = 2142

Третий цикл: 

i = 2
h = 31 * 2142 + 'T' (84) = 66486

Давайте выведем формулу из кода. Здесь n - это индекс i в строку s . Каждая итерация цикла for выполняет эту формулу.

ч n = 31 ч n-1 + s n 

h0 /* after loop i = 0 */ = s[0]
h1 /* after loop i = 1 */ = 31*h0 + s[1] = 31*s[0] + s[1]
h2 /* after loop i = 2 */ = 31*h1 + s[2] = 31*(31*s[0] + s[1]) + s[2]
h = 31*31*s[0] + 31*s[1] + s[2]

Показатели степени 31, которые вы видите, возникают потому, что каждый цикл умножается на еще один коэффициент 31 перед добавлением значения следующего символа.

...