c++ - 具有非常快速的 int-> 数据查找和快速反向查找(搜索/插入/删除数据)的压缩字典？

Question

我想实现一个字典，将唯一的异构数据(变体)与唯一的 int 配对，这样我就不会重复值(可能很大)，而是重复 int。需要时，我会通过字典将其转换为原始值。

数据集会很大，所以 O(1) 中的 (int->data) 很重要。 (data->int) 和插入/删除应该都是 O(log n) 平均情况，因为这些操作不太重要。数据的顺序无关紧要，但插入/删除不得使现有的 int 键无效。

我已经尝试过哈希表 和SSTable 方法。使用哈希表，即使使用哈希值作为索引，而不是将其与值一起存储，所需的存储空间也相当大。碰撞会降低效率，但所有操作的分摊复杂度为 O(1)。另一方面，SSTable 提供了更复杂的操作和重复值(一次用于 vector 存储，一次用于映射索引)。整体内存消耗仅略低于哈希表字典。

Dictionary概要要求:

• 查找整数->数据:O(1)
• 查找数据->int:O(log n) 最差
• 插入:O(log n) 最差
• 删除:最坏情况下为 O(log n) [或其他方法，如垃圾收集，如果不一直运行，性能可能更差]
• 可能的最低内存要求

有没有办法改进字典的设计，进一步降低内存需求，同时保留 O(1) int->data lookup 和合理的 insertion/removal/data->int？

Answer 1

如果int ->数据速度是最重要的，你应该设置它只是一个数组索引操作。

将数据对象保存在 std::vector<data> forward_map 中. int->data 只是一个 forward_map[i]查找，这是 O(1)，常数因子尽可能低。

---

使用独立数据结构来支持搜索/插入/删除操作。

根据您的“数据”对象支持的比较操作，可能是二叉搜索树或 std::unordered set会是不错的选择。 BST/set 的“值”类型只是一个 int , 但比较那些 int实际上比较forward_map[i] < forward_map[j] , 不根据i < j .

假设您有一个 std::unordered_set< forward_map_reference_t > reverse_map . (使用 STL 容器实际上并不那么容易，请参见下文。)

我们实际上是使用集合作为映射:关键是forward_map[val] , 值为 int val本身。

查找给定 int k 的 reverse_map 条目，您需要实际搜索 forward_map[k] .

• const data_t & lookup(int k) { return forward_map[k]; }

• int search(const data_t &) : reverse_map.find()效率很高。

• delete(const data_t &) :搜索并删除 reverse_map 条目，返回 int k .添加k到 forward_map 的 LIFO 空闲列表。 (不要触摸 forward_map 条目。如果您需要检测 use-after-free 的 forward_map 条目，那么此时将其归零或其他。)
• insert(const data_t &) :检查空闲列表的头部是否有要重用的条目，否则 forward_map.push_back() . k = 您将条目放在正向映射中的位置。添加 k到反向 map 。

避免存储 data_t 的另一个拷贝项，reverse_map 需要在其搜索操作中引用 forward_map。

由于缓存未命中，使用基于哈希表而不是搜索树的 reverse_map 具有潜在的巨大优势。通常，将键与树节点进行比较所需的所有数据都存在于节点中，但在这种情况下，它是对 forward_map 的引用。不仅来自 reverse_map 本身的加载会缓存未命中，forward_map[k] 也可能。 (与乱序 CPU 上的已知地址情况不同，未知地址的加载不能提前开始，所以这是非常糟糕的)。推测执行可能会从 reverse_map 开始进行下一次加载，但情况仍然很糟糕。 哈希表需要的总键比较要少得多，这是一个很大的优势。

---

使用STL容器？

这里使用 STL 容器实际上存在一个先有鸡还是先有蛋的问题:考虑一个 std::unordered_set<int> : key 类型是 int .我们会使用自定义 KeyEqual基于 forward_map[i] 比较的函数.但是只有 .find(const Key& key) , 不是 .find(const data_t&) .

一个丑陋的解决方法是临时复制一个 data_t进入 forward_map 中的空闲位置所以它会有一个我们可以传递给 unordered_set<int, custom_compare>::find 的索引, 但这种额外的复制是愚蠢的。

另一个不好的选择(可能不会在编译时优化掉)是一个带有虚函数来访问data_t的类。 .该 map 包含一个带有单个 int 的类成员。我们会通过 .find()派生类也有一个 data_t & ，并在 Hash 和 KeyEquals 函数使用的虚函数重载中引用它而不是 int 数组索引。

您可能必须构建自己的自定义数据结构，或使用 STL 以外的其他东西，除非有办法让 STL 接受与现有集合成员不同类型的键。