Хорнера хеширования

Question

Я знаю, как получить значение хэширования строки метода Wich Хорнера занимает три paramettres String str , int p (prime) and int м как этого

p(str)=(sumOf(str(0)+str(1)*M+....+str(n)*M^n))%p = hashVal 

, но проблема заключается в том, чтобы получить строку строки, давая только hashVal, p и M например, если я даю вам hashval=7, p = 11 и M = 2, вы должны указать мне строку, например «hello» (не правильно, просто предложение для понимания) Я имею в виду, что я не знаю, как это сделать обратный и с вашей помощью

Answer 1

Вы не можете получить уникальный ввод хеша, который вы описываете, поскольку операция по модулю выводит информацию. Если вы знали, что хэшвал равен 7, M = 2 и p = 11, как в вашем примере, вы бы не знали, было ли sumOf (...) равным 7 или 18 или так далее.

Даже если вы это сделали, скажите, что вы знали, что это 5, для примера 2-символьной строки вы не сможете решить, была ли str (0) равной 1, а str (1) - 2, например, или str (0) равно 5, а str (1) равно 0.

Хеши обычно трудно или невозможно отменить, особенно однозначно. Самый простой способ их решения - хешировать все возможные входы и проверять их выходы. В итоге у вас будет много входов с одним и тем же hashVal (если p в вашем примере - 3, есть только 3 разных хэша).