c - 是否可以在没有单独查找表的情况下为一组小的(<64)键创建最小完美哈希函数？

Question

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

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

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

unsigned int thread_ids*;
unsigned int thread_count;
struct {
    /* Some thread specific data */
}* ThreadData;

int start_threads () {
    /* Code which starts the threads and allocates the threaddata. */
}

int f(thread_id) {
    /* return unique index into threadData */
}

int main() {
    thread_count = 64; /* This number will be small, e.g. < 64 */
    start_threads();
    ThreadData[f(thread_ids[0])]
}

Answer 1

是的，您可以在运行时构建最小完美哈希函数 (MPHF)。您可以使用多种算法，但其中大多数实现起来有点复杂，因此我无法为您提供有效的示例代码。许多在 cmph project 中实现.

最简单的可能是BDZ。在高层次上，查找需要计算 3 个哈希函数和 3 个内存访问。如果内存不是问题，您只需要 2 个。它支持数百万个 key 。当使用 3 个哈希函数且每个条目 2 位时，该算法需要一个大约是条目数 1.23 倍的查找表。

还有其他算法，一个是我自己发明的，the RecSplit algorithm (现在甚至有一个 research paper)，还有一个 C++ implementation , 和 Java马上。基本上，算法会找到一种方法(递归地)将集合拆分为子集，直到子集大小为 1。您需要记住拆分方式。最简单的解决方案实际上是使用查找表来查找“如何拆分”，但该表非常小，64 个键可能只有 5 个整数。第一个把16分成4个子集，4个把每个子集映射到一个数字0..15。

(如果您不需要最小完美哈希函数，我添加了第二个答案，只是一个完美哈希函数。构造更简单，查找也很多更快，但需要更大的阵列。)