c++ - 在 block 之间存在间隙的 block 中存在键的情况下使用什么数据结构？

Question

我必须将数据存储在键(整数)遵循如下模式的位置:

1, 2, 4, 5, 60, 61, 63

也就是说， key 有时会聚集在由数百个 key 组成的 block 中，其中几乎没有间隙，但 block 之间可能会有很大的间隙。偶尔在不知名的地方有孤独的 key 或小块。

目前，std::map 用于存储 key ，但它在分析中显示为需要时间来查找 key 。这是因为我们需要随机访问 key ，而 key 有数千个。

到目前为止，最大 key 是 16 位，所以我尝试用 std::vector 替换，它在 Debug模式下(整个程序性能)加速了大约 10%。 Release模式是微不足道的变化，但我们在 Debug模式下做了很多长时间的工作。

但现在 key 的长度可能长达 32 位，所以这是不可能的。

我试过 std::unordered_map 但这比 std::map 性能差!我对 HashMap 没有太多经验，所以也许我可以调整哈希策略，但我不知道如何做。

对于这个任务的高效数据结构有什么建议吗？

谢谢。

Answer 1

如果键或多或少地不断传播(大规模)，您可以发明一种树结构并将每一层的数据分组在一起。

例如你的 key 范围从 0 到 1,000,000 那么你将在第一层:

1) all keys from 0 to 99,000
2) from 100,000 to 199,999
3) ...
10) from 900,00 to 1,000,000

然后你继续到较低的层，在那里你再次拆分子组。在最低层中，您有一个 vector ，其中包含该组中实际可用的键。通过拥有 3 个这样的层，您可以将要通过的键的数量减少到原始数量的 1/1000 倍。这将大大减少某个键的查找时间。