用于存储数十亿个 64 位整数分类的数据结构

问：

我有一组 ~102 亿个 64 位元素，它们是：

1. 常量，在编译时之前已知（因此没有插入、删除或修改）。
2. 分为 3 类，也是恒定的，并且在编译时之前已知所有元素。
3. 它们存储 [0...11] 的排列和 11 位标记，该标记可以是 [0， 2047] 之间的任何数字。大多数排列将具有 2048 个可能标记中每个标记的元素。具体来说，将表示元素 at 的置换位置，并给出 11 位标记。(element >> (4 * pos)) & 0b1111poselement >> 48

我想满足的约束：

1. 内存消耗：在 4GB 以内以适合 RAM，因此平均每个元素最多 ~3.1 位。
2. 没有误报/误报：布隆滤镜作为潜在组件很好，但必须有一些回退来保证正确性。
3. “快速”查找元素的类别：由于这里的一切都是常数，我的理解是 O（log n） 实际上是一个小常数。操作本身发生得非常频繁，所以我认为时钟周期的估计值比渐近运行时更好。
4. （不那么重要）在 GPU 上运行良好：根据我的理解，这意味着算术运算比分支和全局内存访问更受欢迎。

考虑到内存限制和数据的部分结构化和恒定性，类似的帖子无法为我提供完整的解决方案。

大多数传统的数据结构都无法满足内存要求，因为它们通常存储元素本身（而 64 显然不在 ~3.1 位以内）。布隆过滤器本身并不理想，因为一个错误的分类可能会破坏算法的其余部分。

最小完美哈希函数可能是一个可行的解决方案。由于大多数排列都有一个与标记对应的元素，因此一种可能的方法是将 11 位标记与 48 位排列分开，在排列位上使用最小完美哈希，然后将其移开并重新添加 11 位标记。然后，我们用它来索引到一个位集中，其中 2 位用于表示元素的类别。我们将为每个元素留下 ~1.1 位，但最小完美哈希仅在排列位上，因此对于每个排列，我们实际上每个元素有 2252.8 位。但是，我不确定哪种最小完美哈希方案最适合我的用例（如果所有 12 个排列都在起作用，显而易见的选择是阶乘数系统，但实际上只有 ~1% 在数据中），我觉得可能有一种更直接的方法来解决这个问题。

由于有 3 个类别，我正在考虑为前 2 个类别进行某种设置并查询成员资格（检查第 3 个类别是没有必要的，因为如果它不在前 2 个类别中，那么它就在第 3 个类别中）。我完全不确定什么适合这种情况，因为如果只需要成员资格测试，一个完美的哈希函数似乎包含太多信息。我还研究了 trie 和相关策略，但我不确定它们是否适用于这个问题;从我所读到的内容来看，它们会消耗太多内存。非常感谢有关此主题的任何指导！

P.S. 一切都将用 C/C++ 实现，因此强烈建议使用这些语言的资源，但不是必需的。