旋转哈希

✍ dations ◷ 2025-08-03 06:36:40 #散列函数

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

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

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

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

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

其中 a {\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

其中

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


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

相关

  • 多姆纳尔二世君士坦丁之子唐纳德(现代盖尔语: Dòmhnall mac Chòiseim),汉化称之为唐纳德二世(死于900),是9世纪晚期皮特克人的国王或苏格兰国王 (阿尔巴)。 他是君士坦丁一世 (Causantín
  • 氯化铅氯化铅,又称二氯化铅(PbCl2)是一种无机化合物,是一种在标准状况下是白色固体。它微溶于冷水,可溶于热水。它是白色粉末,密度为5.3-5.8克/厘米。摩氏硬度为1.5-2。溶解度为 0.99 g/
  • 冰斗冰斗(英语:cirque)是由山地冰川侵蚀而形成的,一种三面环山的凹地,如果冰已经消失,也被称为围谷、圈谷。冰斗形成于雪线附近的积雪凹地由于随季节和昼夜温度的变化,积雪融化和冻结反
  • 建筑工程建筑工程(简称:AE、BE,英语:Architectural engineering、Building engineering),是一个关于建筑物的施工和内部设施安装的工程学。其中一个分支为营建工程(英语:Construction engine
  • 窈窕淑女 (电影)《窈窕淑女》(英语:)是一部1964年出品,取材自爱尔兰剧作家萧伯纳舞台剧《卖花女》(Pygmalion),由奥黛丽·赫本、雷克斯·哈里逊主演,乔治·库克执导的电影。《窈窕淑女》是描述一名
  • 2011年碧特博格羽毛球黄金大奖赛2011年碧特博格羽毛球黄金大奖赛为第24届碧特博格羽毛球公开赛,是2011年世界羽联大奖赛的其中一站。本届赛事于2011年11月1日-11月6日在德国萨尔州的首府萨尔布吕肯举行,并获
  • 双桅纵帆船双桅纵帆船又称斯库那或斯库纳帆船(schooner),是一种帆船,所有桅杆均挂纵帆。桅杆多于两根时可称为多桅纵帆船或多桅斯库纳。双桅纵帆船的前桅较主桅小,前桅可张挂一面或多面方形
  • 罗纳德斯·赞克兹罗纳德斯·赞克兹(拉脱维亚语:Ronalds Zaķis,1987年7月8日-),拉脱维亚篮球运动员,现在效力于拉脱维亚球队里加篮球俱乐部。他也代表拉脱维亚国家男子篮球队参赛。
  • 高晓声高晓声(1928年7月6日-1999年7月6日),江苏武进人,中国小说家。童年时代在农村度过,其父是知识分子,因而能够接触文学。14岁丧母,家境清贫,中学阶段屡次因付不起学费而辍学。后来进入上
  • 倪伟倪伟(1908年-1997年5月24日),男,奉天(今辽宁)海城人,中华人民共和国政治人物,曾任哈尔滨科学技术大学党委书记,黑龙江省人大常委会副主任,第五届全国人大代表。