博客

进制哈希，就是让长度为n的字符进行下列运算：

for(int i=1;i<=n;i++)

{


ans=(ans*k)+a[i];

}

当然这是初始版

如果溢出，那么计算机会自动舍弃高位的值，留下低进制位的数字

让我们现在考虑该如何选取k

如果是偶数，那么最终会因为溢出而导致高位运算无法参与

而如果是奇数，那么即使溢出，高位字符也会因为奇数不是2的整数倍，会留下1，从而在低位产生影响

所以

1.k为奇数

下面我们在看看k应该选取怎么样的奇数

为了自动取位，我们应该选择数据为unsigned型，如果不是这种类型，那么如果超出这种数据类型的范围之后，就会变成负值了

k一般选择2的n次方-1，一般取常见 31,313,3131,3131313 等等

对于系数选择，以及结果处理，只能尽可能减少碰撞几率，并不可以完全避免

如果发生碰撞，则需要改变一下k的值，或者改一下对结果进行取余的值，或者每次计算加上一个素数，使得结果和位数直接挂钩

ok就写到这里，哈希表还是比较玄学的

212370440130137957这个是一个较大的质数，我看他们经常用这个进行mod。不知道有啥用