11

我最近阅读了这篇文章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])]
}
4

2 回答 2

5

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

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

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

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

于 2019-04-24T12:17:21.280 回答
3

您可以使用蛮力搜索按如下方式构建完美哈希。对于 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));
        }
    }
}
于 2019-04-25T07:09:40.997 回答