c++中各种哈希算法的模板
时间: 2023-05-19 07:04:28 浏览: 189
C语言中常用的哈希算法模板有:MD5、SHA-1、SHA-256、SHA-512、CRC32等。这些算法都可以用于数据的加密、校验等方面。如果您需要更详细的信息,可以查阅相关的资料或者参考开源的哈希算法库。
相关问题
使用c++实现哈希查找算法
在C++中实现哈希查找算法通常涉及到以下几个步骤:
1. **定义哈希表(Hash Table)**:这是哈希查找的核心数据结构。C++没有内置的哈希表,但你可以自定义或使用第三方库如`unordered_map`,它是标准模板库STL的一部分,提供了高效的键值对存储。
```cpp
#include <unordered_map>
using namespace std;
class HashTable {
public:
// 使用哈希函数将键转换为数组索引
size_t hash_func(const string& key) const {
return std::hash<string>{}(key);
}
// 其他方法如插入、查找和删除
private:
unordered_map<string, value_type> data;
};
```
2. **哈希函数**:你需要一个函数来将输入的数据均匀地映射到哈希表中的槽位。理想的哈希函数应尽可能减少冲突,即多个键被映射到同一个槽位的情况。
3. **处理冲突**:当两个或更多的键哈希到同一个位置时,你需要解决冲突。最常用的解决策略有开放地址法(线性探测、二次探测等)或链地址法(使用关联列表或红黑树等数据结构)。
4. **查找操作**:对于`find`这样的查询操作,首先计算键的哈希值,然后使用该哈希值访问对应的桶。如果桶里存在元素,则进一步比较键是否匹配。
5. **插入和删除**:同样,先哈希后定位,根据哈希结果进行插入或删除操作。如果用链地址法,只需遍历链表即可找到目标项。
```cpp
// 示例查找操作
bool search(const string& key) {
size_t index = hash_func(key);
if (data.count(index)) {
if (data[index].first == key) { // 匹配成功
return true;
}
}
return false; // 如果链表为空或者未找到,返回false
}
```
用c++写一个字符串哈希的模板代码
以下是一个基本的字符串哈希模板代码(使用了多项式Hash算法):
```c
#include <stdio.h>
#include <string.h>
#define MAXN 1000010 // 最大字符串长度
#define P 31 // 素数P,用于哈希计算
#define MOD 1000000009 // 哈希计算结果取模值
typedef long long ll;
char s[MAXN];
ll h[MAXN], p[MAXN];
// 初始化哈希相关数组
void init()
{
p[0] = 1;
for (int i = 1; i < MAXN; i++)
{
p[i] = p[i - 1] * P % MOD;
}
}
// 计算字符串s的哈希值
void hash()
{
int n = strlen(s);
h[0] = s[0] - 'a' + 1; // 初始化第一个字符的哈希值
// 依次计算每个字符的哈希值
for (int i = 1; i < n; i++)
{
h[i] = (h[i - 1] * P + s[i] - 'a' + 1) % MOD;
}
}
// 计算子串[l, r]的哈希值
ll get_hash(int l, int r)
{
if (l == 0)
{
return h[r];
}
return (h[r] - h[l - 1] * p[r - l + 1] % MOD + MOD) % MOD;
}
int main()
{
init();
scanf("%s", s);
hash();
int n = strlen(s);
// 输出每个后缀的哈希值
for (int i = 0; i < n; i++)
{
printf("%lld ", get_hash(i, n - 1));
}
return 0;
}
```
这个模板代码可以用于计算一个字符串中每个后缀的哈希值。在使用时,可以根据需要修改哈希算法和哈希计算结果的取模值。