Полиномиальная хеш-функция

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

Идея полиномиальной хеш-функции

Основная идея заключается в том, чтобы представить строку как многочлен с коэффициентами, равными числовым значениям символов строки. Затем этот многочлен вычисляется по модулю некоторого большого числа, что позволяет избежать переполнения и равномерно распределяет хеш-значения.

Формула полиномиальной хеш-функции

Полиномиальная хеш-функция для строки $s$ длиной $n$ символов может быть определена как: $H (s) = (s [0] \cdot p^{n - 1} + s [1] \cdot p^{n - 2} + \dots + s [n - 2] \cdot p + s [n - 1]) mod m$ где:

$s [i]$ — числовое значение $i$ -го символа строки.
$p$ — некоторое фиксированное простое число (обычно используется значение 31 или 37).
$m$ — большое простое число для вычисления остатка (например, $2^{32} - 1$ или другое большое простое число).

Пример реализации на C++

Ниже приведен пример реализации полиномиальной хеш-функции на языке C++:

#include <iostream>
#include <string>
 
unsigned int polynomialHash(const std::string &key, int prime = 31, int mod = 1000000007) {
    unsigned int hash = 0;
    unsigned int power = 1;
    
    for (char ch : key) {
        hash = (hash + (ch * power) % mod) % mod;
        power = (power * prime) % mod;
    }
    
    return hash;
}
 
int main() {
    std::string key1 = "hello";
    std::string key2 = "world";
    std::string key3 = "polynomial";
    std::string key4 = "hash";
 
    std::cout << "Hash of " << key1 << " : " << polynomialHash(key1) << std::endl;
    std::cout << "Hash of " << key2 << " : " << polynomialHash(key2) << std::endl;
    std::cout << "Hash of " << key3 << " : " << polynomialHash(key3) << std::endl;
    std::cout << "Hash of " << key4 << " : " << polynomialHash(key4) << std::endl;
 
    return 0;
}

Объяснение кода

Функция polynomialHash:
- Принимает строку key, простое число prime (по умолчанию 31) и модуль mod (по умолчанию 1000000007).
- Инициализирует переменную hash для хранения итогового хеш-значения и переменную power, представляющую текущую степень простого числа.
Цикл по символам строки:
- Для каждого символа ch строки key:
  - Обновляет hash, добавляя произведение символа и текущей степени простого числа prime, взятое по модулю mod.
  - Обновляет power, умножая его на prime и взяв по модулю mod.
Функция main:
- Определяет несколько строк и вычисляет их хеш-значения, выводя результаты на экран.

Преимущества полиномиальной хеш-функции

Простота и эффективность: Легко реализуется и быстро вычисляется.
Равномерное распределение: Обеспечивает хорошее распределение хеш-значений для большинства строк.
Устойчивость к коллизиям: При правильном выборе простого числа $p$ и модуля $m$ вероятность коллизий уменьшается.

Недостатки полиномиальной хеш-функции

Чувствительность к выбору параметров: Результаты зависят от выбора $p$ и $m$ , что требует тщательного подбора этих значений.
Проблемы с переполнением: Без использования модуля $m$ вычисления могут приводить к переполнению целых чисел.

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

m4lvx

Explorer