免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1567 | 回复: 0

[Linux] zlib源码hash函数疑问 [复制链接]

论坛徽章:
0
发表于 2016-12-02 08:07 |显示全部楼层
            #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
这个H_SHIFT怎么获得,以及这个哈希函数的原理以下解释

*    即H_SHIFT 为哈希码长度除以3再向上取整,原因如下:

设strtsart  = s, 此时生成的哈希码只能与 *    window[s], window[s + 1], window[s + 2]有关,这一点是必须的,因此,必须通过左移将之前 *    window[s - i],window[s - i + 1],......,window[s - 1](i >= MIN_MATCH - 1) *    产生的哈希码去掉, *    不妨设每次左移r位; *    window[s - i]左移一次,window[s - i + 1]左移一次,...,window[s]左移一次, *    共有i + 1次机会,从而(i + 1) * r >= HASH_BITS, 且 i >= MIN_MATCH - 1, *    于是 r = (HASH_BITS + i) / (i + 1) <= (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH  */
1、这个i为什么要i >= MIN_MATCH - 1,
2、直接用h=新值不就可以把之前的值去掉了么?


还有为什么   for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);


这个为什么是j<2,而不是j<=2;


麻烦大侠帮忙解答

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP