zlib源码里面hash疑问

由本社区发起的开源项目
回复
ljx8268771
帖子: 1
注册时间: 2016-12-02 8:07
系统: windows
送出感谢: 0
接收感谢: 0

zlib源码里面hash疑问

#1

帖子 ljx8268771 » 2016-12-02 8:09

#define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
这个H_SHIFT怎么获得,以及这个哈希函数的原理以下解释

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

设strtsart = s, 此时生成的哈希码只能与 * window, window[s + 1], window[s + 2]有关,这一点是必须的,因此,必须通过左移将之前 * window,window[s - i + 1],......,window(i >= MIN_MATCH - 1) * 产生的哈希码去掉, * 不妨设每次左移r位; * window左移一次,window[s - i + 1]左移一次,...,window左移一次, * 共有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;


麻烦大侠帮忙解答
回复

回到 “开源小工具”