1

我花了几天时间试图让图书馆在我的系统上工作。该库有几种生成 MPHF 的算法。我对最小散列函数的理解是，当我使用 MPHF 散列两个不同的键时，它们将返回两个不同的 id。我生成的 200 万个键似乎不是这种情况（整数，由算法读取为字符串）。我已经尝试了该库实现的几种算法，但所有这些算法都会导致很多键出现重复的“ID”。

这是我写的：

#include <cmph.h>
#include <iostream>
#include <fstream>
#include <bitset>
#include <string>
#include <sstream>
#include <limits.h>

using namespace std;

int main(int argc, char** argv){

    FILE *fp = fopen("keys.txt", "r");
    FILE *read = fopen("keys2.txt", "r");
    ofstream ids("ids2.txt");

    if(!fp || !read || !ids.is_open()){
        cerr<<"Failed to open the file\n";
        exit(1);
    }

    cmph_t* hash = NULL;
    // source of keys
    cmph_io_adapter_t *source = cmph_io_nlfile_adapter(fp);
    cmph_config_t *config = cmph_config_new(source);
    cmph_config_set_algo(config, CMPH_BDZ);
    hash = cmph_new(config);
    cmph_config_destroy(config);

    char *k = (char *)malloc(sizeof(12));

    while(fgets(k, INT_MAX, read) != NULL){
        string key = k;
        unsigned int id = cmph_search(hash, k, (cmph_uint32)key.length());
        ids<<id<<"\n";
    }

    cmph_destroy(hash);
    cmph_io_nlfile_adapter_destroy(source);
    fclose(fp);
    fclose(read);
    ids.close();
}

如果算法声称生成最小完美散列函数，那么每个不同键的 ID 不应该是唯一的吗？有 2048383 个键。对于我的项目，我需要将 id 从 0 映射到 2048382，因为我计划使用最小的完美哈希函数。我不确定我的理解哪里出了问题。请帮忙。

4

1 回答 1

0

如果您keys2.txt包含的键不属于用于生成您的集合的一部分hash，那么根据 mphf 的定义，您将获得重复的哈希值，或者可能会获得超出范围的值。您可以存储用于生成的所有密钥，hash然后验证传递给的密钥是否cmph_search与导致 cmph_search 返回的哈希/ID 的密钥相同

于 2020-01-24T11:00:38.603 回答