字符串哈希

原理

哈希： any -> int/long long，结果用于下标，实现随机访问。本质是离散化。 字符串哈希：string -> index

实现 | 哈希算法

本质是转换为进制为 $base$ 的进制数： $$ hash = (str)_{base} $$ 但由于下标类型大小有限，所以需要取模 $mod$ 。

Info

$base$ 选择：大于每位数字最大值，不含 $mod$ 质因子：27, 233, 19260817
$mod$ 选择：
- 一个 $10^9$ 质数做单哈希：1e9+7 ，但是任意 $\sqrt{10^9}$ 个串就容易哈希冲突
- 两个 $10^9$ 质数做双哈希：19260817 & 19660813
- 用 unsigned long long 自然溢出

朴素实现

如下

1
2


for (int i = 0; i < str.size(); i++)
	hash = (hash + str[i] * pow(base, i)) % mod;

时间复杂度由于 pow 为 $O(n^2)$ 。所以使用滚动优化/累积优化降低复杂度到 $O(n)$ 。

单哈希

1
2


for (char c : str)
	hash = (hash * base + c) % mod; // mod = 1e9 + 7

:star:自然溢出

1
2
3
4


static unsigned long long base = 131;
unsigned long long hash = 0;
for (char c : str)
	hash = hash * base + c;

双哈希

1
2
3
4
5
6
7
8


unsigned long long mod1 = 19260817;
unsigned long long mod2 = 19660813;
using Hash = unsigned long long;
auto hash1(const std::string& str) -> Hash;
auto hash2(const std::string& str) -> Hash;
auto compare_hash(const std::string& lhs, const std::string& rhs) -> bool {
	return hash1(lhs) == hash1(rhs) && hash2(lhs) == hash2(rhs);
}

另法 | 用 STL 自带 hash 的容器 / std::hash 说的就是 std::set/std::unordered_map 。