README.ru-RU.md

Полиномиальный скользящий хэш

Хэш-функция

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

Основным применением хеширования является эффективная проверка равенства ключей путем сравнения их хеш-суммой.

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

Скользящий хеш

Скользящий хэш (также известный как рекурсивное хэширование или скользящая контрольная сумма) - это хэш -функция, при которой входные данные хэшируются в окне, которое перемещается по входным данным.

Несколько хеш—функций позволяют очень быстро вычислять переходящий хеш-код - новое значение хеш-кода быстро вычисляется, учитывая только следующие данные:

• старое значение хеш-кода,
• старое значение, удаленное из окна,
• и новое значение, добавленное в окно.

Полиномиальное хеширование строк

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

Алгоритм поиска строк Рабина–Карпа часто объясняется с помощью очень простой скользящей хэш-функции, которая использует только умножение и сложение - полиномиальный скользящий хэш:

H(s₀, s₁, ..., s_k) = s₀ * p^k-1 + s₁ * p^k-2 + ... + s_k * p⁰

где p - константа, а (s₁, ... , s_k) - входные символы.

Например, мы можем преобразовать короткие строки в ключевые числа, умножив цифровые коды на степени константы. Трехбуквенное слово ace можно преобразовать в число, вычислив:

ключ = 1 * 26² + 3 * 26¹ + 5 * 26⁰

Чтобы избежать манипулирования огромными значениями H, вся математика выполняется по модулю M.

H(s₀, s₁, ..., s_k) = (s₀ * p^k-1 + s₁ * p^k-2 + ... + s_k * p⁰) mod M

Тщательный выбор параметров M, p важен для получения “хороших” свойств хэш-функции, т.е. низкой частоты коллизий.

Желательным свойством этого подхода является использование всех символов во входной строке. Вычисленное значение ключа затем может быть хэшировано в индекс массива обычным способом:

function hash(key, arraySize) {
  const base = 13;

  let hash = 0;
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex);
    hash += charCode * (base ** (key.length - charIndex - 1));
  }

  return hash % arraySize;
}

Метод hash() не так эффективен, как мог бы быть. Помимо преобразования символов, в цикле есть два умножения и сложение. Мы можем исключить одно умножение, используя метод Хорнера:

a₄ * x⁴ + a₃ * x³ + a₂ * x² + a₁ * x¹ + a₀ = (((a₄ * x + a₃) * x + a₂) * x + a₁) * x + a₀

Другими словами:

H_i = (P * H_i-1 + S_i) mod M

Функция hash() не может обрабатывать длинные строки, поскольку значение hashVal превышает размер int. Обратите внимание, что размер ключа всегда оказывается меньше размера массива. В методе Хорнера мы можем применять оператор по модулю (%) на каждом шаге вычисления. Это дает тот же результат, что и однократное применение оператора по модулю в конце, но позволяет избежать переполнения.

function hash(key, arraySize) {
  const base = 13;

  let hash = 0;
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex);
    hash = (hash * base + charCode) % arraySize;
  }

  return hash;
}

Полиномиальное хеширование обладает свойством плавного перехода: хэш-сумма может эффективно обновляться при добавлении или удалении символов в концах строки (при условии, что сохранен массив степеней p по модулю M достаточной длины). Популярный алгоритм сопоставления Рабина–Карпа основан на этом свойстве

Ссылки

• Где использовать полиномиальное хеширование строк
• Хеширование на uTexas
• Хэш-функция в Википедии
• Скользящий хэш в Википедии