#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;
class Item {
public:
Item(const string & v): value(v), next(0) { }
string value;
Item * next;
};
int hash_function(const string & s)
{
unsigned int hashval = 0;
int i = s.length();
while (i > 0)
{
hashval += s[--i];
}
return hashval%101;
}
main()
{
string name;
int index;
Item * p;
vector<Item *> bucket(101);
for (index = 0; index < 101; index++)
bucket[index] = 0;
while (cin >> name) {
p = new Item(name);
index = hash_function(name);
// push front
if (bucket[index] != 0)
p->next = bucket[index];
bucket[index] = p;
}
for (index = 0; index < 101; index++)
if (bucket[index] != 0) {
cout << setw(3) << index << ": ";
p = bucket[index];
while (p != 0) {
cout << p->value << " ";
p = p->next;
}
cout << endl;
}
Item * temp;
for (index = 0; index < 101; index++) {
p = bucket[index];
while (p != 0) {
temp = p;
p = p->next;
delete temp;
}
}
}
其中包含两个非常简单的哈希函数。我正在尝试处理未注释掉的一个,因为经过测试似乎是两者中较好的一个。我希望输入的一组名称在其自己的存储桶中均匀分布,到目前为止,这似乎是可行的,但以相同字母开头的名称除外。例如,艾米和爱丽丝将出现在同一存储桶中,依此类推。
这是一个示例输入/输出:
Alice
Amy
Barry
Carrie
David
Garret
Edward
Henry
Ingrid
Fred
65: Amy Alice
66: Barry
67: Carrie
68: David
69: Edward
70: Fred
71: Garret
72: Henry
73: Ingrid
我可以在算法中添加些什么,以允许将Amy和Alice放在自己的存储桶中?
最佳答案
不要盲目地添加每个字母,而是给每个字母赋予一些权重,以便cpp
,pcp
,ppc
都可以产生不同的哈希值。
这是一点改进的版本:
int hash_function(const string & s)
{
double hashval = 0;
int i = s.length();
double weight = 1.0;
while (i > 0)
{
hashval += weight * s[--i];
weight *= 1.5;
}
return (int) hashval;
}
假设字符串
s
不能太长,否则会溢出!