Блог

Метод MAD (умножение-сложение-деление) вычисляет хэш следующим образом для некоторого значения x ,
h(x) = ((ax b) mod p) mod N
где p — простое число, большее, чем N , a и b — несколько случайных целых чисел в диапазоне [1, p-1] и N — размер хеш-таблицы.

Как мне вычислить хэш строкового значения? Я не уверен, должен ли я вычислять хэш строки (например, на основе значения места), а затем использовать метод MAD или есть другой способ?

Что я пробовал? Я хочу реализовать функцию int hash(str) , которая вернет значение хэша. Я написал int hash(int x, int N) , но здесь я отправляю предварительно рассчитанное x на основе ASCII значение символов в строке.

Я могу придумать два разумных способа сделать это.

1. Обрабатывайте каждый символ как его собственное число (многие языки программирования имеют эту ord функцию) и объединяйте оценки h is таким образом, чтобы, например, вы использовали значение для a или b как результат предыдущего результата h .
2. Обрабатывайте всю строку как одно число. Вы можете преобразовать строку в массив байтов, который может быть преобразован с помощью какой-либо библиотеки больших целых чисел в одно число. Это может быть использовано в качестве входных данных, для h которых затем должно быть реализовано с той же библиотекой больших целых чисел.

Невозможно сказать, какой из этих двух методов быстрее. Я бы предположил, что это первый, но оба они не гарантируют никаких свойств, подобных криптографической хеш-функции. Есть еще много способов сделать это.