yxy版c++教程 Hash 浅谈哈希算法

yxy版c++教程 Hash 浅谈哈希算法 哈希表

哈希表其实就是建立和存储一种映射关系

离散化、桶排序就是一种简单数值哈希

常见的哈希方法：

除法哈希法  hash(key) = keymod M（M为素数）

乘法哈希法  hash(key) = floor( M/W * ( a * key mod W) )

                   通常设置M为2的幂次方

                   W为计算机字长大小（也为2的幂次方）

                   a为一个非常接近于W的数

                   若a=W*(√5-1)/2，则为斐波拉契哈希法

相同的输入hash之后一定相同hash值相同的值一定是同一个输入吗？

—— “哈希冲突”。

哈希冲突

 是哈希就会冲突，但是合理的选择哈希函数可以让冲突的概率降低真的冲突了怎么办？

冲突解决办法：

拉链法  链表实现，每个位置一个链表，存储冲突的元素

开放地址法  如果冲突，就按一定的规则放到其它位置

字符串哈希

OI里面常常涉及到的时候字符串哈希，字符串哈希的算法也有很多

最著名的就是BKDR Hash具体做法：

        •将字符串变成数值,并且最后变成的数值是一个P进制的数（一般取131或者13331）一般来说P最好为素数.

        •由于字符串相同，就转化为区间的值相同，所以求一个前缀和

构造方法:

假如给你一个数字1166，形式上你只知道它只是1和6的组合

但你知道它代表的实际大小1*103+1*102+6*101+6*100

同理，给你一个字符串，要把它转换为数字

就可以先把每一个字符都先对应一个数字

然后把它们按照顺序乘以进制的幂进行相加

算法过程

处理过程

        •把字符串看成P进制数

        •预处理字符串所有的前缀hash值hash[i] = (hash[i-1] * P + str[i])mod Q

        •计算区间hash值hash[l, r] = hash[r] -hash[l-1] * p[r -l + 1]这里P一般取131或者13331

        •Q一般取1e9+7或1e9+9等大素数，这样冲突的机率极小(姑且视作不冲突)

        •如果Q取，可以直接用unsigned long long自然溢出反复求值，提前预处理p[n]:更佳