3

我正在开发一种编程语言，并且在我的编程语言中，我将对象存储为哈希表。我使用的散列函数是Pearson Hashing，它依赖于 256 位查找表。这是功能：

char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

我的问题是，给定一个少于 256 个成员名称的固定组，如何确定一个lookup表以pearson()返回从'\0'. 换句话说，我需要一种算法来为完美的哈希创建查找表。这将允许我拥有不超过其成员数量的对象。这将在编译时完成，因此速度不是一个大问题，但更快会更好。蛮力这样做很容易，但我认为（希望）有更好的方法。

这是一个例子：给定一个类中的成员变量“foo”、“bar”和“baz”，我想确定一个lookup这样的：

pearson('foo',lookup) == (char) 0
pearson('bar',lookup) == (char) 1
pearson('baz',lookup) == (char) 2

请注意，顺序无关紧要，因此以下结果也是可以接受的：

pearson('foo',lookup) == (char) 2
pearson('bar',lookup) == (char) 0
pearson('baz',lookup) == (char) 1

在理想的世界中，所有不在表中的名称都会返回一个大于 2 的值，因为这可以让我避免检查，甚至可能避免存储成员名称，但我认为这是不可能的，所以我将不得不添加一个额外的检查以查看它是否在表中。鉴于此，不初始化查找表中未使用的值可能会节省时间（碰撞无关紧要，因为如果它发生碰撞并且检查失败，它根本不在对象中，所以碰撞不需要解决；只需要处理错误）。

4

2 回答 2

1

如果成员名称的数量太多，我强烈怀疑您是否能够通过蛮力找到解决方案。由于生日悖论，不存在冲突的概率（即两个哈希值相同）对于 64 个成员名称约为 1:5000，对于 96 个成员名称约为 1:850,000,000。从您的哈希函数的结构（它源自旨在很好地“混合”事物的密码结构），我不希望存在解决您问题的算法（但我肯定会对这样的野兽感兴趣）。

您的理想世界是一种幻觉（如您所料）：您可以将 256 个字符附加到 'foo'，其中没有两个可以给出具有相同哈希值的新单词。由于散列值只有 256 种可能性，因此您可以将一个字符附加到“foo”，使其散列与“foo”、“bar”或“baz”的任何散列相同。

为什么不使用像CMPH这样的现有库？

于 2009-09-09T09:51:28.110 回答
0

如果我理解正确，您需要的是一个可以进行二进制搜索的排序且无重复元素的数组。如果键在数组中，则索引是“哈希”。否则，您将获得数组的大小。与查找表 O(1) 相比，它是 O(nlogn)，但对于少量元素来说已经足够了——在你的例子中是 256 个。

于 2009-09-09T09:26:56.747 回答