问题标签 [perfect-hash]

考虑以下使用普通回溯生成的 {0,1,2,3,4,5,6,*,*,*} 排列列表：

是否有一个 O(1) 函数，对于任何排列，它会返回排列的索引？

我最近阅读了这篇文章Throw away the keys: Easy, Minimal Perfect Hashing关于为一组已知的键生成一个最小完美哈希表。

该文章似乎假设您需要一个中间表。如果我们假设键集很小（即<64），是否还有其他更简单的方法来生成这样的函数。

就我而言，我想将一组线程 ID:s 映射到数组中的唯一数据块。线程在生成哈希函数之前启动，并在程序运行期间保持不变。线程的确切数量会有所不同，但在程序运行时保持不变：

我需要的

我需要一种产生双射输出的算法。我有一个 31 位输入，需要一个伪随机 31 位输出。

我所考虑的

CRC 在其位宽内是双射的。

我在谷歌上看过，可以找到多项式，但找不到表格或算法。

谁能指出我正确的方向？

我需要一个使用多项式 0x737e312b 的 CRC-31 算法，或者任何可以满足我需求的双射函数。

笔记

我找到了以下代码，但不幸的是我没有编译和运行它的工具。

gperf 信息页面声称，如果您指定，-l则

输入文件中的关键字可能包含 NUL 字节，以字符串语法写成 \000 或 \x00，而 gperf 生成的代码会将 NUL 视为任何其他字节

但是，当我通过以下方式运行此输入文件时gperf -L C++ -l：

我得到：

看起来它将\000and\x00视为文字值而不是空字节。

如何在我的 gperf 字符串中正确使用指定空字节？

我正在寻找一种将一系列“范围”“投影”到一系列值中的方法。应用程序将是具有不均匀 bin 的直方图或创建查找表。

一个例子：

0 到 14 => 0

15 到 234 => 1

235 => 2

236 到 255 => 3

右边的“结果”值（0、1、2、3）的实际顺序并不重要，只要它们在 0 和 3 之间，这样我就可以使用一个小的查找表。如果我可以在浮点值（左侧）上进行这项工作，那就更好了。

我知道我可以在这里使用一个 8 位查找表并重复值，但我想找到一种“完美哈希”的方法：通过一系列系统操作（尽可能小，没有分支）从左边的值，以获得最小的结果空间。

我似乎无法为这种算法找到正确的一系列神奇的 Google 咒语。

如果需要，这个“哈希”或“投影”函数的计算持续时间可以是天。

我目前正在写关于图中聚类的硕士论文。我的教授说他希望将图表表示为哈希表。因为它比邻接矩阵需要更少的空间，并且在检查两个顶点之间是否存在边时比邻接列表更快。无论如何，我在理解如何使用（完美）散列函数构建图形时遇到很多问题。我知道里面应该有两张桌子。第一个包含每个节点，第二个包含所有相邻的顶点。但是我如何找到一个正确的哈希函数呢？构建图表后，我必须为每条边分配权重。建一个新图好还是保留旧图好？如何正确地将权重分配给每个边缘以及如何保存它？最后一个问题：我可以多快对一个顶点进行度数查询？奥（1）？

很抱歉所有这些问题，但我读了很多论文，我仍然感到困惑。预先感谢您的任何帮助！！！

丽莎

我在 golang 的源代码中找到了这个函数，想知道它是否真的是一个完美的哈希函数。这是测试的正确方法吗？

这是问题所在：

X 是一个正整数（包括 0）集合，它具有我预先知道的 n 个不同元素。它们都小于m。我希望有一个尽可能简单的无 occ 哈希函数将它们映射到 0-n-1。

例如：

X = [31,223,121,100,123,71]，所以 n = 6，m = 223。

我想找到一个哈希函数将它们映射到 [0, 1, 2, 3, 4, 5]。

如果映射到 0-n-1 太难，那么如何将 X 映射到小范围也是一个问题。

找到这样的函数并不太难，但要简单易生成却很难。

最好保留 X 的顺序。

有什么线索吗？