只要相信，就能无所不能。——《HELLO WORLD》

哈希

哈希表（），也叫散列表，是根据关键码值（）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

本文只讲字符串哈希，常用在各种字符串题目的~~部分分~~中。

字符串哈希可以在的时间内完成判断两个字符串的字串是否相同，也就是所谓的。

BKDR HASH

由一个字符串的子串得到其哈希值，为了减少碰撞，应该使字符串的子串中每个字符都参与计算，使其符合雪崩效应（是一种不稳定的平衡状态也是加密算法的一种特征，指明文或密钥的少量变化引起密文的很大变化）。

朴素的想法是让子串里的所以字符的码加起来，但是这样很容易发生碰撞（就是有的子串哈希值会相同），所以我们有了以下公式：

$Hash(s)=(\sum^{len(s)}_{i = 1}s[i]⋅b^{len - i}))\mod p$

其中和是常量，由于通常是一个字符，所以可以直接代入码，如果是小字母就代入 ‘ ‘ ，数字就代入 ‘ ‘ 。

来举个例子，如果令 “ “ ，那么就等于，即：

$Hash(s)=15=(73\times6^0+79\times6^1+73\times6^2+75\times6^3+65\times6^4+5\times6^5+7\times6^6+23\times6^7)\%100$

本质上就是将看成一个进制的数，然后就可以得到这个串的哈希值。

但是平时我们通常需要一个字符串的子串，可以由一坨式子来推算出这个子串的哈希值：

$Hash(s[l,r]) = (\sum^r_{i = 1}s[i]·b^{r-i})\mod p$

考虑使用前缀和来操作：

$Hash(s[1,r])=(\sum^r_{i=1}s[i]·b^{r-i})\bmod p$ $Hash(s[1,l-1])=(\sum^{l-1}_{i=1}s[i]·b^{l-i-1})\bmod p$ $\therefore Hash(s[l,r])\equiv Hash(s[1,r]) - Hash(s[1,l-1])·b^{r-l+1}\pmod p$

即：

$Hash(s[l,r])\leftarrow(Hash(s[1,r])-Hash(s[1,l-1])·b^{r-l+1}\bmod p+p) \pmod p$

于是我们在对于原串记录前缀和，就可以完成预处理完成截取子串值的优秀复杂度。

由于の自带的模数和极小的常数，所以一般的情况下，的运算通常会采用，这种写法通常被称作自然溢出。

代码如下：

ull hash (char s[]) 
{
	int len = strlen (s);
	ull res = 0;
	for (int i = 1; i <= len; i ++) // 遍历字符串 
		res = (res * base + (ull)s[i] % mod); 
	return res;
}