是否可以创建一个Minimal Perfect Hash函数，而不需要一个小的（<64）键组的单独查找表？

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 project中实现的。

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

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

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

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