#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放在自己的存储桶中?

最佳答案

不要盲目地添加每个字母,而是给每个字母赋予一些权重,以便cpppcpppc都可以产生不同的哈希值。

这是一点改进的版本:

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不能太长,否则会溢出!

08-16 11:59