Chinaunix

标题: zlib源码hash函数疑问 [打印本页]

作者: ljx8268771 时间: 2016-12-02 08:07
标题: zlib源码hash函数疑问
#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;

麻烦大侠帮忙解答

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)