Приведи пример хеш функции для строки

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

Пример хеш-функции для строки

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

Формула для вычисления хеша может быть следующей:

[ \text{hash}(s) = (s[0] \times b^{n-1} + s[1] \times b^{n-2} + \ldots + s[n-1] \times b^0) \mod m ]

где:

• ( s[i] ) — ASCII-код i-го символа строки,
• ( n ) — длина строки,
• ( b ) — основание (обычно выбирается как простое число, например, 31 или 37),
• ( m ) — модуль, чтобы избежать переполнения (обычно большое простое число).

Пример кода на C++

#include <iostream>
#include <string>
​
// Функция для вычисления хеша строки
unsigned long long hashString(const std::string& str) {
    const int b = 31; // Основание
    const int m = 1e9 + 9; // Модуль
    unsigned long long hashValue = 0; // Начальное значение хеша
    unsigned long long power = 1; // Текущая степень основания
​
    // Проходим по каждому символу строки
    for (char c : str) {
        // Обновляем значение хеша
        hashValue = (hashValue + (c - 'a' + 1) * power) % m;
        // Обновляем степень основания
        power = (power * b) % m;
    }
​
    return hashValue; // Возвращаем вычисленный хеш
}
​
int main() {
    std::string input = "example"; // Пример строки
    std::cout << "Hash of '" << input << "' is: " << hashString(input) << std::endl;
    return 0;
}

Пояснение к коду

1. Константы b и m:

   • b — это основание, выбранное как 31. Это простое число, что помогает равномерно распределять хеши.
   • m — модуль, используемый для предотвращения переполнения. Выбрано большое простое число (10^9 + 9).

2. Переменные hashValue и power:

   • hashValue — начальное значение хеша, изначально равно 0.
   • power — текущая степень основания, изначально равна 1.

3. Цикл по символам строки:

   • Для каждого символа c строки str:
     • Обновляется hashValue с учетом ASCII-кода символа, сдвинутого так, чтобы 'a' соответствовала 1.
     • Обновляется power для следующей степени основания.

4. Возврат значения:

   • Функция возвращает вычисленный хеш строки.

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