如何在C++中使用libcuckoo的cuckoo_hash_map仅存储键？

我在C++项目中使用efficient/libcuckoo库，想要存储一组uint64_t类型的数据到cuckoo_hash_map中，但发现该容器无法仅存储键（我只关注键的哈希存在性）。在不更换布谷鸟哈希库或使用布隆过滤器的前提下，有没有内存效率更高的解决方案？注：仅需使用键，不需要值。

已尝试的方案及问题 #

• 方案一：创建pair<uint64_t, uint64_t>，将键存储两次（一次作为键，一次作为值）
  • 问题：内存占用翻倍，不符合哈希表尽可能小的需求
• 方案二：创建pair<uint64_t, Empty>，第一个元素为键，第二个元素是空类（sizeof(Empty) = 1）
  • 问题：每个键仍会占用1字节无用内存，优化不够彻底

最优解决方案：使用libcuckoo内置的cuckoo_hash_set #

libcuckoo本身提供了cuckoo_hash_set容器，专门用于仅存储唯一键的场景，完全匹配你的需求，没有任何额外内存开销：

#include <libcuckoo/cuckoo_hash_set.hh>

// 定义仅存储uint64_t的布谷鸟哈希集合
using UInt64Set = cuckoo_hash_set<uint64_t, std::hash<uint64_t>>;

// 使用示例
UInt64Set my_set;
my_set.insert(123456789ULL);
bool key_exists = my_set.contains(123456789ULL);

这个方案不需要修改任何现有逻辑，直接用集合替代映射，内存效率达到最优。

替代方案：基于cuckoo_hash_map的零开销空值优化 #

如果因项目限制必须继续使用cuckoo_hash_map，可以通过C++语言特性消除空值类型的内存开销：

1. C++20及以上：[[no_unique_address]]属性优化 #

定义空值类，配合[[no_unique_address]]让编译器彻底优化掉空值的内存占用：

struct EmptyValue {};

// 自定义键值对类型，利用no_unique_address消除空值开销
struct KeyValuePair {
    uint64_t key;
    [[no_unique_address]] EmptyValue value;

    // 满足libcuckoo对键值对的接口要求
    const uint64_t& first() const { return key; }
    uint64_t& first() { return key; }
    EmptyValue& second() { return value; }
    const EmptyValue& second() const { return value; }
};

// 使用自定义键值对的哈希表
using KeyOnlyMap = cuckoo_hash_map<
    uint64_t, EmptyValue, std::hash<uint64_t>,
    std::equal_to<uint64_t>, KeyValuePair
>;

此时KeyValuePair的大小等于uint64_t，无额外内存浪费。

2. 兼容C++11/14/17：空基类优化（EBO） #

通过让键值对结构体继承空类，触发空基类优化，消除空类的内存开销：

struct EmptyValue {};

// 继承空类触发EBO，空基类的内存被优化
struct KeyValuePair : public EmptyValue {
    uint64_t key;

    const uint64_t& first() const { return key; }
    uint64_t& first() { return key; }
    EmptyValue& second() { return *this; }
    const EmptyValue& second() const { return *this; }
};

using KeyOnlyMap = cuckoo_hash_map<
    uint64_t, EmptyValue, std::hash<uint64_t>,
    std::equal_to<uint64_t>, KeyValuePair
>;

这种方式下，KeyValuePair的大小同样等于uint64_t，没有多余内存占用。

内容的提问来源于stack exchange，提问作者Idan