cmph минимальное идеальное хеширование

Question

Я потратил несколько дней, пытаясь заставить библиотеку работать в моей системе. Библиотека имеет несколько алгоритмов, которые генерируют MPHF. Мое понимание минимальной хеш-функции заключается в том, что когда я хеширую два разных ключа с использованием MPHF, они возвращают два разных идентификатора. Это не похоже на случай с 2 ​​миллионами ключей, которые я сгенерировал (целые числа, считанные алгоритмом как строковые). Я пробовал несколько алгоритмов, которые реализует библиотека, но все они приводят к дублированию идентификаторов для многих ключей.

Вот что я написал:

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

Разве идентификаторы не должны быть уникальными для каждого отдельного ключа, если алгоритм утверждает, что генерирует минимальную совершенную хеш-функцию? Есть 2048383 ключей. Для моего проекта мне понадобятся идентификаторы для отображения от 0 до 2048382, так как я планирую использовать минимальную идеальную хеш-функцию. Я не уверен, где я иду не так с моим пониманием. Пожалуйста помоги.

Answer 1

Если твой keys2.txt содержит ключи, которые не были частью набора, который использовался для создания вашего hashто по определению mphf вы получите либо повторяющиеся хэши, либо, возможно, значения за пределами вашего диапазона. Вам решать хранить все ключи, которые использовались для генерацииhash а затем убедитесь, что ключ, переданный в cmph_search был таким же, как тот, который привел к хэшу / идентификатору, возвращенному cmph_search