字符串哈希学习总结
算法·理论
哈希原理
+ 大质数
避免冲突
取模
unsigned 自动溢出
| 变量 | 最大储存 | 可行性 |
|---|---|---|
| unsigned byte | $255 $ | 数据量太小 |
| unsigned short | $65535 $ | 数据量太小 |
| unsigned int | $4 \times 10^9$ | 太大，数组开不下 |
| unsigned long long | $10^{19}$ | 太大，数组开不下 |
哈希后存储
存 true/false : 冲突后无法判断重复
存序号：冲突后无法判断重复
冲突概率
单哈希：$\prod\limits_{i=1}^{n} \dfrac{m-i+1}{m}$
双哈希：$1- \left ( 1-\prod\limits_{i=1}^{n} \dfrac{m-i+1}{m} \right ) \times \left ( 1-\prod\limits_{i=1}^{n} \dfrac{m-i+1}{m} \right )$
( $n$ 为 $\left | s \right |$ ，$m$ 为哈希表长度，是大质数 )
双哈希冲突概率大大降低。
哈希函数
$f(s)=\sum\limits_{i=0}^{n-1} s_{i} \times base^i \mod{m}$
( $s$ 为 $string$，$n$ 为 $\left | s \right |$，$m$ 为哈希表长度，是大质数 )