有关hash #1

省选第一轮丧病的考了一道树hash的裸题,但全场仅有3人ac(即本轮比赛的前三名),且拿分的人并不多,例如我就是此题炸零的人的其中一个。树hash这类的题我是做过的,不过还是遥远的去年在备战noi的时候写过,算法还是自己yy的。省选前也有耳闻杨弋的一篇论文里写到过树hash的相关算法,当时也是完全没有在意。关于这道树hash题的恶心之处及此种种,后面再说。除此之外,这轮的第二题我也用了hash,被常数卡T也是蛮惨。加上NOIP2014最后一题也是道hash题,决定写一篇文整理一下竞赛中各类hash的用法。

伪大整数hash

所谓伪大整数hash,即将不是特别大的数($$\leq10^{18}$$)映射到一个可以开的下的数组中($$\leq10^6$$),方法即为对要hash的数mod一个质数,将结果存到对应的位中。处理冲突的方法有很多,不提。c++选手可以使用map,使用价值为0。

关于为什么要取质数,主要是为了让产生冲突的hash位上的数之间尽量没有关联,具体可以看这里这里

字符串hash

这是一类比较实用的hash方法,很多hash方法也是基于这个方法衍生的。方法如下:

$$ h(S)=(\sum_{i=0}^{len(S)-1}S[i]*B^i)\mod P $$

其中B、P也应尽量为质数。

字符串hash的一个好处便是可以在$$O(n)-O(\log n)$$(或$$O(n\log n)-O(1)$$)的时间内判断两个字符串的子串是否相同。假设要提取字符串s的一个子串 S[i..j]的hash值,我们可以先预处理出字符串S的前缀hash值,即求

$$ sum[i]=h(S[0..i])=(\sum_{j=0}^{i}S[j]*B^j)\mod P $$

我们注意到

$$ sum[j]-sum[i-1]=(\sum_{k=i}^{j}S[k]*B^k)\mod P $$

将其乘上 $$ B^{-i} $$ 后即为子串 S[i..j] 的hash值。复杂度中的log即为求逆元的log。

这里还有一个小trick。我们在递推求sum的时候可以写成这样:$$sum[i]=sum[i-1]*B+S[i]$$,而不是根据定义得到的$$sum[i]=sum[i-1]+S[i]*B^i$$,随便推一下发现求子串hash值得时候变为了$$sum[j]-sum[i-1]*B^{j-i+1}$$,省去了求逆元的时间。

###To be continued.