algorithm - 确定 Pearson 哈希的完美哈希查找表

Question

我正在开发一种编程语言，在我的编程语言中，我将对象存储为哈希表。我使用的哈希函数是 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' 开始的连续范围。换句话说，我需要一种算法来为 perfect hash 创建一个查找表。 .这将使我拥有的对象占用的空间不超过其成员的数量。这将在编译时完成，因此速度不是一个大问题，但越快越好。暴力破解很容易，但我认为(希望)有更好的方法。

这是一个例子:给定类中的成员变量“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 的值，因为这可以让我避免检查，甚至可能避免存储成员名称，但我认为这不是可能，所以我必须添加额外的检查以查看它是否在表中。鉴于此，不初始化未使用的查找表中的值可能会节省时间(碰撞无关紧要，因为如果它碰撞并未通过检查，则它根本不在对象中，因此碰撞不需要解决；只需要处理错误)。

Answer 1

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

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

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