c++ - 具有已知键数的字符串的完美哈希

Question

当要散列的元素数量已知时，是否有可能拥有从字符串到整数的完美散列函数？我所说的完美哈希函数是指没有碰撞的机会。

基本上我是从文件中读取多个表的签名(例如 id、名称、地址)。不同的表可能具有共同的属性(例如名称)，但位于不同 的位置(即列)。我希望能够问类似这样的问题:table1["name"] 是什么？或 table2["name"].

更新:我宁愿自己学习，也不愿使用已有的东西。

Answer 1

参见 GNU gperf .

GNU gperf 是一个完美的散列函数生成器。对于给定的字符串列表，它以 C 或 C++ 代码的形式生成哈希函数和哈希表，用于根据输入字符串查找值。哈希函数是完美的，这意味着哈希表没有冲突，哈希表查找只需要单个字符串比较。