BKDRHash 方法
时间: 2023-10-12 19:14:58 浏览: 49
BKDRHash是一种简单的哈希函数,它使用位运算和乘法运算来生成哈希值。该哈希函数由于其计算速度快、实现简单等优点,在一些场景下被广泛使用。
具体实现如下:
```c++
unsigned int BKDRHash(const char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return hash;
}
```
其中,seed是一个质数,可以自行选择。在循环中,先将哈希值乘以seed,再加上当前字符的ASCII码值。最后,返回哈希值。
需要注意的是,BKDRHash可能存在哈希冲突,因此在使用时需要进行适当的处理。
相关问题
用c++和BKDRHash方法解决下述问题:描述 Akko正在Luna Nova Magic Academy学习魔法。据说魔法世界中有10^5种不同的诅咒。阿卡很难记住所有这些。幸运的是,梅里迪斯教授说她可以帮助阿卡制作一本诅咒词典。当Akko听到诅咒时,字典会告诉她诅咒的效果。此外,当Akko想做某事时,字典会为她找到诅咒。如果没有这样的诅咒,字典将是沉默的。你能写一个程序来重现诅咒词典吗?输入 每个测试用例将包含不超过 10^5 个诅咒。每个诅咒都会像“[名称]效应”。诅咒的名称和效果将只包含小写字母。“]”和它后面的字符串之间只有一个空格。名称长度不超过20,效果长度不超过80。字典的末尾是一行“END”。在所有诅咒之后,将有一个整数 N (1<=N<1000),后跟 N 个查询。每个查询都将是一个“[诅咒名称]”或“诅咒效果”。每个输入文件中只有一个测试用例。输出 对于每个测试用例,您必须按其名称输出诅咒的效果或按其效果输出诅咒的名称。如果没有满足条件的诅咒,请打印“沉默”。提示 哈希字符串 gets() 在 C++14 中被弃用,改用 getline。对于 char arr[],请使用 cin.getline(arr,sizeof(arr));对于字符串 arr,请使用 getline(cin, arr);BKDRHash方法:unsigned int BKDRHash(char* str) { unsigned int seed = 31, key = 0; // 31 131 1313 13131 131313 etc.. while(*str) key = key * seed + (*str++); return key & 0x7fffffff; // return a 31-bit value }
好的,根据您的要求,我会使用 C++ 和 BKDRHash 方法来实现该程序。以下是代码实现:
```c++
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unsigned int BKDRHash(char* str) {
unsigned int seed = 31, key = 0;
while (*str)
key = key * seed + (*str++);
return key & 0x7fffffff;
}
int main() {
unordered_map<unsigned int, string> dict;
string curse;
getline(cin, curse);
while (curse != "END") {
string name = curse.substr(1, curse.find("]") - 1);
string effect = curse.substr(curse.find("]") + 2);
dict[BKDRHash(name.c_str())] = effect;
getline(cin, curse);
}
int n;
cin >> n;
getchar(); // 读取上一个输入流中的换行符
while (n--) {
getline(cin, curse);
if (curse[0] == '[') {
unsigned int key = BKDRHash(curse.substr(1, curse.size() - 2).c_str());
if (dict.find(key) != dict.end())
cout << dict[key] << endl;
else
cout << "沉默" << endl;
} else {
bool found = false;
for (auto& p : dict) {
if (p.second == curse) {
cout << "[" << p.first << "] " << curse << endl;
found = true;
}
}
if (!found)
cout << "沉默" << endl;
}
}
return 0;
}
```
该程序使用了 `unordered_map` 来实现哈希表,使用 BKDRHash 方法作为哈希函数。在读入每个诅咒时,将诅咒名称的哈希值作为键,诅咒效果作为值,存入哈希表中。在读入每个查询时,如果查询是以 `[` 开头的字符串,则将查询名称的哈希值作为键查找哈希表,输出对应的诅咒效果;如果查询是以其他字符串开头的字符串,则遍历哈希表查找对应的诅咒名称,输出对应的诅咒名称和诅咒效果。如果没有对应的诅咒,输出“沉默”。
BKDRHash怎么使用
BKHash是一种简单的哈希函数,可以将任意长度的字符串映射为一个固定长度的哈希值。它的实现很简单,可以用如下的伪代码表示:
```
const int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int BKDRHash(char *str) {
unsigned int hash = 0;
while (*str) {
hash = hash * seed + (*str++);
}
return hash;
}
```
其中seed是一个任意的素数,可以根据实际应用场景进行调整。使用时,只需要将需要哈希的字符串传入该函数即可,函数会返回一个无符号整数作为哈希值。
需要注意的是,BKDRHash虽然简单易用,但是其哈希值分布不够均匀,可能会导致哈希冲突较多。在实际应用中,需要根据具体情况选择合适的哈希函数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)