Найти строку столкновения с заданной хэш-функцией
У меня есть строка annaгде значения символов в строке a = 1, n = 14 ( You can compute the value of other chars like ( char - 96 ) и хэш-функция, которая выглядит так:
int hashCode( string s ) // s = "anna";
{
k = 0;
for ( int i = 0; i < s.length(); i++ )
k = ( 7 * k + 3 * s[i] ) % 61;
return k;
}
Как мне найти строку длины 3, где происходит столкновение (что-то умное)? Единственный способ, который приходит мне в голову, это рассчитать k из anna который 29 а потом как-то придумать другую строку длиной 3, которая дает 29,
Решение
Почему бы вам просто не сгенерировать все строки длины 3 и не вычислить их хэши (на самом деле вы можете остановиться, когда все 61 возможное значение хеш-функций могут быть достигнуты)? Количество вариантов не слишком велико.
Одна возможная оптимизация: если вам нужно ответить на несколько запросов (например, по заданной строке, найти строку длины 3 с тем же значением хеш-функции), вы можете сгенерировать все строки длины 3 и вычислить их хеши один раз, чтобы построить карту hash -> a string of length 3 with this hash, Если у вас есть эта карта, поиск строки длиной 3 с таким же хешем, что и у заданного, — всего лишь один поиск по карте.
Другие решения
Других решений пока нет …