algorithm - 减少简单排序数组的内存开销

Question

我有一个按键值排序的项目数组，通过二分查找检索项目。这些项目的简化版本看起来像这样:

struct Item
{
    uint64_t key;
    uint64_t data;
};

我正在寻找减少 key 开销的方法。键值除了搜索外不用于任何其他用途。假设插入成本不是问题，但检索成本是问题，那么我可以使用哪种替代数据结构来将簿记开销减少到每项少于 64 位？

唯一的另一个“陷阱”是我需要能够检测到 key 不存在于集合中的情况。

Answer 1

一个明显的可能性是将您的 key 视为 8 个单独的字节并从中构建一个 trie。这结合了您的 key 中的通用前缀，因此如果您有(例如)一千个具有相同第一个字节的项目，您只存储第一个字节一次而不是一千次。