哈希表其实就是建立和存储一种映射关系
离散化、桶排序就是一种简单数值哈希
常见的哈希方法：
除法哈希法 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]:更佳
