cmph最小完美哈希

Question

我花了几天的时间试图使该库在我的系统上工作。该库具有几种生成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，因为我计划使用最小完美哈希函数。我不确定我的理解哪里出了问题。请帮助。

Answer 1

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