我正在尝试决定以下使用哪种数据结构。
假设我可能有 1000 万个键，其中包含指向包含某些数据的唯一对象的指针。
键是 UUID 将它们视为 16 字节二进制数组。UUID 是使用优质随机数生成器生成的。
我一直在考虑以下内容，但想知道每个人在速度和内存消耗方面的优缺点。一些公平的估计，64 位平台上的最佳/最差/平均情况会很好。
我需要能够插入几乎无限的项目。
二叉树哈希表基数树（基于位或2位多路）
我需要的操作是：插入、删除、搜索
我喜欢基数树的想法，但事实证明它是最难实现的，而且我还没有找到可以整合到商业产品中的合适实现。
简短的回答
哈希表可能最适合您的情况。
速度
如果散列是常数，则散列表 ( std::unordered_map) 将为O ( 1 )。在您的情况下，O ( 1 ) 成立，因为您甚至不需要散列 - 仅使用随机 UUID 的低 32 位就足够了。查找的成本将类似于一两个指针间接。
二叉树 ( std::map) 将为O ( log 2 n )，因此对于 1000 万个项目，您将有 24 次比较和 24 次潜在的缓存未命中。即使对于n = 4,000，它也会使用 12 次比较，因此它很快就会变得比哈希表差得多。
基数树将是O ( k )，因此您将有最多k个比较和k个潜在的缓存未命中。在极不可能的最好情况下，基数树将与哈希表一样快。更糟糕的是（假设k = 一个合理的 16，对于 256 路树）它会比二叉树执行得更好，但比哈希表差得多。
因此，如果速度是重中之重，请使用哈希表。
高架
一个典型的哈希表如果满了，每个项目将有大约 1-3 个开销指针。如果未满，您可能会在每个空槽中浪费 1 个空间指针。你应该能够保持它几乎满，同时仍然比二叉树更快，因为你有一个非常随机的密钥，但是为了尽可能快的速度，你当然希望给它足够的空间。对于 32 位机器上的 1000 万个项目，一个完整的表预计会有 38–114MiB 的开销。对于半满桌，预计 76–153MiB。
红黑树是最常见的std::map实现，每个项目将有 3 个指针 + 1 个布尔值。一些实现利用指针对齐来将布尔值与其中一个指针合并。根据实现和哈希表的完整程度，红黑树的开销可能略低。预计 114–153MiB。
基数树每个项目有 1 个指针，每个空槽有 1 个指针。不幸的是，我认为如此大的随机键会导致您在树的边缘有很多空槽，因此它可能会比上述任何一个使用更多的内存。减小k可以降低这种开销，但同样会降低性能。
如果最小开销很重要，请使用哈希表或二叉树。如果是优先级，请使用完整的哈希表。
请注意，std::unordered_map它不会让您控制何时调整大小，因此很难获得一个完整的。 Boost Intrusive有一个非常好的unordered_map实现，可以让你直接控制它和许多其他事情。
我会尝试std::map或std::unordered_map首先。
多年来，他们有许多聪明人开发和改进他们。
有什么理由不能使用std::maporstd::unordered_map吗？
我只是做了一个快速计算，我认为你可能对标准树没问题。1000 万个密钥是一个合理的数字。使用一棵平衡树，它的深度只有 23 个节点要检查。使用基数树，您实际上需要检查 128 位的密钥长度。
您的密钥也可以非常便宜地表示和比较。使用两个 64 位值的元组（boost 或 0x）来获得相同的 128 位密钥。元组排序足以在地图中使用。因此，密钥复制很便宜，相比之下也是如此。按原样比较整数可能比为基数深度搜索进行掩码和基于位的比较便宜。
所以在这种情况下，地图可能工作得很好。
*我会避免在unordered_map这里，因为 UUID 往往是结构化数据。这意味着标准散列过程（用于散列映射）很容易在性能上很差。*
更新：
由于您使用的是随机 UUID，因此散列可能会很好——尽管如此大的散列表需要很大的内存开销才能保持效率。
此外，给定完全随机的 UUID，基数可能最终具有与树相同的平衡（因为密钥分布是完全均匀的）。因此，您可能无法保存偶数步，并且仍然会产生位操作的开销。但是有很多方法可以专门化和优化基数树，很难确定它是否可以更快，或者总是更慢。
IMO 基数树并不难实现。但是，一个简单的哈希表就足够了。只需分配 2^16 个对象列表的数组，并使用 UUID 的前 2 个字节来索引插入对象的列表。然后您可以搜索仅包含大约 160 个项目的列表。
或者，分配 20M 指针数组。要存储一个对象，只需在 0-20M 范围内创建一个 UUID 散列，找到第一个空闲 (NULL) 指针并将其存储在那里。搜索意味着从哈希值走到第一个 NULL 值。删除也很简单....尝试阅读http://en.wikipedia.org/wiki/Hash_function