algorithm - 为硬编码哈希表确定固定哈希函数的好方法是什么？

Question

我经常发现自己需要一个哈希表，其值在编译时已知并且永远不会改变。

我想知道是否有一种标准的方法来生成一个量身定制的算法，该算法仅用于特定的哈希表，这样它就不需要在运行时构建，并确保没有冲突。

这种最糟糕的算法就是执行一系列 if 语句，但这有点破坏 O(N)ness。

我想知道是否有一些现有算法可以将固定数量的唯一字符串映射到从 0 到唯一字符串数量的索引。

例如；我可能有一个哈希表

{
    "one": "1",
    "two": "2", 
    "three": "3"
}

创建这样一个硬编码表的一种天真的尝试是创建一个具有条目对内部表的函数，并提出一些任意的区分，例如下面的一个。

#include <stdio.h>
#include <string.h>
#include <math.h>

static const char *my_hash(const char *input)
{   
    const struct {
        const char *key;
        const char *value;
    } h_table[] = {
        {"three", "3"},
        {"one", "1"},
        {"two", "2"}
    };

    int hash;
    int len = strlen(input);

    if (len != 3 && len != 5) {
        return (char *)0;
    }        

    hash = (int)ceil((((input[1] - 102) / 4) - 1) / 2.0);    

    return h_table[hash].value;
}

int main(int argc, char **argv)
{
    puts(my_hash("one"));
    puts(my_hash("two"));
    puts(my_hash("three"));

    return 0;
}

是否有生成此类算法的已知算法？

总结:是否有一种已知的算法可以将 N 个不同的字符串映射到从 0 到 N-1 的 N 个不同的整数？

我觉得这样的东西已经存在了。

Answer 1

这些被称为 minimal perfect hash functions ，并且确实有已知的算法可以找到它们。我个人并不了解这些算法，但没关系。现有的图书馆可以为您完成。

CMPH非常适合为大量键找到最小的完美哈希函数。

gperf专注于少量键的哈希评估速度，其中完美哈希函数不需要最小(因此表中可能有一些空白空间)。