是否可以在不单独查找 table 一组小（<64）键的情况下创建最小完美哈希函数？

Question

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

这篇文章似乎假设你需要一个中级 table。如果我们假设密钥集很小（即 < 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 project.

中实现

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

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

（如果您不需要 minimal 完美哈希函数，我添加了第二个答案，只是 perfect 哈希函数。构造更简单，查找速度更快，但需要更大的数组。）

Answer 2

您可以使用暴力搜索按如下方式构建完美哈希。对于 64 个条目，目标数组的大小需要至少为 512 个条目，否则搜索将无法在合理的时间内找到索引。

那么完美的哈希函数就是murmur(x + perfectHashIndex) & (TARGET_SIZE - 1)

#include <stdio.h>
#include <stdint.h>
#include <string.h>

static uint64_t murmur64(uint64_t h) {
    h ^= h >> 33;
    h *= UINT64_C(0xff51afd7ed558ccd);
    h ^= h >> 33;
    h *= UINT64_C(0xc4ceb9fe1a85ec53);
    h ^= h >> 33;
    return h;
}

// must be a power of 2
#define TARGET_SIZE 512

static uint64_t findPerfectHashIndex(uint64_t *array, int size) {
    uint64_t used[TARGET_SIZE / 64];
    for (uint64_t index = 0; index < 1000;) {
        memset(used, 0, TARGET_SIZE / 64 * sizeof(uint64_t));
        for (size_t i = 0; i < size; i++) {
            uint64_t x = murmur64(array[i] + index) & (TARGET_SIZE - 1);
            if (((used[x >> 6] >> (x & 63)) & 1) != 0) {
                goto outer;
            }
            used[x >> 6] |= 1UL << (x & 63);
        }
        return index;
        outer:
        index++;
    }
    // not found
    return -1;
}

int main() {
    int size = 64;
    uint64_t ids[size];
    for(int i=0; i<size; i++) ids[i] = 10 * i;
    uint64_t perfectHashIndex = findPerfectHashIndex(ids, size);
    if (perfectHashIndex == -1) {
        printf("perfectHashIndex not found\n");
    } else {
        printf("perfectHashIndex = %lld\n", perfectHashIndex);
        for(int i=0; i<size; i++) {
            printf("  x[%d] = %lld, murmur(x + perfectHashIndex) & (TARGET_SIZE - 1) = %d\n", 
                i, ids[i], murmur64(ids[i] + perfectHashIndex) & (TARGET_SIZE - 1));
        }
    }
}

是否可以在不单独查找 table 一组小（<64）键的情况下创建最小完美哈希函数？

Is it possible to create a Minimal Perfect Hash function without a separate lookup table for a small (<64) set of keys?

c

algorithm

hash

perfect-hash