Здравствуйте, Аноним, Вы писали:

А>Добрый день, вы не могли бы на пальцах объяснить почему в функции для нахождения hash, пример для String:


А>int hash = 0;
А>for (char ch : str.toCharArray()) {
А> hash = hash * 31 + ch;
А>}

А>нужно использовать простое число (31 в нашем случае)
А>точнее, я догадываюсь, что так как используется не операция нахождения остатка после деления hash на длину hash таблицы, а битовая маска. т.к. эта операция эффективнее
А>меня интересует именно, почему простое число должно использоваться.
А>с битами не оч. силен, если можно в примере покажите...

Хеши должны обладать такой интересной особенностью, что для двух похожих структур, желательно давать различные результаты(чем более различные тем лучше).
Тогда на реальных, скорее всего упорядоченных данных(не очень рандомных) не будет коллизий.

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

Пусть в качестве множителя мы выбрали число K(в яве оно 31).

Теперь рассмотрим такой простой ряд строк — предложения русского языка с точкой в конце(пример немного надуман, но при желании его можно обобщить)

"[рандомная-часть строки].","[рандомная-часть строки].", "[рандомная-часть строки]."

Во всех строках последний символ одинаковый — ".", и есть некоторый различный префикс. Префикс всегды будет делиться на K.

Т.е. хеш код всех таких функций по модулю K будет одинаковым.

Будет много коллизий, если у K и у длины хеш-таблицы будет общий множитель.

Ну а чтобы минимизировать вероятность появления общих множителей при расширении хеш-таблицы, проще всего в качестве K взять простое число.

Я это как-то так себе представляю.