时间戳

首页 > 解决方案 > 是否可以在没有单独的查找表的情况下为一组小（<64）键创建最小完美哈希函数？

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

问题描述

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

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

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

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])]
}

标签： calgorithmhashperfect-hash

解决方案

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

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

还有其他算法，我自己发明的一种，RecSplit 算法（现在甚至有一篇研究论文），现在有一个C++ 实现和Java。基本上，算法找到了一种将集合拆分为子集（递归）的方法，直到子集大小为 1。您需要记住如何拆分。最简单的解决方案实际上是使用查找表来查找“你如何拆分”，但该表非常小，可能只有 5 个整数对应 64 个键。第一个分为 16 个的 4 个子集，4 个将每个子集映射到一个数字 0..15。

（如果您不严格需要一个最小完美散列函数，我添加了第二个答案，只需要一个完美散列函数。构造更简单，查找速度更快，但需要更大的数组。）

推荐阅读