我正在尝试决定将哪种数据结构用于以下内容。
假设我有大约 1000 万个键，这些键包含指向包含某些数据的唯一对象的指针。
键是 UUID，将它们视为 16 字节二进制数组。 UUID 是使用优质随机数生成器生成的。
我一直在考虑以下内容，但想知道每种方法在速度和内存消耗方面的优缺点。一些公平的估计，64 位平台上的最佳/最差/平均情况会很好。
我需要能够插入几乎无限的项目。
二叉树 哈希表 Radix Tree (bit based or 2bit multi-way)
我需要对这些进行的操作是:插入、删除、查找
我喜欢基数树的想法，但它被证明是最难实现的，而且我还没有找到可以合并到商业产品中的合适实现。
最佳答案
- 你不关心订购
- 你的 key 已经是随机的
- 1000 万件
简短的回答
哈希表可能最适合您的情况。
速度
如果哈希是常量，哈希表 (std::unordered_map) 将为 O( 1 )。在您的情况下，O( 1 ) 成立，因为您甚至不需要散列 — 只需使用随机 UUID 的低 32 位就足够了。查找的成本将类似于一个或两个指针间接寻址。
二叉树 (std::map) 将是 O( log2 n )，所以对于 1000 万个项目，您将进行 24 次比较和 24 次潜在的缓存未命中。即使 n = 4,000，它也会使用 12 次比较，因此它很快就会变得比哈希表差得多。
基数树将是 O( k )，因此您将有最多 k 次比较和 k 潜在的缓存未命中。在极不可能的情况下，基数树将与哈希表一样快。更糟糕的是(假设 k = 一个有点合理的 16，对于 256 路树)它的性能会比二叉树好，但比哈希表差得多。
因此，如果速度是重中之重，请使用哈希表。
开销
典型的哈希表如果已满，每个项目将有大约 1-3 个指针的开销。如果未满，您可能会在每个空槽中浪费 1 个空间指针。你应该能够保持它几乎满，同时仍然比二叉树更快，因为你有一个非常随机的 key ，但为了尽可能快的速度，你当然要给它足够的空间。对于 32 位机器上的 1000 万个项目，预计整个表的开销为 38–114MiB。对于半满表，预计 76–153MiB。
红黑树，最常见的 std::map 实现，每个项目将有 3 个指针 + 1 个 bool。一些实现利用指针对齐将 bool 与其中一个指针合并。根据实现和哈希表的完整程度，红黑树的开销可能略低。预计 114–153MiB。
基数树的每个项目都有 1 个指针，每个空槽有 1 个指针。不幸的是，我认为这么大的随 secret 钥会导致你在树的边缘有很多空槽，所以它可能会比上面任何一个使用更多的内存。减小 k 可以降低此开销，但同样会降低性能。
如果最小开销很重要，请使用哈希表或二叉树。如果优先考虑，请使用完整的哈希表。
请注意 std::unordered_map 不允许您控制何时调整大小，因此很难得到一个完整的。 Boost Intrusive有一个非常好的 unordered_map 实现，可以让你直接控制它和许多其他东西。
关于c++ - 不同数据结构的速度/内存使用估计，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6678286/