有没有可能为一小组(

Question

我最近读到了这篇关于为一组已知的键生成一个最小完美哈希表的文章：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])]
}

Answer 1

是的，您可以在运行时构建一个最小的完美散列函数(MPHF)。您可以使用多种算法，但大多数算法的实现都有点复杂，所以我不能给出工作示例代码。许多是在cmph项目中实施的。

最简单的大概就是BDZ了。在高级别上，查找需要计算3个散列函数和3次内存访问。如果记忆力不是问题，你只需要2。它支持数百万个密钥。这个算法需要一个大约是条目数1.23倍的查找表。

还有其他算法，一个是我自己发明的，RecSplit算法，但是我现在没有C实现，只有Java。基本上，算法找到了一种方法将集合分解成子集（递归），直到子集大小为1。你得记住你是怎么分开的。最简单的解决方案实际上是使用“如何拆分”的查找表，但该表真的很小，可能只有5个整数用于64个键。第一个划分为4个16的子集，4个将每个子集映射到一个数字0..15。

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