Почему хэш-код следующих трех строк одинаков? - PullRequest
Новая
       11

Почему хэш-код следующих трех строк одинаков?

0 голосов
/ 05 ноября 2018

После прочтения исходного кода JDK я все еще удивляюсь, что строки "AaAa", "AaBB" and "BBBB" имеет тот же хеш-код.

Источник JDK следующий: 

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;

Кто-нибудь может уточнить это?

Ответы [ 5 ]

0 голосов
/ 06 ноября 2018

Существует несколько типов хэш-функций с разным дизайном и критериями производительности.

  1. Хеш-функции, используемые для индексации, такие как ассоциативные массивы и аналогичные применения, могут без проблем иметь частые коллизии, потому что код хеш-таблицы будет обрабатывать это в некоторых средствах имен, таких как помещение их в списки или повторное хеширование. Здесь все зависит от производительности во времени. Java hash(), похоже, относится к этому типу

  2. Другой тип функции, такой как криптографический хеш, такой как SHA *, стремится избегать столкновений за счет производительности хеширования.

  3. Тем не менее, третий тип хеш-функций - это хеш-код верификатора пароля, который разработан очень медленно (обычно ~ 100 мс) и может потребовать большого объема памяти, и нечастые коллизии не являются проблемой. Смысл в том, чтобы атаки методом грубой силы были настолько длительными, чтобы быть невозможными.

Один раз выбирает тип и характеристики хэшей в зависимости от использования.

0 голосов
/ 05 ноября 2018

Вот описание из документации Java * метода Object#hashCode:

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

Если два объекта равны в соответствии с методом equals(Object), то вызов метода hashCode для каждого из двух объектов должен привести к одинаковому целочисленному результату.

Не требуется, чтобы, если два объекта были неравны в соответствии с методом java.lang.Object#equals(java.lang.Object), то вызов метода hashCode для каждого из этих двух объектов должен давать различные целочисленные результаты. Однако программист должен знать, что выдача различных целочисленных результатов для неравных объектов может повысить производительность хеш-таблиц.

Итак, реализация класса String также поддерживает вышеуказанные характеристики. Так что это нормальное явление.

0 голосов
/ 05 ноября 2018

Их хэш-коды

AaAa: ((65 * 31 + 97) * 31 + 65) * 31 + 97 = 2.031.744
AaBB: ((65 * 31 + 97) * 31 + 66) * 31 + 66 = 2.031.744
BBBB: ((66 * 31 + 66) * 31 + 66) * 31 + 66 = 2.031.744

Это просто математика, с которой нечего путать.
Обратите внимание на разницу ровно в 31 между 97 и 66, именно поэтому эти хэш-коды так хорошо выстраиваются.

0 голосов
/ 05 ноября 2018

Потому что вероятность .

Существует ~ 4 миллиарда возможных хеш-кодов (Integer.MIN_VALUE -> Integer.MAX_VALUE) и в основном бесконечно много возможных строк. Там должно быть столкновений . Фактически, проблема дня рождения показывает нам , что для высокой вероятности произвольного столкновения требуется всего ~ 77 000 строк , и это было бы, если бы хэш-функция имела чрезвычайно высокую энтропию, которая это не так.

Возможно, вы думаете о криптографической хеш-функции , где

небольшое изменение в сообщении должно изменить значение хеша так экстенсивно, что новое значение хеша кажется не связанным со старым хеш-значение

В этом случае Object.hashCode не предназначен для криптографических целей.

См. Также Насколько безопасен Java hashCode ()?

0 голосов
/ 05 ноября 2018

Так как хэш-код определен для вычисления для String:

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

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

Итак:

  • Для AaAa: 65*31^3 + 97*31^2 + 65*31 + 97 = 2031744
  • Для AaBB: 65*31^3 + 97*31^2 + 66*31 + 66 = 2031744
  • Для BBBB: 66*31^3 + 66*31^2 + 66*31 + 66 = 2031744
...