旋转哈希

✍ dations ◷ 2025-06-30 19:23:43 #散列函数

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

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

主要应用之一是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进行哈希处理,可以在线性时间内完成。

相关

  • 吉尔曼艾尔佛列·古曼·吉尔曼(英语:Alfred Goodman Gilman,1941年7月1日-2015年12月23日),美国药学和生物化学家。因发现G蛋白与马丁·罗德贝尔一起分享1994年诺贝尔生理学或医学奖。19
  • 沃德·坎宁安沃德·坎宁安(英语:Ward Cunningham,1949年5月26日-),是计算机程序员,也是Wiki概念的发明者。他也是设计模式和敏捷软件方法的先驱之一。他从普度大学获得(电子工程和计算机科学的)交
  • 行宫伯爵行宫伯爵(拉丁语:comes palatinus),另译普法尔茨伯爵、王权伯爵,是一种起源于罗马帝国后期、在中世纪以后主要由神圣罗马帝国等国家使用的贵族头衔。行宫伯爵头衔中的palatinus一
  • 醇类似物醇类似物是泛指任何有类似于醇类或羟基结构的有机化合物,例如硫醇、酚等。大部分的醇类似物都有类似的性质,例如易挥发和刺激性等性质。酚是一种具有羟基的芳香烃,不属于醇类,但
  • 阿列克谢·切皮奇卡阿列克谢·切皮奇卡(捷克语:Alexej Čepička,1910年8月18日-1990年9月30日),捷克斯洛伐克共产党领导人之一,捷克斯洛伐克国防部部长。
  • 图尔维尔安内·德·图尔维尔(法语:Anne Hilarion de Tourville,1642年11月24日-1701年5月23日),法国贵族、海军上将与法国英雄。1642年图尔维尔生于巴黎,因是贵族之子及天主教徒,15岁(1657年)
  • 暗棕壤暗棕壤是寒温带湿润地区针阔混交林下发育的淋溶型棕化土壤,又名山地灰化土、棕色灰化土、灰化棕色森林土、灰棕壤、山地棕壤、灰棕色森林土、暗棕色森林土等。1978年中国土壤
  • 独乐乡独乐乡,是中华人民共和国河北省保定市易县下辖的一个乡镇级行政单位。独乐乡下辖以下地区:中独乐村、南独乐村、北独乐村、裴庄村、康家庄村和寨子村。
  • 陈永锵陈永锵(1948年-),广东人,中国画家。祖籍广东省南海区西樵,1948年生于广州市。14岁时拜岭南画派梁占峰为师学习花鸟画,1973年创作《鱼跃图》入选全国美展,被评为优秀作品,自此以后,作品
  • 幻影猫幻影猫(英语:Shadowcat),本名凯瑟琳·安妮·凯蒂·普莱德(Katherine Anne "Kitty" Pryde),是出现在惊奇漫画出版物中的超级英雄虚构人物。首次出现于《神奇的X战警》(Uncanny X-Men)