旋转哈希

旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输入的内容在一个窗口中进行移动哈希。

少数哈希函数允许快速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被快速计算出来，旧的值从窗口中移除，新的值添加到窗口中 — 类似于移动平均函数的计算方式，比其他低通滤波器更快。

主要应用之一是Rabin–Karp字符串搜索算法，该算法使用下面描述的滚动哈希。另一个流行的应用是rsync程序，它使用基于Mark Adler的adler-32的校验和作为滚动哈希。低带宽网络文件系统（LBFS）使用Rabin指纹作为其滚动哈希。

滚动哈希值最多只能是成对独立（英语：pairwise independent）的或强通用（英语：universal hashing）的。例如，它们不能是三向独立（英语：k-independent hashing）的。

通常使用仅包含乘法和加法的滚动哈希函数来解释Rabin–Karp字符串搜索算法：

其中${\displaystyle a}$ , data length , output: cut point ← 2KB //split minimum chunk size is 2KB ← 64KB //split maximum chunk size is 64KB ← ← ← // buffer size is less than minimum chunk size if ≤ then return n; if ≥ then ←     while < do ← ( << 1 ) + ] if !( & ) then return     return

其中

算法从数组下标为 ${\displaystyle MinSize}$ 开始循环，省去了处理长度不足最小分块所浪费的时间。计算当前字节下对应的指纹信息，当发现指纹信息等于提前预设好的 ${\displaystyle Mask}$ 时，则进行分段处理。如果计算到最大的 ${\displaystyle MaxSize}$ 时仍然没有匹配到 ${\displaystyle Mask}$ 时，此时强行进行分块。

所有滚动哈希函数在字符数上都是线性的，但其复杂度与窗口长度的关系（${\displaystyle k}$）不等。Rabin–Karp滚动哈希需要两个${\displaystyle k}$位数字的乘法，整数乘法是在${\displaystyle O(k\log <!--\; \; -->k{2}^{O({\log }^{\ast <!--\; \ast \; -->}<!--\; \; -->k)})}$。通过循环多项式对ngram进行哈希处理，可以在线性时间内完成。