如何将字符串添加到布谷鸟过滤器？

Question

我正在运行布谷鸟过滤器存储库提供的示例的修改版本：https://github.com/efficient/cuckoofilter/blob/master/example/test.cc

我想添加字符串到布谷鸟过滤器。虽然字符串已添加，但当我检查它是否存在于筛选器中时，它总是返回false。有人能指出我的方法有什么问题吗？

size_t total_items  = 1000000;
CuckooFilter<string, 12> filter(total_items);

// Insert items to this cuckoo filter
string temp1 = "sample";
if (filter.Add(temp1) != cuckoofilter::Ok) {
        cout<<"not added"<<endl;
}    

// Check if previously inserted items are in the filter
string temp2 = "sample";
assert(filter.Contain(temp2) == cuckoofilter::Ok);

断言应该是真的，但在本例中却是假的。为什么？

Answer 1

快速浏览一下https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L65的源代码就会发现它使用了一个函数

inline void GenerateIndexTagHash(const ItemType &item, size_t* index, uint32_t* tag) const
{
    std::string hashed_key = HashUtil::SHA1Hash(
        (const char*) &item,
        sizeof(item)
    );

// ... rest is skipped for brevity

}

以生成物品的初始索引和指纹(标签)。问题是它会对传递的实际对象进行散列。为了简化，它这样做：

// Your filter.Add(temp1) inside does this
HashUtil::SHA1Hash((const char*) &temp1, sizeof(temp1));

// Your filter.Contain(temp2) inside does this
HashUtil::SHA1Hash((const char*) &temp2, sizeof(temp2));

基本上，它散列两个完全不同的对象，如预期的那样，生成不同的散列并映射到不同的存储桶。

为了让它在您的例子中工作，它需要以一种散列实际字符串数据的方式调用HashUtil::SHA1Hash()，即：

// It should do something like this
HashUtil::SHA1Hash(
    temp1.c_str(), // <-- notice we pass a pointer to an actual character data rather than a pointer to an instance of a std::string()
    temp1.length()
);


HashUtil::SHA1Hash(
    temp2.c_str(), // <-- notice we pass a pointer to an actual character data rather than a pointer to an instance of a std::string()
    temp2.length()
);

这应该会回答你的为什么？有个问题。至于

谁能指出我的方法出了什么问题？

你的方法本身并没有什么问题，只是它不像你预期的那样工作，因为库不支持这样的用例。

Answer 2

我正在尝试将字符串添加到cuckoofilter库https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h

mycode

cuckoofilter::CuckooFilter<string, 12> cuckoo_mempool(total_items);

但每次运行代码时，我都会在https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L68行得到以下错误

错误:对‘(const cuckoofilter::TwoIndependentMultiplyShift) ( const std：：_cxx11：：basic_string&)’68的调用不匹配|const hash = hasher(item)；|^~