哈希表及其应用
哈希表是一种常见的数据结构，它利用哈希函数将一个键映射到一个较小的值，从而实现快速的查找。哈希表在很多实际问题中都有着重要的应用，例如在数据库、缓存、编译器等领域中。
哈希表的一个重要的应用是字符串查找。在本文中，我们将介绍在 C++ 中如何使用哈希表实现字符串查找。
字符串查找问题
字符串查找问题就是在一个大的字符串中查找一个子字符串的位置。这个问题在实际生活中经常用到，例如在文本编辑器中查找关键字等。
暴力法
最简单的解决方案是使用暴力法。对于大字符串中的每一个位置都判断是否与子字符串相等，时间复杂度是 O(nm)，其中 n 是大字符串的长度，m 是子字符串的长度。
int search(string s, string p) {
int n = s.length(), m = p.length();
for (int i = 0; i <= n - m; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (s[i + j] != p[j]) {
flag = false;
break;
}
}
if (flag) return i;
}
return -1;
}
由于暴力法时间复杂度较高，在字符串较大时效率低下，因此我们需要一种更加高效的算法。
哈希表法
哈希表法是一种常见的字符串查找算法，它可以在时间复杂度 O(n) 的时间内完成查找操作。哈希表将每一个字符串映射到一个对应的哈希值上，并将这些哈希值保存在一个数组或哈希表中。通过比较哈希值，可以快速判断字符串是否相等。
哈希函数的设计
哈希函数是一个非常关键的部分。一个好的哈希函数可以将字符串映射到不同的哈希值上，从而避免哈希冲突。在实际应用中，我们可以使用多种方法设计哈希函数。
简单哈希函数
最简单的哈希函数是将字符串中每一个字符的 ASCII 码相加。这种方法的复杂度是 O(m)，其中 m 是字符串的长度。
int hash(string s) {
int res = 0;
for (char c : s) {
res += c;
}
return res;
}
这种方法的问题在于容易产生哈希冲突。例如，字符串 "abc" 和 "cba" 的哈希值都是 294，它们会被认为是相等的。
优化哈希函数
为了避免哈希冲突，我们需要优化哈希函数。一种常见的优化方法是将每一个字符和其位置的乘积相加作为哈希值。
int hash(string s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
res += s[i] * (i + 1);
}
return res;
}
这种方法的时间复杂度是 O(m)，其中 m 是字符串的长度。它可以有效地避免哈希冲突，在实际应用中效果较好。
使用哈希表实现字符串查找
使用哈希表实现字符串查找的步骤如下：
将子字符串的哈希值计算出来。
对于大字符串中长度为 m 的每一个子串，计算其哈希值，并与子字符串的哈希值进行比较。
如果相等，则判断两个字符串是否相等。
如果相等，则返回匹配的位置。
代码实现如下：
int hash(string s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
res += s[i] * (i + 1);
}
return res;
}
int search(string s, string p) {
int np = p.length();
int hp = hash(p);
for (int i = 0; i <= s.length() - np; i++) {
string ts = s.substr(i, np);
int hs = hash(ts);
if (hs == hp && ts == p) {
return i;
}
}
return -1;
}
该算法的时间复杂度是 O(nm)，其中 n 是大字符串的长度，m 是子字符串的长度。但是实际的复杂度要低于暴力法，因为一般来说哈希冲突比较少，因此哈希表法的效率要比暴力法高。
总结
在本文中，我们介绍了哈希表及其应用。特别地，我们介绍了在 C++ 中如何使用哈希表实现字符串查找。相对于暴力法，哈希表法可以在更短的时间内完成字符串查找，是一种常见的高效算法。