多项式滚动哈希

哈希函数

哈希函数用于将任意长度的键元素集映射到固定长度的指纹元素集。

哈希的基本应用是通过比较它们的指纹来高效测试键的相等性。

当两个不同的键具有相同的指纹时，就会发生冲突。在大多数哈希应用中，冲突处理的方式至关重要。哈希特别适用于构建高效的实用算法。

滚动哈希

滚动哈希（也称为递归哈希或滚动校验和）是一种哈希函数，其中输入在窗口中移动时进行哈希计算。

一些哈希函数允许非常快速地计算滚动哈希——仅根据以下数据即可迅速计算新的哈希值：

旧的哈希值，
从窗口中移除的旧值，
和添加到窗口中的新值。

多项式字符串哈希

理想的字符串哈希函数显然应该依赖于键中存在的符号的多重集以及符号的顺序。这类哈希函数最常见的一族将字符串的符号视为多项式的系数，其中有一个整数变量p，并计算其在整数常数M模下的值：

拉宾-卡普字符串搜索算法通常使用一个非常简单的滚动哈希函数来解释，该函数只使用乘法和加法——多项式滚动哈希：

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

其中p是一个常数，(s₁, ... , s_k)是输入字符。

例如，我们可以通过将数字代码乘以常数的幂，将短字符串转换为键编号。三个字母的单词ace可以通过计算得到一个数字：

key = 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()无法处理长字符串，因为哈希值超出了整数的大小。请注意，键最终总是小于数组大小。在霍纳方法中，我们可以在计算的每一步应用模运算符（%）。这给出了与在最后一次性应用模运算符相同的结果，但避免了溢出。

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的数组）。流行的拉宾-卡普模式匹配算法就是基于这一属性。

多项式滚动哈希

哈希函数

滚动哈希

多项式字符串哈希

参考文献